剑指Offer

Posted on   |   Updated on | In | | Visitors

2. 实现Singleton模式

使用__new__控制实例创建过程

1
2
3
4
5
6
7
8
9
class Singleton:
    _instance = None
    def __new__(cls, *args, **kw):
        if not cls._instance:
            cls._instance = super().__new__(cls)
        return cls._instance

class MyClass(Singleton):
    pass

使用decorator

1
2
3
4
5
6
7
8
9
10
11
12
13
from functools import wraps
def singleton(cls):
    instances = {}
    @wraps(cls)
    def get_instance(*args, **kw):
        if cls not in instances:
            instances[cls] = cls(*args, **kw)
        return instances[cls]
    return get_instance

@singleton
class Myclass:
    pass

使用元类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Singleton(type):
    def __init__(self, *args, **kwargs):
        self.__instance = None
        super().__init__(*args, **kwargs)
        
    def __call__(self, *args, **kwargs): 
        if self.__instance is None:
            self.__instance = super().__call__(*args, **kwargs)
            return self.__instance 
        else:
            return self.__instance
# Example
class Spam(metaclass=Singleton):
    def __init__(self):
		print('Creating Spam')

3 数组中重复的数字

牛客网传送门

书中参数还传了一个数组用来保存重复的数字，身为一个Pythoner，直接返回tuple。

1
2
3
4
5
6
7
8
9
def duplicate(nums: list) -> int:
    for i, num in enumerate(nums):
        while i != num:
            if num == nums[num]:
                return True, num
            else:
                nums[i], nums[num] = nums[num], nums[i]
                num = nums[i]
    return False, None

3_1 数组中重复的数字，不能修改数组

AcWing传送门

元素范围变成了1~n。此方法有缺陷，不能找出所有的重复的数字，因为在1~2的范围里有1和2两个数字，这个范围的数字也出现两次，不能确定是每个数字各出现一次还是某个数字出现了两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find_duplicate(nums: list) -> int:
    def count_range(i, j):
        return sum(i<=num<=j for num in nums)

    lo = 1
    hi = len(nums) - 1     # n为范围
    while lo <= hi:
        mid = (lo + hi) // 2
        count = count_range(lo, mid)
        if lo == hi:
            if count > 1:
                return lo
            else:
                break
        if count > mid-lo+1:
            hi = mid
        else:
            lo = mid + 1
    return -1

4. 二维数组中的查找

牛客网传送门

AcWing传送门

LeetCode传送门

选取右上角为起始点。

1
2
3
4
5
6
7
8
9
10
11
def find(target, array):
    row = 0
    col = len(array[0]) - 1
    while col >= 0 and row <= len(array)-1:
        if array[row][col] > target:
            col -= 1
        elif array[row][col] < target:
            row += 1
        else:
            return True
    return False

更为优雅的方法。

1
2
3
4
5
6
7
8
def searchMatrix(self, matrix, target):
    j = -1
    for row in matrix:
        while j + len(row) and row[j] > target:
            j -= 1
        if row[j] == target:
            return True
    return False

5.替换空格

牛客网传送门

AcWing传送门

1
2
def replaceSpace(self, s):
    return ''.join(c if c!=' ' else '%20' for c in s)

6.从尾到头打印链表

AcWing传送门

1
2
3
4
5
6
def printListFromTailToHead(self, listNode):
    stack, h = [], listNode
    while h:
        stack.append(h.val)
        h = h.next
    return stack[::-1]

7.重建二叉树

LeetCode传送门

说明：根据前序遍历和中序遍历重建二叉树，假设遍历结果中不包含重复的数字。

1
2
3
4
5
6
7
8
9
def buildTree(preorder, inorder):
    if preorder == []:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    cut = inorder.index(root_val)
    root.left = buildTree(preorder[1:cut+1], inorder[:cut])
    root.right = buildTree(preorder[cut+1:], inorder[cut+1:])
    return root

方法二：空间复杂度更低的解法。

1
2
3
4
5
6
7
8
9
10
11
def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
    def build(stop):
        if inorder and inorder[-1] != stop:
            root = TreeNode(preorder.pop())
            root.left = build(root.val)
            inorder.pop()
            root.right = build(stop)
            return root
    preorder.reverse()
    inorder.reverse()
    return build(None)

8 二叉树的下一个节点

牛客网传送门

AcWing传送门

如果节点有右子树，那么下一个节点为右子树中的最左节点；

如果节点是父节点的左子节点，那么父节点就是下一个节点；

如果节点是父节点的右子节点，沿着父节点向上遍历找到祖先节点中，为父节点左子节点的点，这个左子节点的父节点就是下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def GetNext(self, pNode):
    # write code here
    if not pNode:
        return None
    # 有右子树，右子树中最左节点
    if pNode.right:
        pre = pNode.right
        while pre.left:
            pre = pre.left
        return pre
    while pNode.next:
        parent = pNode.next
        if parent.left == pNode:
            return parent
        pNode = parent
    return None

9.用两个栈实现队列

LeetCode传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    def push(self, x: int) -> None:
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())
        
    def pop(self) -> int:
        return self.s1.pop()
        
    def peek(self) -> int:
        return self.s1[-1]
        
    def empty(self) -> bool:
        return self.s1 == []

9.1用两个队列实现栈

LeetCode传送门

两个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyStack:

    def __init__(self):
        from collections import deque
        self.q1, self.q2 = deque(), deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]
        
    def empty(self) -> bool:
        return not self.q1

单队列旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyStack:

    def __init__(self):
        from collections import deque
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # self.q.rotate(1)  这里是用了双端队列的特性
        # self.q.rotate(1-len(self.q))  这里和下面循环是一样的效果
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]
        
    def empty(self) -> bool:
        return not self.q

10.斐波那契数列

LeetCode传送门

1
2
3
4
5
def fibonacci(n):
    a = b = 1
    for _ in range(n-1):
        a, b = b, a+b
    return b

11.旋转数组的最小数字

LeetCode传送门

思路：通过二分法不断缩小范围，由于mid是整除，最后l==mid，并且nums[mid] > nums[r]的。

1
2
3
4
5
6
7
8
9
10
11
12
def find_min(nums):
    l, r = 0, len(nums)-1
    if nums[l] < nums[r]:
        return nums[l]
    while l <= r:
        mid = (l+r) // 2
        if nums[mid] > nums[l]:
            l = mid
        elif nums[mid] < nums[r]:
            r = mid
        else:
            return nums[r]

12.矩阵中的路径

