这篇文章用于记录《剑指Offer》刷题的总结，对不同类型题目分类，对题目会进行多个方法解题，并分析方法的难度（以星号表示）、时间复杂度等。刷题使用的是Leetcode，部分代码来源于讨论区：https://leetcode-cn.com/problemset/lcof/
数据结构
链表
03 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：2 <= n <= 100000
哈希表法O(n) ☆☆☆
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
dic = {}
for i in nums:
if i in dic:
return i
else:
dic[i] = 0
排序法O(nlogn) ☆
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
'''
排序后出现连续的数字便为重复。
'''
nums.sort()
pre = nums[0]
for i in range(1, len(nums)):
if nums[i]==pre:
return nums[i]
else:
pre = nums[i]
观察题意法O(n) ☆☆☆☆☆
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
'''
由题意可知，一个无重复且范围都在0~n-1的数组应该排序后对应位置就是对应的值，
一个个去比对然后对换能直接排好序，但其中若出现冲突说明重复。
'''
for i in range(len(nums)):
while nums[i] != i:
if nums[nums[i]] == nums[i]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
return none
06 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
输入：head = [1,3,2]
输出：[2,3,1]
栈O(n) ☆☆☆
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
lis = []
while head:
lis.append(head.val)
head = head.next
return lis[::-1]
递归法O(n) ☆☆☆☆
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
lis = []
if head and head.next:
lis = self.reversePrint(head.next)
if head:
lis.append(head.val)
return lis
18 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
双指针法O(n) ☆☆☆
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return head
if head.val == val:
return head.next
node = head
# 虽然只是单指针，思路仍然是双指针
while node:
if node.next and node.next.val == val:
node.next = node.next.next
return head
node = node.next
return head
递归法O(n) ☆☆☆☆
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return head
if head.val == val:
return head.next
head.next = self.deleteNode(head.next, val)
return head
22 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
给定一个链表：1->2->3->4->5, 和 k = 2
返回链表： 4->5
递归回溯法O(n) ☆☆☆
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if head:
level = self.getKthFromEnd(head.next, k)
if type(level) == int:
level += 1
else:
return level
return head if level == k else level
else:
return 0
双指针法O(n) ☆☆
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
'''
former指针总比latter指针多k格，那么遍历到最后latter就是n-k
'''
former,latter = head,head
for i in range(k-1):
former = former.next
while former.next:
former = former.next
latter = latter.next
return latter
存储法O(n) ☆☆☆☆
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
'''
在三个方法里面算是最快
'''
stack = list()
while head:
stack.append(head)
head = head.next
return stack[-k]
其中二次遍历法太简单，有点像暴力法就不详细讲了。
24 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：0 <= 节点个数 <= 5000
双指针法O(n) ☆☆☆
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
'''
只需要一次遍历，保存一个换了方向的指针。
'''
last = None
while head:
head.next, last, head = last, head, head.next
return last
递归法O(n) ☆☆☆☆☆
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 尾节点保存
if not head or not head.next:
return head
# end只用于保留最后一个节点用于返回
end = self.reverseList(head.next)
# 关键在head.next.next=head，让A->B转换为B->A
head.next.next = head
head.next = None
return end
25 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：0 <= 节点个数 <= 5000
双指针法O(m+n) ☆☆
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = l = ListNode(-1)
while l1 and l2:
if l1.val > l2.val:
l2, l.next = l2.next, l2
else:
l1, l.next = l1.next, l1
l = l.next
l.next = l1 if l1 else l2
return head.next
递归法O(m+n) ☆☆☆☆☆
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
(l1, l2) = (l2, l1) if l2.val < l1.val else (l1, l2)
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
35 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
可以用一行代码解决（深复制原理，但没必要）
copy.deepcopy(head)
哈希法O(n) ☆☆☆
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
# 以对象作键保存哈希表
visited = {}
def dfs(head):
if not head: return None
if head in visited:
return visited[head]
copy = Node(head.val)
visited[head] = copy
copy.next = dfs(head.next)
copy.random = dfs(head.random)
return copy
return dfs(head)
原地修改法O(n) ☆☆☆☆☆(推荐，节省空间)
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return head
# 首先1->2->3转变为1->1'->2->2'->3->3'
node = head
while node:
copy = Node(node.val)
copy.next = node.next
node.next = copy
node = node.next.next
# 再给复制节点添加random
node = head
while node:
if node.random:
node.next.random = node.random.next
node = node.next.next
# 取消相同的链接，分为1->2->3与1'->2'->3'
newHead,node = head.next,head
while node and node.next:
tmp = node.next
node.next = tmp.next
node = tmp
return newHead
52 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
哈希法O(n²) ☆
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
lis = [None]
while headA or headB:
if headA:
if headA in lis:
return headA
lis.append(headA)
headA = headA.next
if headB:
if headB in lis:
return headB
lis.append(headB)
headB = headB.next
return None
双指针法O(m+n+c) ☆☆☆☆☆
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 这个方法非常巧妙:
# 一个链表遍历完了开始遍历另一个链表，那么最多遍历两个链表的和的量，此时为无公共节点情况；
# 而如果有公共节点就会在公共节点停止遍历，因为两人都遍历了双方不共通的部分与一次共通的部分。
nodeA, nodeB = headA, headB
while nodeA != nodeB:
nodeA = nodeA.next if nodeA else headB
nodeB = nodeB.next if nodeB else headA
return nodeB
栈与队列
09 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
输入：
函数：[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
参数：[[],[3],[],[]]输出：[null,null,3,-1]
class CQueue:
def __init__(self):
self.stack1 = [] # 用于入栈
self.stack2 = [] # 用于出队
def appendTail(self, value: int) -> None:
self.stack1.append(value)
def deleteHead(self) -> int:
if self.stack2:
return self.stack2.pop()
elif self.stack1:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
else:
return -1
30 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
输入：
函数：[“MinStack”,”push”,”push”,”push”,”min”,”top”,”pop”,”min”]
参数：[[],[-2],[0],[-1],[],[],[],[]]输出：[null,null,null,null,-2,-1,null,-2]
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack1 = [] # 用于正常装栈
self.stack2 = [] # 用于获得min值
def push(self, x: int) -> None:
self.stack1.append(x)
# 关键在此，stack2装载的是递减的数据，最后进去的一定为最小值
if not self.stack2 or x <= self.stack2[-1]:
self.stack2.append(x)
def pop(self) -> None:
tmp = self.stack1.pop()
if self.stack2 and self.stack2[-1] == tmp:
self.stack2.pop()
def top(self) -> int:
return self.stack1[-1] if self.stack1 else None
def min(self) -> int:
return self.stack2[-1] if self.stack2 else None
31 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
模拟法O(n) ☆☆☆☆
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
j = 0
for x in pushed:
stack.append(x)
while stack and stack[-1] == popped[j]:
stack.pop()
j += 1
return not stack
58-1 翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理，并去除多余空格。例如输入字符串”I am a student. “，则输出”student. a am I”。
钻空子 ☆
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])
常规做法 ☆☆
class Solution:
def reverseWords(self, s: str) -> str:
stack = []
string,tmp = "",""
for i in s[::-1]:
if i != " ":
tmp = i+tmp
else:
if tmp:
string += tmp+" "
tmp = ""
return (string + tmp).strip()
59-1 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
单调队列法 O(n) ☆☆☆☆(这里用的递增，也可以用递减做)
class Solution:
def maxSlidingWindow(nums, k: int):
if not nums or k == 0:
return []
aux, res = [nums[0]], []
# 初始化窗口
for i in range(1, k):
if aux[-1] <= nums[i]:
aux.append(nums[i])
res.append(aux[-1])
# 窗口移动
for i in range(1, len(nums) - k + 1):
if nums[i - 1] == aux[0]:
aux.pop(0)
if aux: # 判定窗口是否加入新元素
if aux[-1] <= nums[i + k - 1]:
aux.append(nums[i + k - 1])
else: # 窗口为空，重新入窗
aux.append(nums[i])
for j in range(i+1, i + k):
if aux[-1] <= nums[j]:
aux.append(nums[j])
res.append(aux[-1])
return res
妙法O(n) ☆☆☆☆☆
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if n * k == 0:
return []
if k == 1:
return nums
# 初始化左右数组
# left[i]：按分块从左到i最大值
# right[j]：按分块从右到j最大值
# 分块：将原数组分为k份
# 那么res[i] = max(right[i],left[i+k-1])
left = [0] * n
left[0] = nums[0]
right = [0] * n
right[-1] = nums[-1]
# 获取左右数组
for i in range(1,n):
if i % k == 0:
left[i] = nums[i]
else:
left[i] = max(nums[i] , left[i-1])
j = n - i -1
if (j+1) % k == 0:
right[j] = nums[j]
else:
right[j] = max(nums[j],right[j+1])
res = []
for i in range(n-k+1):
res.append(max(left[i+k-1],right[i]))
return res
树
07 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
递归法 ☆☆☆
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:1+i], inorder[:i])
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
递归法改良 ☆☆☆☆☆
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
self.dic, self.po = {}, preorder
for i in range(len(inorder)):
self.dic[inorder[i]] = i # 用字典保存index方便查找
return self.recur(0, 0, len(inorder) - 1)
def recur(self, pre_root, in_left, in_right):
if in_left > in_right: return # 终止条件：中序遍历为空
root = TreeNode(self.po[pre_root]) # 建立当前子树的根节点
i = self.dic[self.po[pre_root]] # 搜索根节点在中序遍历中的索引，从而可对根节点、左子树、右子树完成划分。
root.left = self.recur(pre_root + 1, in_left, i - 1) # 开启左子树的下层递归
root.right = self.recur(i - in_left + pre_root + 1, i + 1, in_right) # 开启右子树的下层递归
return root # 返回根节点，作为上层递归的左（右）子节点
迭代法 ☆☆☆☆
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
length = len(preorder)
stack = []
stack.append(root)
index = 0
for i in range(1, length):
preorderval = preorder[i]
node = stack[-1]
if node.val != inorder[index]: # 每次比较栈顶元素和inorder[index]
node.left = TreeNode(preorderval)
stack.append(node.left)
else:
while stack and stack[-1].val == inorder[index]:# 栈顶元素等于inorder[index],弹出；并且index += 1
node = stack[-1]
stack.pop()
index += 1
node.right = TreeNode(preorderval)
stack.append(node.right)
return root
26 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
递归 ☆☆☆☆
class Solution:
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 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
[4,2,7,1,3,6,9]
镜像输出：
[4,7,2,9,6,3,1]
递归O(n) ☆☆☆☆
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
node = root
if node:
node.left, node.right = node.right, node.left
self.mirrorTree(node.left)
self.mirrorTree(node.right)
return root
辅助栈O(n) ☆☆☆
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if root:
stack = [root]
while stack:
node = stack.pop()
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
node.left, node.right = node.right, node.left
return root
28 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。
输入：root = [1,2,2,3,4,4,3]
输出：true
规律法 ☆☆☆☆☆
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def recur(L, R):
if not L and not R: return True
if not L or not R or L.val != R.val: return False
return recur(L.left, R.right) and recur(L.right, R.left)
return recur(root.left, root.right) if root else True
32-1 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
BFSO(n) ☆☆
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque() # 用Deque可以快速popleft
queue.append(root)
while queue:
node = queue.popleft()
res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
32-2 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
BFSO(n) ☆☆☆
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(tmp)
return res
BFS递归O(n) ☆☆☆☆
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
res = []
def helper(root, level):
if not root:
return
if level == len(res):
res.append([])
res[level].append(root.val)
helper(root.left, level + 1)
helper(root.right, level + 1)
helper(root, 0)
return res
32-3 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
BFSO(n) ☆☆☆
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
k = 0
while queue:
tmp = []
for _ in range(0,len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
k += 1
res.append(tmp if k%2 else tmp[::-1]) # 就是比上面多了这么点
return res
34 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
给定如下二叉树，以及目标和 sum = 22，返回：[ [5,4,11,2], [5,8,4,5] ]
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
回溯法
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def recur(root, tar):
if not root: return
path.append(root.val)
tar -= root.val
if tar == 0 and not root.left and not root.right:
res.append(list(path))
recur(root.left, tar)
recur(root.right, tar)
path.pop()
recur(root, sum)
return res
37 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
class Codec:
def serialize(self, root):
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if node:
res.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
res.append(None)
print(res)
return res
def deserialize(self, data):
if not data: return
vals, i = data, 1
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if vals[i] is not None:
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] is not None:
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
54 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
DFS逆向中序遍历O(n) ☆☆☆☆
# 因为BST中序遍历一定为递增序列，逆向中序遍历则为递减
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
if not root:
return
dfs(root.right) # 右
if self.k == 0: # 若已找到便停止深入寻找
return
self.k -= 1 # 中
if self.k == 0:
self.res = root.val
dfs(root.left) # 左
self.k = k
dfs(root)
return self.res
还有更秀的写法 ☆☆☆
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
return dfs(root.left) + [root.val] + dfs(root.right) if root else []
return dfs(root)[-k]
55-1 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
DFSO(n) ☆☆☆☆
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root:
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1 # 优雅
return 0
BFSO(n) ☆☆☆
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
queue, level = [root], 0
while queue:
tmp = []
for node in queue:
if node.left: tmp.append(node.left)
if node.right: tmp.append(node.right)
queue = tmp
level += 1
return level
55-2 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
先序遍历+深度O(nlogn) ☆☆
class Solution:
def getDepth(self,node):
if node:
return max(self.getDepth(node.left),self.getDepth(node.right))+1
return 0
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
if self.isBalanced(root.left) and self.isBalanced(root.right): # 子树是否平衡
return abs(self.getDepth(root.left) - self.getDepth(root.right)) <= 1 # 自己是否平衡
return False
后序遍历 + 剪枝O(n) ☆☆☆☆
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def recur(root):
if not root:
return 0
left = recur(root.left) # 左
if left == -1:
return -1
right = recur(root.right) # 右
if right == -1:
return -1
return max(left, right) + 1 if abs(left - right) <= 1 else -1 # 若不平衡直接剪枝
return recur(root) != -1
68-1 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
分析：本题是一定存在最近祖先节点的，由于是二叉搜索树，只要p与q分别在当前节点异侧（或自身是其中一个节点），当前节点就一定是最近公共祖先。若他俩在同一侧，便深入到那一侧节点去继续搜。
递归法O(n) ☆☆☆
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root
迭代法O(n) ☆☆☆
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else: break
return root
68-2 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
积分法O(n) ☆☆
class Solution:
def __init__(self):
self.res = None
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
def helper(node):
count = 0
if not node:
return 0
if node.val == p.val or node.val ==q.val:
count = 1 + helper(node.left) + helper(node.right) # 每遇到一次p/q加一分
else:
count = helper(node.left) + helper(node.right)
if count == 2:
self.res = node # 一旦积够两分，当前点就是最近公共祖先
count = -1
return count
helper(root)
return self.res
递归法O(n) ☆☆☆☆☆
class Solution:
# 很优雅的递归
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left: return right
if not right: return left
return root
算法
查找
04 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
这题时间复杂度量级上区别不会太大，关键在于看从哪个角开始遍历，及时换行列就完事了。
规律法 ☆☆☆
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 从左下角遍历最快
i, j = len(matrix) - 1, 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] > target: i -= 1
elif matrix[i][j] < target: j += 1
else: return True
return False
直接暴力 ☆☆
class Solution:
def findNumberIn2DArray(self, matrix, target: int) -> bool:
for i in matrix:
if target in i:
return True
return False
二分搜索 ☆（这题并不必要）
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
if n == 0:
return False
else:
m = len(matrix[0])
left, right = 0, m-1
for i in range(n):
while left <= right:
mid = (left+right+1)//2
if matrix[i][mid] > target:
right = mid-1
elif matrix[i][mid] == target:
return True
else:
left = mid+1
left = 0
return False
11 旋转数组的最小数字
二分查找 O(logn) ☆☆☆☆
class Solution:
def minArray(self, numbers: List[int]) -> int:
l,r = 0, len(numbers)-1
while l!=r:
m = (l+r)//2
if numbers[m]>numbers[r]:
l = m+1 # 最小点在右半部分[m+1, r]
elif numbers[m]<numbers[r]:
r = m # 最小点在左半部分[l,m]
else:
r -= 1 # 相同时无法判断在哪，遂缩小范围，但不能缩l，因为m可能为l但不为r
return numbers[l]
39 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
哈希 O(n) ☆☆
class Solution:
def majorityElement(self, nums: List[int]) -> int:
length = len(nums)//2
dic = {}
for i in nums:
if i not in dic:
dic[i] = 0
if dic[i] == length:
return i
dic[i] += 1
摩尔投票法 O(n) ☆☆☆☆
class Solution:
def majorityElement(self, nums: List[int]) -> int:
votes = 0
for num in nums:
if votes == 0: x = num
votes += 1 if num == x else -1
return x
50 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
s = “abaccdeff”
返回 “b”
哈希O(n) ☆☆☆
class Solution:
def firstUniqChar(self, s: str) -> str:
dic = {}
for c in s:
dic[c] = not c in dic
for c in s:
if dic[c]: return c
return ' '
有序哈希O(n) ☆☆☆☆
class Solution:
def firstUniqChar(self, s: str) -> str:
# python3.6后，字典默认有序，否则需用OrderedDict()
dic = {}
for c in s:
dic[c] = not c in dic
for k, v in dic.items():
if v: return k
return ' '
53-1 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
二分查找 O(logn) ☆☆
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r,length = 0,len(nums)-1,len(nums)-1
while l<=r:
m = (l+r)//2 # 二分找到target点
if nums[m]<target:
l=m+1
elif nums[m]>target:
r=m-1
elif nums[m] == target:
l = m-1
while l>=0 and nums[l]==target: # target往左找左边界
l-=1
r = m +1
while r<=length and nums[r]==target: # target往右找右边界
r+=1
break
return r-l-1 if l<r else 0 # 避免找不到的情况
二分查找·改 O(logn) ☆☆☆☆
class Solution:
def search(self, nums: [int], target: int) -> int:
def helper(tar):
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] <= tar: i = m + 1 # 修改条件，直接找右边界
else: j = m - 1
return i
return helper(target) - helper(target - 1) # 两次二分完成
53-2 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
二分查找O(logn) ☆☆
class Solution:
def missingNumber(self, nums: List[int]) -> int:
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] == m: # 想到这个条件就完事了
i = m + 1
else:
j = m - 1
return i
排序
21 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
双指针法 O(n)
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
i,j = 0, len(nums)-1
while i<j: # 操作十分像快速排序
while i < j and nums[i] & 1 == 1: i += 1
while i < j and nums[j] & 1 == 0: j -= 1
nums[i], nums[j] = nums[j], nums[i]
return nums
40 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
大可以sort()了之后选前几个切片，但是没必要。
左半快排 O(n) ☆☆☆☆
class Solution:
def partition(self, nums, l, r):
pivot = nums[r]
i = l - 1
for j in range(l, r):
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[r] = nums[r], nums[i + 1]
return i + 1
def randomized_partition(self, nums, l, r):
i = random.randint(l, r)
nums[r], nums[i] = nums[i], nums[r]
return self.partition(nums, l, r)
def randomized_selected(self, arr, l, r, k):
pos = self.randomized_partition(arr, l, r)
num = pos - l + 1
if k < num:
self.randomized_selected(arr, l, pos - 1, k)
elif k > num:
self.randomized_selected(arr, pos + 1, r, k - num)
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0:
return list()
self.randomized_selected(arr, 0, len(arr) - 1, k)
return arr[:k]
哈希/计数排序 O(M) 对本题是最快的，但有局限性（因为范围给定了，不大且是整数）
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
nums = [0] * 10000
res,idx = [],0
for i in arr:
nums[i] += 1
while k > 0:
if nums[idx]:
nums[idx] -= 1
res.append(idx)
k -= 1
else:
idx += 1
return res
堆排序 O(nlogn) ☆☆☆☆☆
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0:
return list()
# Python中默认堆为小根堆，需要加上负号作为大根堆使用
hp = [-x for x in arr[:k]]
heapq.heapify(hp)
for i in range(k, len(arr)):
if -hp[0] > arr[i]:
heapq.heappop(hp)
heapq.heappush(hp, -arr[i])
res = [-x for x in hp]
return res
45 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
找规律 O(nlogn) ☆☆☆☆
class Solution:
def minNumber(self, nums: List[int]) -> str:
def sort_rule(x, y):
a, b = x + y, y + x
if a > b: return 1
elif a < b: return -1
else: return 0
strs = [str(num) for num in nums]
strs.sort(key = functools.cmp_to_key(sort_rule))
return ''.join(strs)
57 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
双指针 O(n) ☆☆☆
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
l,r = 0,len(nums)-1
s = nums[l]+nums[r]
while s!=target and l<r:
if s>target:
r-=1
else:
l+=1
s = nums[l]+nums[r]
return [nums[l],nums[r]]
回溯
12 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
DFS O(3ᵏMN) ☆☆☆
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
row,col,length = len(board)-1,len(board[0])-1,len(word)-1
def dfs(x,y,k):
if x<0 or x>row or y<0 or y>col or board[x][y] != word[k]:
return False
if not k-length:
return True
board[x][y] = 0 # 标记
if dfs(x,y+1,k+1) or dfs(x+1,y,k+1) or dfs(x-1,y,k+1) or dfs(x,y-1,k+1):
return True
else:
board[x][y] = word[k] # 还原
return False
for i in range(row+1):
for j in range(col+1):
if dfs(i,j,0):
return True
return False
13 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
这题的两个重点：
- 判断其不需要左和上的移动便可以遍历全部
- 数位和小于k的判断：s_x + 1 if (x + 1) % 10 else s_x - 8
DFS O(MN) ☆☆☆☆☆
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def dfs(i, j, si, sj):
if i >= m or j >= n or k < si + sj or (i, j) in visited: return 0
visited.add((i,j))
return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)
visited = set()
return dfs(0, 0, 0, 0)
BFS O(MN) ☆☆☆☆
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
queue, visited, = [(0, 0, 0, 0)], set()
while queue:
i, j, si, sj = queue.pop(0)
if i >= m or j >= n or k < si + sj or (i, j) in visited: continue
visited.add((i,j))
queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
return len(visited)
38 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
DFS O(n!) ☆☆☆☆
class Solution:
def permutation(self, s: str) -> List[str]:
res,queue = [],collections.deque(s)
def dfs(lis, string):
if len(lis)==1 : # 访问到最后一个字符，直接添加到答案
res.append(string+lis[0])
return
count = 0
visited = set() # 保存当前字符出现过的字符
while count < len(lis): # 每个字符都访问过了就结束
count+=1 # 用计数来循环是为了方便直接popleft，取剩余的queue继续使用
tmp = queue.popleft() # 每次取第一个进行函数，剩下的为后续可能的字符
if tmp not in visited: # 在第N个字符出现过同样的字符，则直接剪枝
dfs(queue,string+tmp)
visited.add(tmp)
queue.append(tmp) # 将取出的字符还回去
dfs(queue, "")
return res
位运算
15 二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
输入：00000000000000000000000000001011
输出：3
移位 O(n) ☆☆☆
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
if n & 1:
res +=1
n>>=1
return res
消1法 O(m) ☆☆☆☆☆
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += 1
n &= n - 1 # 最右侧的1替换为0
return res
16 数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
快速幂 O(logn) ☆☆☆☆☆
将指数n转换成n=1+2+4+…+2ᵐ-1，二进制处理，再利用指数相加即幂相乘得到快速幂。
如 7->111，则有 x⁷ = x¹ · x² · x⁴，10->1010，则有x¹⁰ = x¹ · x² · x⁴ · x⁸
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0: return 0
res = 1
if n < 0: x, n = 1 / x, -n
while n:
if n & 1: res *= x # 有余对应二进制位为1，即此要参与相乘
x *= x # 为下一位的相乘做准备
n >>= 1 # n//2
return res
56-1 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分组异或 O(n) ☆☆☆☆☆
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = functools.reduce(lambda x,y:x ^ y, nums)
d = 1
while d & ret == 0:
d <<= 1
a, b = 0, 0
for i in nums:
if i & d:
a ^= i
else:
b ^= i
return [a, b]
56-2 数组中数字出现的次数 II
一个整型数组 nums 里除一个数字之外，其他数字都出现了三次。请写程序找出这个只出现一次的数字。
64 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
钻空子 (没必要)
class Solution:
def sumNums(self, n: int) -> int:
return sum(range(1,n+1))
递归法O(n) ☆☆☆
class Solution:
def sumNums(self, n: int) -> int:
return n and (n+self.sumNums(n-1)) # python返回特性，多个True返回最后一个值
65 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
钻空子 （没必要）
class Solution:
def add(self, a: int, b: int) -> int:
return sum([a,b])
动态规划
10-1 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。答案需要取模 1e9+7。(0<=n<=100)
可以用打表法做，但是没必要。
定义法/动态规划O(n) ☆☆☆☆☆
class Solution:
def fib(self, n: int) -> int:
if n==1:
return 1
f1,f2 = 0,1
while n-1 > 0:
ans = f1 + f2
ans -= 0 if ans < 1e9+7 else 1e9+7 # 由于范围小可以直接减省去了求余运算
ans = int(ans)
f1 = f2
f2 = ans
n-=1
return f2
递归法O(n) ☆☆☆(其实就是递归写动态规划，也可以加记忆化)
class Solution:
@lru_cache(None) # 用于定义递归的深度为无限
def fib(self, n: int) -> int:
if n<2:
return n
return (self.fib(n-1)+self.fib(n-2))%1000000007
10-2 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7。(0<=n<=100)
由于此题一样是有$f(n)=f(n-1)+f(n-2)$，上述的动态规划法基本改改初始值搬下来就能用就不重复写了。
递归法O(n) ☆☆☆
class Solution:
@lru_cache(None) # 用于定义递归的深度为无限
def numWays(self, n: int) -> int:
if n <= 1:
return 1
if n == 2:
return 2
return int((self.numWays(n-1) + self.numWays(n-2))% (1e9+7))
记忆化递归法O(n) ☆☆☆☆
class Solution:
@lru_cache(None) # 用于定义递归的深度为无限
def numWays(self, n: int) -> int:
f = [1, 1, 2] + [0] * 98
def dp(n: int):
if f[n]:
return f[n]
f[n] = dp(n-1) + dp(n-2)
f[n] -= 0 if f[n] < (1e9+7) else (1e9+7)
return int(f[n])
return dp(n)
19 正则表达式匹配
请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。
回溯法 $O((n+m)*2^\frac{n+m}{2})$ ☆☆☆☆
- 当主串与*匹配0次时，删除包括该*前的匹配串
- 当主串需要与*匹配多次时，减一次
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p: return not s
first_match = bool(s and (p[0] == s[0] or p[0] == '.')) # 第一个字母是否匹配
# 如果 p 第二个字母是 *
if len(p) >= 2 and p[1] == "*":
# *号效果0次 or *号效果大于0次，让主串减去一次让主串
return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
else:
return first_match and self.isMatch(s[1:], p[1:])
动态规划 O(mn) ☆☆☆☆☆
$d p(i)(j)=\left{\begin{array}{ll}
d p(i-1)(j-1), & \mathrm{s}(\mathrm{i})=\mathrm{p}(\mathrm{j}) \text { or } \mathrm{p}(\mathrm{j})= “.”\
d p(i)(j-2), & \mathrm{p}(\mathrm{j})=, \mathrm{p}(\mathrm{j}-1) !=\mathrm{s}(\mathrm{i}) \
d p(i-1)(j) \operatorname {or} dp(i)(j-2), & \mathrm{p}(\mathrm{j})=, \mathrm{p}(\mathrm{j}-1)=\mathrm{s}(\mathrm{i}) \text { or } \mathrm{p}(\mathrm{j}-1)=”.” \
\text {False} , & \text {else}
\end{array}\right.$
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p: return not s
m,n = len(s),len(p)
# 初始化当s为空的dp数组(dp[i][j] = s[:i]是否匹配p[:i])
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0], dp[0][1] = True, False
for i in range(2,n+1):
if p[i-1] == "*":
dp[0][i] = dp[0][i-2] # 每有一个*，该dp值会与其前第二个一样
# 动态规划
for i in range(1,m+1):
for j in range(1,n+1):
if p[j-1] == s[i-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
if p[j-2] != s[i-1]:
dp[i][j] = dp[i][j-2] # 匹配0次
if (p[j-2] == s[i-1] or p[j-2] == '.'):
dp[i][j] = dp[i][j-2] or dp[i-1][j] # 匹配0次 or 匹配多次
else:
dp[i][j] = False
return dp[m][n]
42 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
动态规划 O(n) ☆☆☆☆
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i] += if nums[i-1]>0 else 0
return max(nums)
49 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
动态规划 O(n) ☆☆☆☆
class Solution:
def nthUglyNumber(self, n: int) :
dp, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[n-1]
其他
43 1～n整数中1出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
递归 O(lgn) ☆☆☆☆☆
解析参考这里。
class Solution:
def countDigitOne(self, n: int) -> int:
def helper(s):
if not s:
return 0 # 剩余位为0
n = len(str(s)) # 长度，即最高位数
if n == 1:
return 1
strs = str(s)
s0 = int(strs[0])
if s0 > 1:
return s0 * (n-1) * 10 ** (n-2) + helper(int(strs[1:])) + 10**(n-1)
else:
return s0 * (n-1) * 10 ** (n-2) + helper(int(strs[1:])) + (int(strs[1:])+1)
return helper(n)
57-2 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
输入：target = 9
输出：[[2,3,4],[4,5]]
滑动窗口法 O(n) ☆☆☆
def findContinuousSequence(self, target: int) -> List[List[int]]:
i = 1 # 滑动窗口的左边界
j = 1 # 滑动窗口的右边界
sum = 0 # 滑动窗口中数字的和
res = []
while i <= target // 2:
if sum < target:
# 右边界向右移动
sum += j
j += 1
elif sum > target:
# 左边界向右移动
sum -= i
i += 1
else:
# 记录结果
arr = list(range(i, j))
res.append(arr)
# 左边界向右移动
sum -= i
i += 1
return res
58-2 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
切片 ☆
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
return s[n:] + s[:n]
拼接 ☆☆
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
res = []
for i in range(n, n + len(s)):
res.append(s[i % len(s)])
return ''.join(res)
62 圆圈中最后剩下的数字
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
模拟法 O(n²) ☆☆
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
lis = list(range(n))
i = -1 # 记录上一次删除的位置
while len(lis)>1:
j = (i + m)%len(lis)
del lis[j]
i = j-1
return lis[0]
数学解法-约瑟夫环 O(n) ☆☆☆☆
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
# 通过最后的坐标反推一开始的坐标
res = 0
for i in range(2,n+1):
res = (res+m)%i
return res
66 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中b[i]的值是数组a中除了下标i以外的元素的积。
对称遍历 O(n) ☆☆☆☆
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
b,tmp = [1] * len(a),1
for i in range(1,len(a)):
b[i] = b[i-1] * a[i-1]
for i in range(len(a)-2,-1,-1):
tmp *= a[i+1]
b[i] *= tmp
return b
67 把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
暴力法O(lgn) ☆☆
class Solution:
def strToInt(self, str: str) -> int:
s = str.strip()
if not s:
return 0
res, sign = 0, 1
int_max,int_min = 2**31-1,-2**31
bndry = 2**31 //10
if s[0]=='+':
pass
elif s[0] == '-':
sign = -1
elif '0' <= s[0] <= '9':
res = ord(s[0]) - ord('0')
else:
return res
for c in s[1:]:
if '0' <= c <= '9':
# 数字越界处理
if res > bndry or res == bndry and c > '7':
return int_max if sign>0 else int_min
res = res * 10 + ord(c) - ord('0')
else:
break
return res * sign
