CodingInterviews: A Python repository from PuHaoran

剑指 Offer（第 2 版）

leetcode地址：https://leetcode.cn/problem-list/xb9nqhhg/

数组

// 快排模版
def quick_sort(l, r):
    if l >= r:
        return
    i, j = l-1, r+1
    x = nums[l]
    while i < j:
        while 1:
            i += 1
            if nums[i] >= x:
                break
        while 1:
            j -= 1
            if nums[j] <= x:
                break
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quick_sort(l, j)
    quick_sort(j+1, r)
    
// 归并排序模版
def merge_sort(l, r):
    if l >= r:
        return
    mid = (l+r) // 2
    i, j, k = l, mid+1, 0
    merge_sort(l, mid)
    merge_sort(mid+1, r)
    temp = []
    while i <= mid and j <= r:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    if i <= mid:
        temp += arr[i:mid+1]
    if j <= r:
        temp += arr[j:r+1]
    for i in range(len(temp)):
        arr[l+i] = temp[i]

Alg	**	时间复杂度	Tag
剑指 Offer 03. 数组中重复的数字	若当前元素已经在对应索引上则遍历下一个元素；若当前元素不等于对应的索引，则与对应索引的元素进行交换，保证该元素在对应索引上，但若对应索引已经有一个正确的元素，那说明当前元素为重复元素。	O(n)	数组
剑指 Offer 04. 二维数组中的查找	利用矩阵单调性解题，左上角的元素一定是对应列的最小值，一定是对应行的最大值，通过该特性可以不断缩小搜索范围。	$O(n^2)$	数组
剑指 Offer 29. 顺时针打印矩阵	按照右、下、左、上的顺序遍历数组，其中起始位置位于(0,-1)，走下一步之前先进行正确性的判断。	O(n)	数组
剑指 Offer 39. 数组中出现次数超过一半的数字	先排序，然后通过前后两个双指针去掉任意两个不相等的数据，最后剩下的就是众数。	O(n)	数组
剑指 Offer 45. 把数组排成最小的数	快排。两元素比较规则：x + y < y + x => x < y;y + x < x + y => y < x。	O(logn)	快速排序
剑指 Offer 51. 数组中的逆序对	归并排序过程对A、B两个有序数组进行比较，若arr[i]<=arr[j]，则i+=1，若arr[i]>arr[j]，则j+1，此时共mid-i+1个数均大于arr[j]。	O(logn)	归并排序
剑指 Offer 61. 扑克牌中的顺子	题解一。去掉0之后，判断是否重复，是否最大值-最小值<=4。题解二。统计0的个数，判断是否重复，0的个数是否>=数字间隔之和。	O(n)	数组
剑指 Offer 66. 构建乘积数组	每一行所有除对角线元素相乘即为乘积数组的元素。先从上到下构建下三角乘积数组，然后从下到上构建上三角乘积数组。	$O(n^{2})$	数组

字符串

Alg	**	时间复杂度	Tag
剑指 Offer 20. 表示数值的字符串	去掉两端空格，遍历字符串，判断e、.、符号不满足条件的所有情况。	O(n)	字符串
剑指 Offer 43. 1～n 整数中 1 出现的次数	-	-	-
剑指 Offer 44. 数字序列中某一位的数字	找规律，先找到其是几位数，然后再找到对应数字，最后数字的对应位。	O(1)	找规律字符串
剑指 Offer 50. 第一个只出现一次的字符	遍历数组，字典保存字符是否出现一次，出现一次为True，多次为False；然后遍历字典(python3.6默认有序)，返回第一个出现一次的字符。	O(n)	字符串字典
剑指 Offer 58 - II. 左旋转字符串	先全部翻转，然后前半部分和后半部分分别翻转。	O(n)	字符串
剑指 Offer 67. 把字符串转换成整数	去掉两边的空字符，然后记录首位的正负号；遍历数组，若字符为符号字符(+/-)且在开头则跳过，若为数字字符则res=res*10+ord(s[i])-48，否则为非法字符则跳出循环。	O(n)	字符串

二分