LeetCode传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def exist(self, board: List[List[str]], word: str) -> bool:

    def dfs(i, j, remain):
        if not remain: return True
        origin, board[i][j] = board[i][j], '-'
        for x, y in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
            if 0<=x<M and 0<=y<N and remain[0]==board[x][y]:
                if dfs(x, y, remain[1:]):
                    return True
        board[i][j] = origin
        return False

    M, N = len(board), len(board[0])
    return any(dfs(i, j, word[1:]) for i in range(M) for j in range(N) if word[0]==board[i][j])

13. 机器人的运动范围

AcWing传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def movingCount(self, m: int, n: int, k: int) -> int:

    visited = [[False]*n for _ in range(m)]

    def is_arive(i, j):
        return sum(map(int, str(i)+str(j))) <= k

    def dfs(i, j):
        if is_arive(i, j):
            visited[i][j] = True
            for x, y in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
                if 0<=x<m and 0<=y<n and not visited[x][y]:
                    dfs(x, y)

    dfs(0, 0)
    return sum(sum(visited, []))

14.剪绳子

AcWing传送门

说明：数学思想，当n>=5时，2(n-2)>n并且3(n-3)>n，而且3(n-3) >= 2(n-2)，所以尽可能多剪长度为3的绳子。如果长度为4的时候，2*2>3*1，所以4的时候就剪成2*2的两段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def cut_rope(length):
    if length < 2:
        return 0
    if length == 2:
        return 1
    if length == 3:
        return 2
    
    # 尽可能剪出3
    timesOf3 = length // 3
    # 如果最后余1，则留一段4分成两半
    if length-timesOf3*3 == 1:
        timeOf3 -= 1
    timesOf2 = (length-timesOf3*3) // 2
    return (3**timesOf3) * (2**timesOf2)

15.二进制中1的个数

LeetCode传送门

方法一：常规解法，使用1与n作与运算，如果不是0说明，含有一个1。

1
2
3
4
5
6
def hamming_weight(n):
    count = 0
    for _ in range(32):
        count += (n&1==1)
        n >>= 1
    return count

方法二：关键点是，一个数n和n-1的与运算操作，相当于去掉了最右面的1。
1
2
3
4
5
6
def hamming_weigth(n):
    bits = 0
    while n:
        bits += 1
        n = (n-1) & n
    return bits

16.数值的整数次方

LeetCode传送门

这里需要注意的一点ans *= ans不能写成ans = ans**2因为浮点数是有范围的，可能会超出范围报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def myPow(self, x: float, n: int) -> float:
    
    def pow_with_unsigned(x, n):
        if n == 0:
            return 1
        if n == 1:
            return x
        ans = pow_with_unsigned(x, n>>1)
        ans *= ans
        if n & 1 == 1:
            ans *= x
        return ans

    if n < 0:
        return 1 / pow_with_unsigned(x, -n)
    else:
        return pow_with_unsigned(x, n)

17 打印从1到最大的n位数

404.

打印呗，反正Python的int没有长度限制。

1
2
3
4
def print_n(n: int):
    n = 10 ** (n)
    for i in range(1, n):
        print(i)

18.删除链表中的节点

LeetCode传送门

开始看到这题的思路是，要是能拿到父节点就好了，然后这道题需要别的思路，其关键在于复制

1
2
3
def deleteNode(self, node):
    node.val = node.next.val  # 4->1->1->9
    node.next = node.next.next  # 4->1->9

19.正则表达式

LeetCode传送门

先考虑没有*的情况，通过一个递归逐个字符判断

1
2
3
4
def match(text, pattern):
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    return first_match and match(text[1:], pattern[1:])

当*出现时，一定会在前面跟一个其他字符，所以一定会出现在pattern[1]的位置。一种情况是我们忽略这对pattern，因为可以出现0次；另一种情况是匹配上这个字符，用递归的方式匹配下一个。

一定要用f_match = bool(s)，否则结果可能输出''

1
2
3
4
5
6
7
8
9
@lru_cache(None)
def match(self, s, pattern):
    if not pattern: return not s
    f_match = bool(s) and pattern[0] in {s[0], '.'}
    if len(pattern) > 1 and pattern[1] == '*':
        return (self.match(s, pattern[2:]) or
                (f_match and self.match(s[1:], pattern)))
    else:
        return f_match and self.match(s[1:], pattern[1:])

20. 表示数值的字符串

65. Valid Number

此处留坑，排名第一的python答案暂时没有理解。

21.调整数组顺序使奇数位于偶数前面

AcWing传送门

生成器写法，

1
2
3
4
def exchange(self, nums: List[int]) -> List[int]:
    odd = (num for num in nums if num&1)
    even = (num for num in nums if num&1==0)
    return list(chain(odd, even))

时间：O(n), 空间O(1)

1
2
3
4
5
6
7
8
9
def reOrderArray(self, array):
    # write code here
    l, r = 0, len(array)-1
    while l < r:
        while l < r and array[l]&1 == 1:
            l += 1
        while l < r and array[r]&1 == 0:
            r -= 1
        array[l], array[r] = array[r], array[l]

看了一下没有通过牛客网的测试用例，因为题目有些不同，牛客网要求奇数和奇数，偶数和偶数之前的相对位置不变。

1
2
def reOrderArray(array):
    return sorted(array, key=lambda x:x&1==0)

不使用sort

1
2
3
4
5
6
7
8
9
10
11
def reOrderArray(self, array):
    # write code here
    from collections import deque
    q = deque()
    n = len(array)
    for i in range(n):
        if array[-i-1] & 1 == 1:  # 从后找奇数
            q.appendleft(array[-i-1])
        if array[i] & 1 == 0:  #从前找偶数
            q.append(array[i])
    return q

22.链表中倒数第k个节点

AcWing传送门

思路：两个指针，快指针先走k步，然后两个一起走，快指针走到尾节点时，慢指针在倒数第k个节点。
需考虑k=0时和fast已经走到尾节点的情况。

1
2
3
4
5
6
7
8
9
10
def FindKthToTail(self, head, k):
    fast = slow = head
    for _ in range(k):
        if fast:
            fast = fast.next
        else:
            return None
    while fast:
        slow, fast = slow.next, fast.next
    return slow

23.链表中环的入口节点

LeetCode传送门

  • 首先判断此链表是否有环。
  • 然后再相交点和头结点一起走，一定会在入口相遇。
1
2
3
4
5
6
7
8
9
10
11
12
13
def detectCycle(self, head):        
    fast = slow = head
    # 检测是否有环
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    # 找出入口节点
    while head is not slow:
        head, slow = head.next, slow.next
    return head

24.反转链表

LeetCode传送门

