剑指Offer

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)空间。