算法题

Posted on   |   In

近期温习下丢了很长时间的数据结构和算法，用python实现。

第一周

1、面试题 01.03. URL化：https://leetcode-cn.com/problems/string-to-url-lcci/

1
2
3
4
5
6
7
8
9
class Solution:
    def replaceSpaces(self, S: str, length: int) -> str:
        S1 = ""
        for index in range(length):
            if S[index] == " ":
                S1 = S1 + "%20"
            else:
                S1 = S1 + S[index]
        return S1

2、1528. 重新排列字符串：https://leetcode-cn.com/problems/shuffle-string/

1
2
3
4
5
6
7
8
class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        s2 = []
        for i in range(len(indices)):
            s2.append("")
        for i in range(len(indices)):
            s2[indices[i]] = s[i]
        return ''.join(s2)  #做一次字符串数组转字符转

第二周

1、两数相加：https://leetcode-cn.com/problems/add-two-numbers/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        promote = 0
        res = ListNode()
        r = res
        while p != None or q != None:
            if p != None and q != None:
                sum = p.val + q.val + promote
            elif p == None and q != None:
                sum = q.val + promote
            elif p != None and q == None:
                sum = p.val + promote
            
            if p == l1 and q == l2:
                r.val = sum%10
            else:
                r.next = ListNode(sum%10, None)
                r = r.next
            promote = int(sum/10)
            if p != None:
                p = p.next
            if q != None:
                q = q.next
        if promote != 0:
            r.next = ListNode(promote, None)
        return res

2、反转链表：https://leetcode-cn.com/problems/reverse-linked-list/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """迭代"""
    def reverseList2(self, head: ListNode) -> ListNode:
        if head == None:
            return
        elif head.next == None:
            return head
        p = head
        q = head.next
        r = q
        p.next = None
        while q != None: #迭代
            r = r.next #r在最前面，后更新
            q.next = p
            p = q
            q = r
        return p
        """递归"""
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None:
            return
        elif head.next == None:
            return head
        elif head.next.next == None:
            head.next.next = head
            new_head = head.next
            head.next = None
            return new_head
        else:
            new_head = self.reverseList(head.next) #开始递归
            head.next.next = head
            head.next = None
            return new_head