1
2
3
4
5
def reverseList(self, head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

25.合并两个有序链表

LeetCode传送门

方法1：iteratively 迭代

1
2
3
4
5
6
7
8
9
10
def mergeTwoLists(l1, l2):
    l = head = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            l.next, l1 = l1, l1.next
        else:
            l.next, l2 = l2, l2.next
        l = l.next
    l.next = l1 or l2
    return head.next

方法2：recursively 递归

1
2
3
4
5
6
7
8
9
10
def mergeTwoLists(l1, l2):
    # 判断是否存在None
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

26.树的子结构

572. Subtree of Another Tree

二刷的时候突然发现，此题和LeetCode中不同。LeetCode中子树4-1-2返回False因为2下边还有节点，所以不一样；而书中认为True，不考虑2下边的节点。

1
2
3
4
5
6
7
    3
   / \
  4   5
 / \
1   2
   /
  0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isSubStructure(self, s: TreeNode, t: TreeNode) -> bool:

    def is_same(t1, t2):
        if not t2:
            return True
        if not t1:
            return False
        return t1.val==t2.val and is_same(t1.left, t2.left) and is_same(t1.right, t2.right)     

    if not s or not t: return False
    stack = s and [s]
    while stack:
        node = stack.pop()
        if node:
            if is_same(node, t):
                return True
            stack.append(node.right)
            stack.append(node.left)
    return False

方法二：学到一个递归写法，更简单。

1
2
3
4
5
6
7
8
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:

    def recur(A, B):
        if not B: return True
        if not A or A.val != B.val: return False
        return recur(A.left, B.left) and recur(A.right, B.right)

    return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

27.二叉树的镜像

AcWing传送门

1
2
3
4
5
6
def Mirror(self, root):
    if root:
        root.left, root.right = root.right, root.left
        self.Mirror(root.left)
        self.Mirror(root.right)
		return root

迭代

1
2
3
4
5
6
7
def Mirror(self, root):
    stack = root and [root]
    while stack:
        n = stack.pop()
        if n:
            n.left, n.right = n.right, n.left
            stack += n.right, n.left

28.对称的二叉树

LeetCode传送门

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

方法一：recursively.

1
2
3
4
5
6
7
8
9
10
11
12
def isSymmetric(self, root: 'TreeNode') -> 'bool':

    def symmetric(p1, p2):
        if p1 and p2:
            return (p1.val == p2.val and symmetric(p1.left, p2.right) and 
                    symmetric(p1.right, p2.left))
        else:
            return p1 is p2

    if not root:
        return True
    return symmetric(root.left, root.right)

方法二：iteratively.

1
2
3
4
5
6
7
8
9
10
def isSymmetric(self, root: 'TreeNode') -> 'bool':
    stack = root and [(root.left, root.right)]        
    while stack:
        p1, p2 = stack.pop()
        if not p1 and not p2: continue
        if not p1 or not p2: return False
        if p1.val != p2.val: return False
        stack.append((p1.left, p2.right))
        stack.append((p1.right, p2.left))
    return True

29.顺时针打印矩阵

LeetCode传送门

这里注意一点matrix.pop(0)需要转成list，因为zip函数中的每个元素是一个tuple，如果不转变成了一个tuple+list，会抛出异常。

1
2
3
def spiralOrder(self, matrix):
    return (matrix and list(matrix.pop(0)) + 
            self.spiralOrder(list(zip(*matrix))[::-1]))

方法二：迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix: return []
    M, N = len(matrix), len(matrix[0])
    ans = []
    seen = [[False]*N for _ in range(M)]
    x, y, di, dj = 0, 0, 0, 1
    while len(ans) < M*N:
        seen[x][y] = True
        ans.append(matrix[x][y])        
        nx, ny = x+di, y+dj
        if not (0<=nx<M and 0<=ny<N and not seen[nx][ny]):
            di, dj = dj, -di
        x, y = x+di, y+dj
    return ans

此题有个变形，如果逆时针该如何打印。这样的话情况稍微复杂一些。

1
2
3
4
5
6
7
def anti_clock_wise(self, matrix)
    if not matrix:
        return []
    clock_wise = list(zip(*(matrix[::-1])))
    a = list(clock_wise.pop(0))[::-1]
    b = self.anti_clock_wise(clock_wise)
    return a + b

30.包含min函数的栈

LeetCode传送门

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
class MinStack:

    def __init__(self):
        self._stack = []
        
    def push(self, x: int) -> None:
        cur_min = self.getMin()
        if x < cur_min:
            cur_min = x
        self._stack.append((x, cur_min))
        
    def pop(self) -> None:
        self._stack.pop()

    def top(self) -> int:
        if not self._stack:
            return None
        else:
            return self._stack[-1][0]

    def getMin(self) -> int:
        if not self._stack:
            return float('inf')
        else:
            return self._stack[-1][1]

31.栈的压入、弹出序列

LeetCode传送门

1
2
3
4
5
6
7
8
9
def validateStackSequences(self, pushed: 'List[int]', popped: 'List[int]') -> 'bool':
    stack = []
    j = 0
    for num in pushed:
        stack.append(num)
        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return j == len(popped)

32.从上到下打印二叉树

AcWing传送门

1
2
3
4
5
6
7
8
def levelOrder(self, root: TreeNode) -> List[int]:
    ans, q = [], [root]
    for node in q:
        if node:
            ans.append(node.val)
            q.append(node.left)
            q.append(node.right)
    return ans

32.1分层从上到下打印二叉树

LeetCode传送门

1
2
3
4
5
6
def levelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
    ans, level = [], root and [root]
    while level:
        ans.append([n.val for n in level])
        level = [k for n in level for k in (n.left, n.right) if k]
    return ans

32.2之字形打印二叉树

LeetCode传送门

1
2
3
4
5
6
7
def zigzagLevelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
    ans, level, order = [], root and [root], 1
    while level:
        ans.append([n.val for n in level][::order])
        order *= -1
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return ans

33.是否是二叉树的后序遍历

AcWing传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def VerifySquenceOfBST(self, seq):
    from itertools import takewhile
    if not seq:
        return False
    p = seq[-1]
    left_sub = list(takewhile(lambda x: x < p, seq[:-1]))
    right_sub = seq[len(left_sub):-1]
    if not all(x>p for x in right_sub):
        return False
    left = right = True
    if left_sub:
        left = self.VerifySquenceOfBST(left_sub)
    if right_sub:
        right = self.VerifySquenceOfBST(right_sub)
    return left and right

34.二叉树和为某一值的路径

LeetCode传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
[
   [5,4,11,2],
   [5,8,4,5]
]
方法一：iteratively. 举一反三。 
1
2
3
4
5
6
7
8
9
10
11
12
def pathSum(self, root: 'TreeNode', total: 'int') -> 'List[List[int]]':
    stack = root and [(root, [root.val], total)]
    ans = []
    while stack:
        n, v, t = stack.pop()
        if not n.left and not n.right and n.val==t:
            ans.append(v)
        if n.right:
            stack.append((n.right, v+[n.right.val], t-n.val))
        if n.left:
            stack.append((n.left, v+[n.left.val], t-n.val))
    return ans

recursively. 先找出所有路径，再过滤，实际上和257题一样。不过这并没有把这道题的特性涵盖进去。

1
2
3
4
5
6
7
8
9
10
def pathSum(self, root, sum_val):
    paths = self.all_paths(root)
    return [path for path in paths if sum(path)==sum_val]
    
def all_paths(self, root):
    if not root:
        return []
    return [[root.val]+path
            for kid in (root.left, root.right) if kid
            for path in self.all_paths(kid)] or [[root.val]]

方法二：模板写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:

    def dfs(node, s, p):
        if node:
            p.append(node.val)
            s -= node.val
            if not node.left and not node.right and s==0:
                ans.append(p[:])
            dfs(node.left, s, p)
            dfs(node.right, s, p)
            p.pop()

    ans = []
    dfs(root, total, [])
    return ans
方法三：recursively. 
1
2
3
4
5
6
7
8
9
def pathSum(self, root, sum):
    if not root:
        return []
    val, *kids = root.val, root.left, root.right
    if any(kids):
        return [[val] + path
                for kid in kids if kid
                for path in self.pathSum(kid, sum-val)]
    return [[val]] if val==sum else []

35.复杂链表的复制

LeetCode传送门

方法一：遍历两次。

1
2
3
4
5
6
7
8
9
10
11
def copyRandomList(self, head: 'Node') -> 'Node':
    cp = {None: None}
    m = n = head
    while m:
        cp[m] = Node(m.val, None, None)
        m = m.next
    while n:
        cp[n].next = cp[n.next]
        cp[n].random = cp[n.random]
        n = n.next
    return cp[head]

Time-O(n), Memory-O(n). 这种方式是相当于把第一次迭代的过程委托给了defaultdict，通过创建一个默认的对象，再去修改它的label值。

1
2
3
4
5
6
7
8
9
10
def copyRandomList(self, head: 'Node') -> 'Node':
    cp = collections.defaultdict(lambda: Node(0, None, None))
    cp[None] = None
    h = head
    while h:
        cp[h].val = h.val
        cp[h].next = cp[h.next]
        cp[h].random = cp[h.random]
        h = h.next
    return cp[head]

36.二叉搜索树与双向链表

LeetCode有此题，但是不是免费的。

AcWing传送门

方法一：中序遍历，再构造链表。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def convert(self, root):
    from itertools import tee
    def dfs(node):
        if node:
            yield from dfs(node.left)
            yield node
            yield from dfs(node.right)

    a, b = tee(dfs(root))
    ans = next(b, None)
    for f, s in zip(a, b):
        f.right = s
        s.left = f
    return ans
方法二：分别递归处理左子树和右子树。 
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
def Convert(self, root):
    
    def convert_tree(node):
        if not node:
            return None  
        if node.left:
            left = convert_tree(node.left)
            while left.right:
                left = left.right
            left.right = node
            node.left = left
        if node.right:
            right = convert_tree(node.right)
            while right.left:
                right = right.left
            right.left = node
            node.right = right
        return node

    if not root:
        return root
    root = convert_tree(root)
    while root.left:
        root = root.left
    return root
方法三：Morris Traversal. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def Convert(self, root):
    cur = root
    pre = ans = None
    while cur:
        while cur.left:
            q = cur.left
            while q.right:
                q = q.right
            q.right = cur                   # 补齐右指针
            cur.left, cur = None, cur.left  # 拆掉左指针
        cur.left = pre
        if pre is None:
            ans = cur   # 这里是为了找到链表的头，只执行一次
        else:
            pre.right = cur
        pre, cur = cur, cur.right
    return ans

37.序列化二叉树

LeetCode传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Codec:

    def serialize(self, root):
        if not root:
            return '$'
        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)

    def deserialize(self, data):
        
        def deserialize_tree(nodes):
            val = next(nodes)		# 这里不会报错的原因是，序列化后必然以`$`结尾的，所以不会出现耗尽的情况
            if val == '$':
                return None
            root = TreeNode(val)
            root.left = deserialize_tree(nodes)
            root.right = deserialize_tree(nodes)
            return root     
        nodes = iter(data.split(','))
        return deserialize_tree(nodes)