Alg	**	时间复杂度	Tag
剑指 Offer 11. 旋转数组的最小数字	利用左区间一定大于右区间解题，求右区间的左端点。arr[mid]>arr[r],l=mid+1；arr[mid]<arr[r],r=mid；因为存在[3,3,1,3]这种情况，当arr[mid]==arr[r]时，不能r=mid，而是r-=1。	O(logn)	数组二分
剑指 Offer 16. 数值的整数次方	快速幂。分治算法，当n为偶数x^(n//2)x^(n//2)，n为奇数x^(n//2)x^(n//2)*x，递归求解。	O(logn)	快速幂二分
剑指 Offer 53 - I. 在排序数组中查找数字 I	二分。找最左端索引和最右端索引，然后二者相减+1即为出现次数；单调数组中找一个区间，本质是找右区间端点和左区间端点。	O(logn)	二分
剑指 Offer 53 - II. 0～n-1中缺失的数字	二分。本质是寻找区间左端点（左边第一个索引与值不相等的索引）。	O(logn)	二分

链表

Alg	**	时间复杂度	Tag
剑指 Offer 06. 从尾到头打印链表	递归。先访问每一个节点，然后将节点添加到结果数组中。	O(n)	链表递归
剑指 Offer 18. 删除链表的节点	遍历节点的同时保留一个前驱节点，若当前为目标节点，pre.next = p.next。	O(n)	链表
剑指 Offer 22. 链表中倒数第k个节点	快慢双指针，快指针先走k步，然后慢指针再走，当快指针走到头时，慢指针即为倒数第k个数。	O(n)	链表双指针
剑指 Offer 24. 反转链表	p为首节点，q为空节点；遍历p的同时保存p_next=p.next，并将p节点作为q的首节点p.next=q，然后更新p和q。	O(n)	链表
剑指 Offer 25. 合并两个排序的链表	创建一个新链表。从前往后进行遍历链表并判断大小，小的合并到新链表上，最终未遍历完的链表也拼接到新链表。递归。递归返回当前节点或者一串节点，l1.next=merge(l1.next, l2) return l1。	O(n)	链表递归
剑指 Offer 35. 复杂链表的复制	复制链表各节点在原链表节点后，然后遍历链表根据原链表random节点的下一个节点即为新链表对应的random节点，得到复制链表。	O(n)	链表
剑指 Offer 52. 两个链表的第一个公共节点	A和B在两条不同长度的跑道上跑步，以相同速度，A跑完自己的跑道之后跑B的跑道;B也一样，二者最终一定会在跑道交点或终点相交。	O(m+n)	链表

栈/队列/堆

// 堆排序模版
// 建堆。构建1-n数组。
global n
arr = arr[1...n]
n = len(arr)
// 重构堆。从倒数第一个非叶子节点从后向前down(i)，以递归形式对节点位置进行调整。
def down(i):
    t = i
    if 2*i<=n and arr[2*i] < arr[t]:
        t = 2*i
    if 2*i+1<=n and arr[2*i+1] < arr[t]:
        t = 2*i+1
    if i != t:
        arr[i], arr[t] = arr[t], arr[i]
        down(t)
for i in range(n//2, 0, -1):
    down(i)
// 去掉堆顶元素
arr[1], arr[n] = arr[n], arr[1]
n -= 1
down(1)

Alg	**	时间复杂度	Tag
剑指 Offer 09. 用两个栈实现队列	使用A和B两个栈模拟队列的插入和删除操作。进队列直接看做进入A栈，出队列操作需要把A栈数据全部倒入B栈，然后弹出栈顶元素。注意B栈为空时才能将A栈数据全部倒入，否则直接弹出B栈现存的栈顶元素即可。	O(n)	栈队列
剑指 Offer 30. 包含min函数的栈	单调栈。创建普通栈的同时创建一个单调递减的栈；若当前元素入栈元素小于等于栈顶则直接入栈，否则不做处理；若当前元素等于栈顶元素，则出栈；否则，直接入栈。	O(n)	单调栈
剑指 Offer 31. 栈的压入、弹出序列	遍历pushed，将元素逐个入栈，若当前栈顶元素等于popped当前所指元素，则弹出栈顶元素并popped指针进一。	O(n)	栈
剑指 Offer 40. 最小的k个数	一堆排序解法。构建1-n的数组，然后从倒数第一个非叶子节点从后向前遍历，down(i)以递归方式进行节点位置的调整，判断当前节点与孩子节点大小并交换(若交换则按交换的孩子位置继续down)。二快排模版解法。[A][B]，若k的个数<=A长度则只递归A（最小的k个值在A区间里），否则只递归B并更新k-=A区间长度（A区间的值都满足最小的k个值，同时有一部分k-A长度个值在B区间里）。	O(logn)	堆排序
剑指 Offer 41. 数据流中的中位数	大/小顶堆。维护A、B两个堆，A保存较小元素，B保存较大元素；A使用大顶堆存储，B使用小顶堆存储。findMedian: A == B，AB各弹出一个求平均；否则，B弹出一个。addNum: A == B，将元素入B，然后弹出一个最小值入A；否则，将元素入A，然后弹出一个最大值入B。	O(nlogn)	大顶堆小顶堆
剑指 Offer 48. 最长不含重复字符的子字符串	遍历数组，设置一个双向队列存储无重复子串，当前元素不在队列中则直接加入队列，当前元素若已在队列中则从左边弹出元素直至队列中不再存在当前元素。	O(n)	队列
剑指 Offer 59 - I. 滑动窗口的最大值	维持一个单调递减的双端队列，每次遍历时，去掉队列中超出滑动窗口的元素，并保持队列单调递减。	O(n)	单调队列
剑指 Offer 59 - II. 队列的最大值	双端队列。一个队列用于存储原始数据，另外维持一个单调递减的双端队列用于取出最大值。	O(n)	单调队列

双指针

Alg	**	时间复杂度	Tag
剑指 Offer 05. 替换空格	双指针。先利用空格数量开辟空间，然后根据双指针所指的元素从后向前进行替换操作。	$O(n)$	字符串双指针
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面	前后双指针，后指针找到一个奇数，前指针找到一个偶数，i<j则交换二者位置。（PS:快速排序使用了相同的技巧。）	O(n)	双指针
剑指 Offer 22. 链表中倒数第k个节点	快慢双指针，快指针先走k步，然后慢指针再走，当快指针走到头时，慢指针即为倒数第k个数。	O(n)	链表双指针
剑指 Offer 57. 和为s的两个数字	前后双指针。前后两个指针分别指向第一个和最后一个元素，若二者和等于target则输出结果，若小于target则i++，若大于target则j--。	O(n)	双指针
剑指 Offer 57 - II. 和为s的连续正数序列	一双指针。i、j分别指向数组起始位置，若区间内的元素和等于目标，则i++、j++；若区间内的元素和大于目标，则i++；否则j++。二前缀和解法。找到所有两数相减等于target的区间。	O(n)	双指针前缀和

位运算

求x的二进制数最低位1的位置lowbit为何可以用x & -x表示？
计算机采用二进制的补码进行数学运算，其中正数的补码是原码，负数的补码是原码取反+1，故
7 & -7 =》 000111 & 111001 =》 000001 =》1。
4 & -4 =》 000100 & 111100 =》 000100 =》4。

n >> k & 1，可以求n的第k位对应的二进制数。

n&(n-1)，可以消除n最低位的1。

Alg	**	时间复杂度	Tag
剑指 Offer 15. 二进制中1的个数	求n二进制最后一位数字，n & 1；消除最低位的1，n&(n-1)。	O(1)	位运算
剑指 Offer 56 - I. 数组中数字出现的次数	位运算。先将数组的每个元素逐个进行异或，然后对结果取lowbit（不相等的两个元素可通过与lowbit进行&操作区分）；然后再次遍历数组并根据&的结果进行分组，分组的元素异或后的结果就是目标元素。	O(n)	lowbit
剑指 Offer 56 - II. 数组中数字出现的次数 II	利用n >> k & 1，求n的第k位二进制数。两层循环，外层遍历共31位的二进制数，内层遍历所有元素，所有元素k位求和%3得到多余的数在k位上的数字。	-	位运算
剑指 Offer 64. 求1+2+…+n	布尔判断作为递归终止条件。	-	位运算
剑指 Offer 65. 不用加减乘除做加法	-	-	-

二叉树

Alg	**	时间复杂度	Tag
剑指 Offer 07. 重建二叉树	根据前序数组的首元素可确定根节点，根据中序数组可确定该根节点对应的左右子树。然后，根据确定的左/右子树的前序数组和中序数组继续递归。root.left = dfs(左子树前序数组，左子树中序数组)，root.right = dfs(右子树前序数组，右子树中序数组)。	O(logn)	二叉树
剑指 Offer 26. 树的子结构	递归。判断B是否是A的子树需要从A的各个节点进行判断，故我们需要二个递归，一个用来比较从根节点开始是否相等，一个用来遍历A的所有节点。	O(logn)	二叉树递归
剑指 Offer 27. 二叉树的镜像	前序遍历，针对每个根节点交换其左右叶子节点。	O(logn)	二叉树
剑指 Offer 28. 对称的二叉树	一、直接运用递归求解，dfs(l, r)，然后判断l的左节点==r的右节点&&l的右节点==r的左节点。二、先对树进行翻转，然后同时对两棵树进行前序遍历，判断翻转后的树与原树是否对称。	O(logn)	二叉树
剑指 Offer 32 - II. 从上到下打印二叉树 II	BFS。初始化队列 while len(q): t=q.popleft() 扩展t，注意当前队列大小即为当前层的全部元素长度。	O(logn)	二叉树 BFS
剑指 Offer 33. 二叉搜索树的后序遍历序列	根节点位于最右边，找到第一个大于根节点的索引，其到根节点之间的所有节点为右子树，其之前的所有节点为左子树；若只有一个节点或右子树比根节点小则递归终止，否则继续递归dfs(左子树)&&dfs(右子树)。	O(logn)	二叉树
剑指 Offer 34. 二叉树中和为某一值的路径	DFS。增加一个变量保存当前target-node.val的值，当该值为零且当前节点为叶子节点，将路径保存到结果列表。	O(logn)	二叉树
剑指 Offer 36. 二叉搜索树与双向链表	中序遍历。遍历过程中保存上次遍历的节点并进行双向链表构建。	O(logn)	二叉树
剑指 Offer 37. 序列化二叉树	层序遍历。通过两次层序遍历进行序列化和反序列化；其中反序列化过程可通过一个指针指向当前节点所对应的孩子节点。	O(logn)	二叉树 BFS
剑指 Offer 54. 二叉搜索树的第k大节点	二叉搜索树。对二叉搜索树进行中序遍历，可以得到一个从小到大的数组。	O(logn)	二叉搜索树
剑指 Offer 55 - I. 二叉树的深度	一BFS解法。记录层次遍历的层数。二DFS解法。当前节点深度等于其max(左孩子深度，右孩子深度)+1。	O(logn)	二叉树
剑指 Offer 55 - II. 平衡二叉树	DFS。遍历当前树并返回左右子树深度，若左右子树深度>1，说明不为平衡二叉树。	O(logn)	二叉树
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先	利用二叉搜索树左节点<根<右特点，不断缩小范围。	O(logn)	二叉搜索树
剑指 Offer 68 - II. 二叉树的最近公共祖先	递归终止条件是找到p或q或二者都没找到；若左右子树都未找到，返回None；若左子树和右子树都可以找到，则该节点是根节点；若右子树先找到，则左子树先找到的节点为根节点；若左子树先找到，则右子树先找到的节点为根节点。	O(logn)	二叉树

DFS

// DFS模版
// 初始化mark
def dfs(u, i, j):
    // 终止条件
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    for k in range(4):
        x, y = i+dx[k], j+dy[k]
        if 满足条件:
            mark[x][y] = 1
            dfs(u+1, x, y)
            mark[x][y] = 0

Alg	**	时间复杂度	Tag
剑指 Offer 12. 矩阵中的路径	dfs函数传入u作为递归终止条件，数组mark记录走过的路径并回溯，使用剪枝提前终止递归。当需要判断True/False时，考虑res = dfs(...) or dfs(...)。	$O(n^{2}m)$	DFS 数组
剑指 Offer 17. 打印从1到最大的n位数	利用DFS对数字进行全排列，dfs输入u步数作为递归终止条件，path存储路径。	-	DFS
剑指 Offer 38. 字符串的排列	DFS，使用数组mark标记走过的路径，函数传递u作为终止条件。	O(n*n!)	DFS

BFS

// BFS模版
// 初始化队列
while len(q):
    t = q.pop()
    // 扩展t，入队列

Alg	**	时间复杂度	Tag
剑指 Offer 13. 机器人的运动范围	// 初始化队列 while q.qsize(): t = q.get() // 扩展t，入队列。	$O(n^{2})$	BFS 数组

动态规划

Alg	**	时间复杂度	Tag
剑指 Offer 10- I. 斐波那契数列	线性DP。①状态表达。f(i)为前f(i-1)和f(i-2)之和。②状态转移。f(n) = f(n-1)+f(n-2)。	O(n)	DP
剑指 Offer 10- II. 青蛙跳台阶问题	线性DP。①状态表达。f(i)为前f(i-1)和f(i-2)之和。②状态转移。f(n) = f(n-1)+f(n-2)。	O(n)	DP
剑指 Offer 14- I. 剪绳子	一DP。①状态表示 f(n)，长度为n的绳子，剪开后的最大乘积。②状态转移 f(n)=max(f(n), f(i)f(n-i))，当前绳长等于剪开一次后两个子绳的最大乘积。例如长度为5的绳子，f(5) = max(f(1)f(4), f(2)f(3))二贪心。尽可能剪成长度为3的子串，其次长度为2的子串。注意长度为4时，22>1*3，故需要当最后剩下子串为4（n%3==1），需要特殊处理。	$O(n^{2})$	贪心 DP
剑指 Offer 19. 正则表达式匹配	①状态表示。f(i,j)，f(i,j)是s和p是否存在一个合法方案。②状态转移。1. p[j] not '' and i, f(i,j)=(s[i]==p[j]orp[j]=='.')&&f(i-1,j-1) 2. p[j] == '', f(i,j)=f(i,j-2)or(f(i-1,j-2)&&s[i]==p[j-1])or(f(i-2,j-2)&&s[i]==p[j-1]&&s[i-1]==p[j-1]) ①f(i-1,j)=f(i-1,j-2)or(f(i-2,j-2)&&s[i-1]==p[j-1])or(f(i-3,j-2)&&s[i-1]==p[j-1]&&s[i-2]==p[j-1]) ② =>f(i,j)=f(i,j-2)or(f(i-1,j)&&(s[i]==p[j-1]orp[j-1]=='.'))	O(nm)	DP
剑指 Offer 42. 连续子数组的最大和	DP。①状态表达 f[i] 当前子数组的最大和。②状态转移 f[i] = max(f[i-1]+arr[i], arr[i]) (集合中只有取与不取两个状态)。	O(n)	DP
剑指 Offer 46. 把数字翻译成字符串	DP。①动态表达 f(i) i个字符前有多少种不同的翻译。②动态转换 f(i) = f(i-1)+f(i-2)或f(i-1) （PS:新增的字符不满足成双的情况对增加翻译数量无益）	O(n)	DP
剑指 Offer 47. 礼物的最大价值	DP。①动态表达 f(i, j)，第i,j步能拿到的最大价值。②动态转移 f(i,j)=max(f(i-1,j), f(i,j-1))+arr[i][j]。	$O(n^{2})$	DP
剑指 Offer 49. 丑数	DP+三指针。①状态表示 f(i)第i个丑数对应的数字。②状态转移 f(i)=min(f(a)2,f(b)3,f(c)*5)，其中a、b、c是从头开始移动的三个指针，abc中一定存在一个或多个恰好大于f[i-1]的数。	O(n)	DP 三指针
剑指 Offer 60. n个骰子的点数	①状态表达。f(i)点数集合i出现的概率。②状态转移。t=[0, 1.0/6,...], temp(i+j)+=f(i)*arr(j) f=temp。	-	DP

贪心

Alg	**	时间复杂度	Tag
剑指 Offer 63. 股票的最大利润	遍历数组，res=max(res, 当前元素-之前元素的最小值)。	O(n)	数组

PuHaoran/CodingInterviews

剑指 Offer（第 2 版）

数组

字符串

二分

链表

栈/队列/堆

双指针

位运算

二叉树

DFS

BFS

动态规划

贪心