38.字符串的排列

46. Permutations II

LeetCode传送门

使用itertools

1
2
3
4
5
6
def Permutation(self, ss):
    # write code here
    from itertools import permutations
    if not ss:
        return []
    return sorted(list(set([''.join(x) for x in permutations(ss)])))

这里注意几点：

  • 为什么要判断if not ss，是因为如果ss=''的时时候，返回了['']而不是[]。因为这里返回了一个空的tuple，所以在列表推导式中是有一个元素的。

    1
    2
    >>> list(permutations('', 0))
    [()]
  • 为什么使用set去重，因为当ss='aa'的时候，牛客网的测试用例要求返回一个元素，即['aa']。
  • 排序也是为了满足测试用例。

自己实现。这里拆成两个方法的原因还是因为ss=''的时候会影响递归循环。

1
2
3
4
5
6
7
8
9
10
def Permutation(self, ss):
    if not ss:
        return []
    return self.permute(ss)

def permute(self, ss):
    return sorted(list(set([h + p
        for i, h in enumerate(ss)
        for p in self.permute(ss[:i]+ss[i+1:])
    ]))) or [""]
方法二：迭代。 
1
2
3
4
5
6
def Permutation(self, ss):
    ans = ['']
    for s in ss:
        ans = [p[:i] + s + p[i:]
               for p in ans for i in range((p+s).index(s)+1)]
    return sorted(ans) if ss else []

39.数组中出现次数超过一半的数字

LeetCode传送门

方法一：排序. Time-O(nlogn), Space-O(n)

1
2
def majority_element(nums):
    return sorted(nums)[len(nums)//2]

方法二：Counter Time-O(n), Space-O(n)

1
2
3
4
5
def majority_element(nums):
    from collections import Counter
    c = Counter(nums)
    # return max(c.keys(), key=c.get)
    return c.most_common(1)[0][0]
方法三：Boyer-Moore Voting Algorithm. 书中的算法说的就是这个，这详情请看波义尔摩尔投票。 
1
2
3
4
5
6
7
8
def majorityElement(self, nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

40.最小的k个数

相似题目，但是求最大的k个数LeetCode传送门

牛客网传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def GetLeastNumbers_Solution(self, tinput, k):
    # write code here
    l, r = 0, len(tinput)-1
    if k > len(tinput) or k < 1: return [] # for passing the damn testcase
    while True:
        pos = self.partition(tinput, l, r)
        if pos < k-1:
            l = pos + 1
        elif pos > k-1:
            r = pos - 1
        else:
            return sorted(tinput[:pos+1])  # sorted for passing the damn testcase
    
def partition(self, nums, l, r):
    from random import randint
    p = randint(l, r)
    nums[r], nums[p] = nums[p], nums[r]
    for i, v in enumerate(nums[l:r+1], l):
        if nums[i] <= nums[r]:
            nums[l], nums[i] = nums[i], nums[l]
            l += 1
    return l-1  # the pivot index

使用堆，不改变原数组

1
2
3
4
5
6
7
8
9
def GetLeastNumbers_Solution(self, tinput, k):
    import heapq as hq
    if k > len(tinput) or k <= 0: return []
    heap = [-x for x in tinput[:k]]
    hq.heapify(heap)
    for num in tinput[k:]:
        if -heap[0] > num:
            hq.heapreplace(heap, -num)
    return sorted(-x for x in heap)

41.数据流中的中位数

LeetCode传送门

思路：使用两个堆，最大堆存储较小的数据，最小堆存储较大的数据。添加数字时，先添加到最大堆，然后最大堆返回一个最大的数字给最小堆，最后为了平衡，可能需要最小堆还给最大堆一个最小值，以保证最大堆的长度>=最小堆的长度。由于headpq是最小堆，所以使用取反实现最大堆。添加数字：Time-O(logn)，取出中位数：Time-O(1)。

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
Adding number 41
MaxHeap lo: [41]           // MaxHeap stores the largest value at the top (index 0)
MinHeap hi: []             // MinHeap stores the smallest value at the top (index 0)
Median is 41
=======================
Adding number 35
MaxHeap lo: [35]
MinHeap hi: [41]
Median is 38
=======================
Adding number 62
MaxHeap lo: [41, 35]
MinHeap hi: [62]
Median is 41
=======================
Adding number 4
MaxHeap lo: [35, 4]
MinHeap hi: [41, 62]
Median is 38
=======================
Adding number 97
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97]
Median is 41
=======================
Adding number 108
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97, 108]
Median is 51.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq as hq

class MedianFinder:

    def __init__(self):
        self.lo, self.hi = [], []  # lo is max_heap, hi is min_heap
        
    def addNum(self, num):
        hq.heappush(self.lo, -num)
        hq.heappush(self.hi, -hq.heappop(self.lo))
        
        if len(self.lo) < len(self.hi):
            hq.heappush(self.lo, -hq.heappop(self.hi))       

    def findMedian(self):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0]+self.hi[0]) / 2.0
        else:
            return float(-self.lo[0])

42.连续子数组的最大和

LeetCode传送门

方法一：书中的思想。

1
2
3
4
5
6
def maxSubArray(self, nums):
    cp_nums = nums[:]
    for i in range(1, len(nums)):
        if cp_nums[i-1] > 0:
            cp_nums[i] += cp_nums[i-1]
    return max(cp_nums)

方法二：one-liner。注意accumulate是把函数放到后面的。

1
2
3
def maxSubArray(self, nums):
    from itertools import accumulate
    return max(accumulate(nums, lambda x, y: x+y if x > 0 else y))

43.1~n整数中1出现的次数

LeetCode传送门

1
2
3
4
5
6
7
def countDigitOne(self, n):    
    countr, i = 0, 1
    while i <= n:
        divider = i * 10
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr

分三种情况讨论比较清晰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countDigitOne(self, n: int) -> int:
    # xyz b abc
    # (1) xyz * 1000                     if d == 0
    # (2) xyz * 1000 + abc + 1           if d == 1
    # (3) xyz * 1000 + 1000              if d > 1
    q, ans, f = n, 0, 1
    while q > 0:
        q, cur = divmod(q, 10)
        ans += q * f
        if cur == 1:
            ans += n % f + 1
        elif cur > 1:
            ans += f
        f *= 10
    return ans

45.把数组排成最小的数字

AcWing传送门

python2的写法。

1
2
3
def PrintMinNumber(self, numbers):
    return ''.join(sorted(map(str, numbers), 
                          lambda x, y: cmp(x+y, y+x)))

匿名函数作为sort的参数，在python2中有这个参数。

cmp specifies a custom comparison function of two arguments (iterable elements) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None.

作为sort的参数，cmp提供了一个自定义的比较两个元素的方法，如果返回-1表示前者小于后者。python3中取消了这个参数，但是提供了一种key的转换。而内置函数可以通过运算符实现。

1
cmp(a, b)

等同于

1
(a>b) - (a<b)

所以python3的写法如下：

1
2
3
4
5
6
from functools import cmp_to_key
def PrintMinNumber(self, numbers):
    # write code here
    nums = list(map(str, numbers))
    nums.sort(key=cmp_to_key(lambda x, y: ((x+y)>(y+x)) - ((y+x)>(x+y))))
    return ''.join(nums)

46 把数字翻译成字符串

LeetCode传送门

1
2
3
4
5
6
7
8
9
def numDecodings(self, s: str) -> int:
    # w tells the number of ways
    # v tells the previous number of ways
    # d is the current digit
    # p is the previous digit
    v, w, p = 0, int(s>''), ''
    for d in s:
        v, w, p = w, int(d>'0')*w + (9<int(p+d)<27)*v, d
    return w

47 礼物的最大价值

LeetCode传送门。相似题目，求的是最小。

Acwing传送门这个是原题。

对首行使用初始化，然后消除了i的判断。

1
2
3
4
5
6
7
8
9
10
def get_max_value(g: 'List[List[int]]') -> int:
    R, C = len(g), len(g[0])
    cur = list(itertools.accumulate(g[0]))
    for i in range(1, R):
        tmp = []
        for j in range(C):
            left = tmp[-1] if j > 0 else float('-inf')
            tmp.append(max(cur[j], left) + g[i][j])
        cur = tmp
    return cur[-1]

48.最长不含重复字符的子字符串

LeetCode传送门

方法二：找到重复值时，更新start的值，为什么使用max，因为start有可能大于dic[s[end]]+1，比如当s='abba'，end走到最后的时候，上一次start因为b做了更新变为了2。

1
2
3
4
5
6
7
8
9
def lengthOfLongestSubstring(self, s):
    ans = start = 0
    pos = {}    # last index of element
    for end, c in enumerate(s):
        if c in pos:
            start = max(start, pos[c]+1)
        pos[c] = end
        ans = max(ans, end-start+1)
    return ans

49.丑数

LeetCode传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthUglyNumber(self, n: int) -> int:
    q = [1]
    t2 = t3 = t5 = 0
    for _ in range(n-1):
        a2, a3, a5 = q[t2]*2, q[t3]*3, q[t5]*5
        to_add = min(a2, a3, a5)
        q.append(to_add)
        if a2 == to_add:
            t2 += 1
        if a3 == to_add:
            t3 += 1
        if a5 == to_add:
            t5 += 1
    return q[-1]

50.第一个只出现一次的字符

LeetCode传送门有一点小区别，LeetCode输出索引，书中输出值。

1
2
3
4
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.

Time-O(N), Space-O(N)。暂时没发现更快的算法了。

1
2
3
4
5
6
7
def firstUniqChar(self, s):
    from collections import Counter
    c = Counter(s)
    for i, ch in enumerate(s):
        if c[ch] == 1:
            return i
    return -1

51.数组中的逆序对

牛客网传送门

AcWing传送门

这里使用了双端队列感觉不太合适，因为还要显式地转成list，否则没法对剩余的left或right做切片。也试了将其改为stack，但是stack来回reverse又太麻烦。

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
def InversePairs(self, data):
    self.count = 0
    
    def merge(left, right):
        q = deque()
        l, r = len(left)-1, len(right)-1
        while l >= 0 and r >= 0:
            if left[l] > right[r]:
                self.count += r + 1
                q.appendleft(left[l])
                l -= 1
            else:
                q.appendleft(right[r])
                r -= 1
        # q.extendleft(left[l:-1:-1] or right[r:-1:-1])
        q = left[:l+1] + right[:r+1] + list(q)
        return q
        
    def merge_sort(ary):
        if len(ary) <= 1: return ary
        mid = len(ary) // 2
        left = merge_sort(ary[:mid])
        right = merge_sort(ary[mid:])
        return merge(left, right)
    
    merge_sort(data)
    return self.count % 1000000007

52.两个链表的第一个公共节点

LeetCode传送门

1
2
3
4
5
6
def getIntersectionNode(self, headA, headB):
    p1, p2 = headA, headB
    while p1 is not p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
    return p1

53.在排序数组中查找数字

相似题目，LeetCode是求出数字的索引，书中返回个数。

LeetCode传送门。相似题目，LeetCode要返回两个索引，书中求个数。

1
2
3
4
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

方法一：标准库写法。这里不需要target去整个nums中判断。

1
2
3
4
5
6
7
def searchRange(self, nums: List[int], target: int) -> List[int]:
    from bisect import bisect, bisect_left
    lo = bisect_left(nums, target)
    if target in nums[lo:lo+1]:
        return lo, bisect(nums, target)-1
    else:
        return -1, -1

方法二：自己实现。bisect_right的方式采用+1的形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def searchRange(self, nums: List[int], target: int) -> List[int]:

    def search(n):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= n:
                hi = mid
            else:
                lo = mid + 1
        return lo
    lo = search(target)
    if target in nums[lo:lo+1]:
        return lo, search(target+1)-1
    else:
        return -1, -1

53.0~n-1中缺失的数字

LeetCode传送门

相似题目，LeetCode是未排序，书中是已排序。所以可以利用排序的特性使时间复杂度小于O(n)。即找出第一个下标与值不相等的元素，再-1就是缺失的元素。

AcWing传送门

方法一：数学公式。

1
2
3
4
5
def missingNumber(self, nums):
    n = len(nums)
    expected_sum = n*(n+1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

方法二：XOR.

index 0 1 2
value 3 0 1 
1
2
3
4
5
def missingNumber(self, nums: 'List[int]') -> 'int':
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing

方法三：利用书中已排序的特性。

1
2
3
4
5
6
7
8
9
def missingNumber(self, nums: List[int]) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) >> 1
        if nums[mid] > mid:
            hi = mid
        else:
            lo = mid + 1
    return lo

53 数组中数值和下标相等的元素

AcWing传送门

1
2
3
4
5
6
7
8
9
10
11
def getNumberSameAsIndex(self, nums):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo + hi) >> 1
        if nums[mid] < mid:
            lo = mid + 1
        elif nums[mid] > mid:
            hi = mid - 1
        else:
            return mid
    return -1

54.二叉搜索树的第k大节点

AcWing传送门

注意：牛客网上是求第k小节点，这里被坑了一次，然后返回值居然要求返回节点对象，而不是节点值，这里的答案按书中返回。如果是牛客网上需要把节点添加到res中，然后return res[k-1]

1
2
3
4
5
6
7
8
9
10
11
12
def kth_largest(self, root: TreeNode, k: int) -> int:
    stack, ans = [], None
    while stack or root:
        while root:
            stack.append(root)
            root = root.right
        root = stack.pop()
        k -= 1
        ans = root
        root = root.left
        if k == 0:
            return ans

方法二：生成器写法，无比的清晰。

1
2
3
4
5
6
7
8
9
def kthLargest(self, root: TreeNode, k: int) -> int:

    def r_inorder(node):
        if node:
            yield from r_inorder(node.right)
            yield node.val
            yield from r_inorder(node.left)

    return next(islice(r_inorder(root), k-1, None))

55.二叉树的深度

LeetCode传送门

1
2
3
4
5
6
    3
   / \
  9  20
    /  \
   15   7
return 3

方法一：recursively

1
2
3
4
5
def max_depth(root):
    if not root:
        return 0
    # return max(max_depth(root.left), max_depth(root.right)) + 1
    return max(map(max_depth, (root.left, root.right))) + 1

方法二：iteratively. BFS with deque

1
2
3
4
5
6
7
8
9
10
def maxDepth(self, root: 'TreeNode') -> 'int':
    q = root and collections.deque([(root, 1)])
    d = 0
    while q:
        node, d = q.popleft()
        if node.right:
            q.append((node.right, d+1))
        if node.left:
            q.append((node.left, d+1))
    return d

55.1平衡二叉树

LeetCode传送门

方法一：递归+递归。

1
2
3
4
5
6
7
8
9
10
def isBalanced(self, root):
    if not root:
        return True
    return self.isBalanced(root.left) and self.isBalanced(root.right) and \
           abs(self.max_depth(root.left)-self.max_depth(root.right)) <= 1
    
def max_depth(self, root):
    if not root:
        return 0
    return max(self.max_depth(root.left), self.max_depth(root.right)) + 1

方法二：上诉两种方法中都包含了一些无意义的重复遍历。这里采用后序遍历，边遍历边判断，不会重复节点。受此思想启发，添加一种后序遍历二叉树的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isBalanced(self, root):
    stack, node, last = [], root, None
    depths = collections.defaultdict(int)
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack[-1]
            if not node.right or last == node.right:
                node = stack.pop()
                left, right  = depths[node.left], depths[node.right]
                if abs(left - right) > 1: 
                    return False
                depths[node] = 1 + max(left, right)
                last, node = node, None
            else:
                node = node.right
    return True

方法三：dfs. 算深度的时候判断左右是否深度超过1. 这里变量不能把self去掉，否则[1,2,2,3,3,null,null,4,4]会错误的返回True而不是False。也可以使用nonlocal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isBalanced(self, root: 'TreeNode') -> 'bool':
    self.balanced = True
    
    def dfs(node):
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        if abs(left-right) > 1 and self.balanced:
            self.balanced = False
        return max(left, right) + 1
    
    dfs(root)
    return self.balanced

56 数组中只出现一次的两个数字。

找出数组中两个唯一出现一次的元素，其余元素均出现两次。LeetCode传送门

1
2
Input:  [1,2,1,3,2,5]
Output: [3,5]

思想：将这两个元素分到两个组，由于这两个数不相等，所以亦或结果不为0，也就是说二进制中至少有一位1，记为第n位。我们以第n位是否为1，把数组分为两个子数组。

1
2
3
4
5
6
7
8
9
10
def singleNumbers(self, nums: List[int]) -> List[int]:

    def xor_total(ary):
        return reduce(xor, ary)

    total = xor_total(nums)
    mask = total & -total
    n1 = (num for num in nums if num&mask==0)
    n2 = (num for num in nums if num&mask!=0)
    return xor_total(n1), xor_total(n2)

56.1数组中出现一次的数字，其余元素出现三次。

LeetCode传送门

1
2
Input: [2,2,3,2]
Output: 3

方法一：找出单独元素每一位的值。如果把所有数字的二进制每一位加起来，如果某一位可以被3整除，则表示单独元素的该位为0，否则为1。以下使用count来表示每一位1的个数。假设count%3!=0为True，说明该元素i位为1，然后是用|=更新ans在第i个位置的值，这里也可以使用+=，但是效率稍慢。convert的作用是因为python中的int是个对象，且没有最大限制，不是在第32位使用1来表示负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def singleNumber(self, nums, n=3):
    ans = 0
    for i in range(32):
        count = 0
        for num in nums:
            if ((num >> i) & 1):
                count += 1
        ans |= ((count%n!=0) << i)
    return self.convert(ans)

def convert(self, x):
    if x >= 2**31:
        x -= 2**32
    return x

这里有个状态机的解法，不明觉厉，留坑。讨论1和讨论2

1
2
3
4
5
6
def singleNumber(self, nums):
    ones, twos = 0, 0;
    for i in range(len(nums)):
        ones = (ones ^ nums[i]) & ~twos
        twos = (twos ^ nums[i]) & ~ones
    return ones

57.和为s的数字

牛客网传送门

AcWing传送门

看牛客网上的描述，如果有多对数字和为s，要求返回乘积最小的一对。乍一看以为牛客网又乱改题，但是仔细一想，如果两个和为s的数，而且是在递增数组中很明显，边缘的数字乘积要小，例如8X8>1X15。所以还是和书中解法一样。

1
2
3
4
5
6
7
8
9
10
def FindNumbersWithSum(self, array, tsum):
    l, r = 0, len(array)-1
    while l < r:
        if array[l] + array[r] < tsum:
            l += 1
        elif array[l]+array[r] > tsum:
            r -= 1
        else:
            return array[l], array[r]
    return []

57_1 和为s的连续正数序列

牛客网传送门

AcWing传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findContinuousSequence(self, tsum):
    end = (tsum + 1) // 2
    lo, hi, cur_sum = 1, 2, 3
    ans = []
    while lo < end:
        if cur_sum < tsum:
            hi += 1
            cur_sum += hi
        else:
            if cur_sum == tsum:
                ans.append(list(range(lo, hi+1)))
            cur_sum -= lo
            lo += 1
    return ans

58.翻转字符串。

LeetCode传送门

1
2
Input: "the sky is blue",
Output: "blue is sky the".

方法一：如果面试官是一个Pythoner，那么就让你过了。

1
2
def reverse_words(s):
    return ' '.join(reversed(s.split()))

如果你的面试官是一个只写Java或者C，看见代码就不平衡了，凭啥可以写到一行，非要你实现reverse。

1
2
3
4
5
6
7
8
9
10
def reverseWords(self, s: str) -> str:

    def hp_reversed(s):
        s = list(s)
        for i in range(len(s)//2):
            # s[i], s[-i-1] = s[-i-1], s[i]
            s[i], s[~i] = s[~i], s[i]
        return ''.join(s)
    s = hp_reversed(s)
    return ' '.join(hp_reversed(word) for word in s.split())

实现split，hp_reverse，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def reverseWords(self, s: str) -> str:

    def hp_reversed(s):
        s = list(s)
        for i in range(len(s)//2):
            s[i], s[~i] = s[~i], s[i]
        return ''.join(s)

    s = hp_reversed(s)
    ans = word = ''
    for r, c in enumerate(s):
        if c != ' ':
            word += c
        if (c== ' ' or r==len(s)-1) and word:
            ans += hp_reversed(word) + ' '
            word = ''
    return ans[:-1]

58_1 左旋转字符串

牛客网传送门

AcWing传送门

切片，书中的方法个人觉得Python并不适用。

1
2
3
4
5
def LeftRotateString(self, s, n):
    if not s:
        return ''
    n = n % len(s)
    return s[n:] + s[:n]

59.滑动窗口的最大值。

LeetCode传送门

得益于python的切片。Time: O(n*k). k=n-size

1
2
3
def maxInWindows(self, nums, size):
    return [max(nums[i:i+size])
            for i in range(len(nums)-size+1) if size!=0 ]

方法二：队列保存索引。

1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    q = collections.deque()
    ans = []
    for i, d in enumerate(nums):
        while q and nums[q[-1]] < d:
            q.pop()
        q.append(i)
        if q[0] == i-k:
            q.popleft()
        if i >= k-1:
            ans.append(nums[q[0]])
    return ans

60.n个骰子的点数

AcWing传送门

1
[[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]

dp[0][j]==1表示第一个骰子和为j+1的次数为1，因为数组下标从0开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dice_probability(n, val=6):
    dp = [[0]*val*n for _ in range(n)]
    dp[0][:val] = [1] * val  # 初始化第一个骰子
    
    for i in range(n-1):  # 根据第i个骰子更新第i+1个骰子
        for j in range(i, len(dp[i+1])):
            # 第i+1个骰子和为j（实际为j+1，因为数组下标从0开始）的次数，等于第i个
            # 骰子j-1 ~ j-6次数的总和
            dp[i+1][j] = sum([dp[i][j-k] for k in range(1, val+1)])
            
    # 整理数据成为dict，key表示和，value表示出现的次数
    # count = {i+1: times for i, times in enumerate(dp[-1])}
    # 计算概率
    count = {i+1: round(float(times / (val**n)), 5)
             for i, times in enumerate(dp[-1]) if times!=0}
    return count

感觉用dict来表示更加明确，没有数组下标从0开始的混淆。按照AcWing中的返回写出一种解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import defaultdict
from itertools import repeat

def numberOfDice(self, n):
    last_p = defaultdict(int)
    last_p.update(dict(zip(range(1, 7), repeat(1))))
    for i in range(2, n+1):
        new_p = defaultdict(int)
        for j in range(i, i*6+1):
            new_p[j] = sum(last_p[j-k] for k in range(1, 7))
        # print(new_p)
        last_p = new_p
    return list(last_p.values())

61.扑克牌中的顺子

牛客网传送门

AcWing传送门

开始以为还要用个dict来映射值，后来发现直接传得卡牌的值。思想就是先排序，然后查joker的数量，看剩下牌的差值加起来能不能用已有的joker连起来。

1
2
3
4
5
6
7
8
9
10
11
def IsContinuous(self, numbers):
    if not numbers:
        return False
    joker_count = numbers.count(0)
    left_cards = sorted(numbers)[joker_count:]
    need_joker = 0
    for i in range(len(left_cards)-1):
        if left_cards[i+1] == left_cards[i]:
            return False
        need_joker += (left_cards[i+1]-left_cards[i]-1)
    return need_joker <= joker_count

只要没有重复的，并且最大的和最小的差<5就能组成顺子。

1
2
3
def isStraight(self, nums: List[int]) -> bool:
    cards = [x for x in nums if x!=0]
    return len(cards)==len(set(cards)) and max(cards)-min(cards)<5

62.圆圈中最后剩下的数字

AcWing传送门

方法一：其实不需要环形链表，使用一个list足矣，每次将其旋转rot位，一开始想将要把第m个数旋转到list首部，然后再pop(0)，后来想到直接可以通过切片取出来，节省了pop(0)的O(n)复杂度。

1
2
3
4
5
def lastRemaining(self, n: int, m: int) -> int:
    num = 0
    for i in range(2, n+1):
        num = (num + m) % i
    return num

方法二：书中的推导过程过于复杂，这里学到了一个稍微简单的推导过程。参考约瑟夫环问题。

解析Josephus-problem

1
2
3
4
5
6
7
def LastRemaining_Solution(self, n, m):
    if n<=0 or m<=0:
        return -1
    last_num = 0
    for i in range(2, n+1):
        last_num = (last_num+m) % i
    return last_num

63.股票的最大利润

LeetCode传送门

方法一：Brute Force.其实就是求最高峰点和前面最低谷点的差。

1
2
3
4
5
6
def maxProfit(self, prices: List[int]) -> int:
    profit, min_buy = 0, float('inf')
    for p in prices:
        min_buy = min(min_buy, p)
        profit = max(profit, p-min_buy)
    return profit

方法二：标准的卡登算法。此题为53.连续数组最大和的变形，如果价格比之前小，则舍弃，否则一起计算连续子数组的和。

1
2
3
4
5
6
7
def maxProfit(self, prices: List[int]) -> int:
    cur = sofar = 0
    for i in range(1, len(prices)):
        cur += prices[i] - prices[i-1]
        cur = max(0, cur)
        sofar = max(cur, sofar)
    return sofar

方法三：使用标准库的卡登算法。

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices: List[int]) -> int:
    from itertools import tee
    cur = profit = 0
    a, b = tee(prices)
    next(b, None)
    for before, today in zip(a, b):
        cur += today - before
        cur = max(0, cur)
        profit = max(profit, cur)
    return profit

64.求1+2+···+n

AcWing传送门

这题对python不是很友好，感觉and也属于条件判断语句。reduce`sum`之类的属于作弊行为，这里就不贴了。

1
2
3
def Sum_Solution(self, n):
    # write code here
    return n and (n+self.Sum_Solution(n-1))

65.不用加减乘除做加法

LeetCode传送门

此题由于Python中的int没有长度限制，在负数出现的情况，会导致结果与预期不同。详情见Python负数位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
def getSum(self, a, b):
    # 32 bits integer max
    MAX = 0x7FFFFFFF  # 2**31-1
    # 32 bits interger min  
    MIN = 0x80000000  # -2**31
    # mask to get last 32 bits
    mask = 0xFFFFFFFF  # 2*32-1
    while b != 0:
        # ^ get different bits and & gets double 1s, << moves carry
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    # if a is negative, get a's 32 bits complement positive first
    # then get 32-bit positive's Python complement negative
    return a if a <= MAX else ~(a ^ mask)

或者可以将其转成32位整数。

1
2
3
4
5
6
7
import numpy as np

class Solution(object):
    def getSum(self, a, b):
        while b != 0:
            a, b = np.int32(a ^ b), np.int32((a & b) << 1)
        return int(a)

66 构建乘积数组

LeetCode传送门

思路：不能使用除法。如书中所说，以i为分割点，将B拆成C，D两部分，左边是A[0] x A[1] x...x A[i-1]右边则为A[i+1] x ...x A[n-1] ，C[i] = C[i-1] * A[i-1]

方法一：这里生成器没法直接使用reversed，否则能达到O(1)的空间复杂度。

1
2
3
4
5
6
def constructArr(self, a: List[int]) -> List[int]:
    right = list(accumulate([1]+a, mul))        
    left = list(accumulate([1]+a[::-1], mul))[::-1]
    # right:      1  , 1 , 2 ,  6, 24, 120
    # left:  120, 120, 60, 20,  5,  1
    return [a*b for a, b in zip(right, left[1:])]

方法二：

不使用标准库的方法。

1
2
3
4
5
6
7
8
9
def multiply(self, A):
    C = [1] # 第一个元素相当于没有
    for i in range(len(A)-1):
        C.append(C[-1] * A[i])
    D = [1]
    for j in range(len(A)-1, 0, -1):
        D.append(D[-1] * A[j])
    D.reverse()
    return [C[i] * D[i] for i in range(len(A))]

方法三：O(n)时间，O(1)空间。