这是剑指offer第二版的刷题小总结, 对应leetcode上剑指Offer专题的题目. 括号内的数字对应主站中题目的序号, 没有注明的复杂度都是指时间复杂度.
树
07.重建二叉树: 构建二叉树, 用前序遍历. preorder确定根节点的值, inorder确定左子树的大小, 就能根据index的大小来构建树. 复杂度O(n).
26.树的子结构: 两层遍历, 第一层遍历A的所有节点, 再以这些节点为根, 与B比较.
27.二叉树的镜像(226): 前序后序都可以, 交换二叉树的左右子树.
28.对称的二叉树(101): 遍历, 从左右子树两个方向一起走, 必须保证值相等, 直到左右同时到达null.
32-I.从上到下打印二叉树: BFS.
32-II.从上到下打印二叉树II(102): BFS.
32-III.从上到下打印二叉树III: 在上题的基础上加一个boolean turn来判断每一层正着添加还是倒着添加.
33.二叉搜索树的后序遍历序列: 最后一个结点是根节点, 由此判断大小关系, 分隔数组, 并在下一个递归继续判断. 复杂度$O(n^{2})$. 这道题的序列只是可能是二叉搜索树的后序遍历结果, 因为不同的数树可能有同样的遍历结果.
36.二叉搜索树与双向链表(426): 二叉搜索树自然需要中序遍历. 需要记录当前遍历的节点cur和前驱节点pre, 每次连接即可. 注意pre和head的值要存下来, 最后把最后的pre(最大的节点)和head(最小的节点)连接起来.
37.序列化二叉树(297): 前序遍历或后序遍历都可以. 序列化时, 没有子节点的节点则加入null到数组(LinkedList也可以). 反序列化就是遍历序列化的那个String/数组/LinkedList.
54.二叉搜索树的第k大节点: 按右中左的顺序中序遍历, 把k当成class Solution的属性, 就不需要额外的变量保存遍历的次数了.
55-I.二叉树的深度(104): 前序遍历, 或者递归思想直接返回左子树和右子树较大的那个高度.
55-II.平衡二叉树(110): 在上一题的基础上比较深度, 要求左右子树深度差小于等于1, 并且所有子树都满足条件, 时间复杂度$O(nlogn)$(每层执行复杂度 * 层数复杂度). 而后序遍历的复杂度是$O(n)$, 从往上算高度, 一旦不满足条件则可以返回-1, 表示该树不平衡.
68-I.二叉搜索树的最近公共祖先(235): 根据大小判断两个节点在左子树还是右子树, 如果一大一小则该节点是最近公共祖先.
68-II.二叉树的最近公共祖先(236): 后序遍历, 没找到就返回null, 否则返回p, q. 当left, right都不为null时, root就是答案.
链表
06.从尾到头打印链表: 用ArrayList遍历再反过来填到数组中, 复杂度$O(n)$.
18.删除链表的节点: 用dummy虚拟指针简化操作, 返回时直接返回dummy.next.
22.链表中倒数第k个节点: 双指针.
24.反转链表: 迭代较为简单, 递归可以想象为二叉树的后序遍历, 先遍历到最后的newHead, 再层层翻转.
25.合并两个排序的链表(21): 迭代较为简单, 递归可以想象为二叉树的前序遍历, 函数的作用是返回合并后的链表, 所以只要让head.next = mergeTwoLists(l1, l2)即可.
35.复杂链表的复制: 用HashMap的key保存原结点, value保存新的结点. 通过源节点的指针构建新的链表, 复杂度$O(n)$.
52.两个链表的第一个公共节点(160): 两个链表拼起来总长度一样, 所以遍历一遍一定会在中间相交, 除非没有相交节点. 复杂度$O(m+n)$.
动态规划
10-I.斐波那契数列: 不断由两个数相加得到下一个数, 每个状态只与前两个数有关, 所以只用保存两个数字即可, 空间复杂度$O(1)$.
10-II.青蛙跳台阶问题: 和上一道题一样, 但是初始条件改变, 跳上第0级台阶的方法数为1, 也就是不跳.
14-I.剪绳子(343): dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j)), 复杂度$O(n^{2})$, 也可以贪心贪心的去做, 复杂度O(n).
19.正则表达式匹配(10): 类似编辑距离, 用二维数组boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];解双序列问题, 数组的含义是前s的前i个字符和p的前j个字符是否匹配. 在charAt的时候要减一, 因为我们增加了两个序列都为空的初始状态.
42.连续子数组的最大和(53): nums[i] = Math.max(nums[i], nums[i - 1] + nums[i]);, 每一轮都要看是否超过了之前的最大值. 这个方法默认抛弃了和为负的连续子数组.
46.把数字翻译成字符串: 符合要求dp[i] = dp[i - 1] + dp[i - 2], 否则dp[i] = dp[i - 1].
47.礼物的最大价值: 选左边和上面最贵的礼物.
49.丑数(264): dp[0] = 1, 用三个指针指向它, 分别代表乘2, 3, 5. 每次选乘积最小的那一个并移动指针.
60.n个骰子的点数: 一个一个骰子逐层计算, 每一个都是在上一个的基础上, 6个乘1/6.
63.股票的最大利润: 只买卖一次, 所以只用计算当前值减去前面出现过的最小值即可, res = Math.max(res, price - minprice);.
二分法
11.旋转数组的最小数字(154): 把right和mid作比较, 从而知道当前mid在大的那一边还是小的那一边, 如果相等则right–(因为可能有重复的数字).
53-I.在排序数组中查找数字I(34): 先找到数字, 再向左右扩展查找. 复杂度$logn$.
53-II.0～n-1中缺失的数字: mid == nums[mid]说明缺失的数字在右边. 否则缺失的数字在左边. 最后返回left.
堆/栈/队列
09.用两个栈实现队列: stack1专门用来执行deleteHead操作, 当stack1为空时需要先把stack2中的元素全移动到stack1, stack2只用来执行appendTail操作.
30.包含min函数的栈(155): 用辅助栈把最小的元素入栈, 如果这个元素被主栈pop了, 在虚拟栈中也要pop.
31.栈的压入, 弹出序列(946): 题目中说pushed是popped的排列并且没有重复值, 所以直接用栈模拟这个过程即可, 每次循环都push一个元素, 并且当栈顶与popped当前元素相等时就出栈. 最后判断栈是否为空得到答案.
41.数据流中的中位数(295): 用大顶堆小顶堆解决. 大顶堆存较小的数, 小顶堆存较大的数. 当两个堆大小不同的时候, 添加数字往大顶堆添加, 而中位数就是小顶堆的顶. 否则往小顶堆添加, 中位数是两个堆顶的平均数, 这里出除法要除以2.0, 否则是整除. 添加数字的复杂度是log(n), 而查找中位数的复杂度是$O(1)$.
59-I.滑动窗口的最大值(239): 双端的单调队列, 保证队首永远是最大的数字, 每次也把队首添加进结果数组, 复杂度O(n).
59-II.队列的最大值: 方法同上, 用Queue保存元素, Deque的单调队列保存最大值. 注意这里会用到Integer比较, 所以用.equals().
数组
04.二维数组中的查找(240): 从左下的结点开始搜索, 向上走数字减小, 向右走数字变大, 复杂度$O(m+n)$, m和n指数组的行数和列数.
21.调整数组顺序使奇数位于偶数前面: 头尾双指针, 用left找前面的偶数, right找后面的奇数, 然后交换.
29.顺时针打印矩阵(54): 将上下左右边界逐渐收缩, 直到(left > right || up > down).
57.和为s的两个数字: 左右双指针.
57-II.和为s的连续正数序列: 滑动窗口, Java可以用list.toArray(new int[list.size()][]);来转换List到int数组.
66.构建乘积数组: 把a展开成二维数组(二维数组是虚拟的, 我们只在意每一列的值), 1就位于对角线上, 也就是那个没有被乘的数字. 那么只要按顺序计算下三角和上三角乘积即可.
DFS与BFS
12.矩阵中的路径(79): 对每个起始节点回溯, 如果有一个点成功就返回true.
13.机器人的运动范围: DFS/BFS都可以, 用DFS可以用回溯框架. 返回值是1 + backtrack() + backtrack() + ..., 避免设置类的设置属性.
34.二叉树中和为某一值的路径(113): 套着树外壳的回溯题. 这里在添加路径之后不能直接return, 因为还没有做回溯的操作. 求sum的回溯可以直接算sum - root.val, 减少变量, 这个减操作会放在判断sum == 0之前, 目的是去重, 所以进入了递归结束的功能区之后, 添加了一个path需要手动地path.removeLast()才能返回. 复杂度$O(n)$.
38.字符串的排列: 相当于没有重复值的全排列问题, 复杂度$O(N!)$.
数学系列
16.数值的整数次方(50): 快速幂, 注意n可能是负数, 所以x可能需要取倒数, n可能需要取相反数, 而int型最小的$2^{-31}$取相反数超出了int范围, 所以要用long来存. 复杂度$O(logn)$.
17.打印从1到最大的n位数: 关键点在解决大数问题, 需要用String来表示数字, 从而转化为全排列问题链接. 通过9的数量用来进位, 通过设立左边界, 确定位数的范围.
43.1～n整数中1出现的次数(233): 分三位cur, low, high, 分别计算每一位中1出现的次数. 如果cur==0, 则只由高位决定; 如果cur==1, 则由高位和低位造成的当前多出现的那些1决定; 若果cur>1, 相当于上一个基础上又多跑了一个高位的数字. 复杂度logn, 底为10.
44.数字序列中某一位的数字(400): 1位的数字有9个(0除外), 2位有90个, 由此判断该数字是第几位, 进而判断数字是多少, n对应的该数字第几位. 复杂度logn, 底为10.
61.扑克牌中的顺子: 转换思路, 等价于除0外没有重复数字的情况下, 最大的数和最小的数之差是否小于2.
62.圆圈中最后剩下的数字: 约瑟夫环, 这题是从0开始的序列, 数字本身就是index. 根据最后剩下的数字反推, 最后剩下一个人数字, index为0. 正向看, 每次删除都是向前移动m个位置, 倒推的时候, 就每次补上m个位置再与当前长度i取模, 推出当前目标数字的index, 直到i == n.
哈希表
03.数组中重复的数字: HashSet存储, 复杂度$O(n)$.
39.数组中出现次数超过一半的数字(169): 直接统计即可, 空间复杂度$O(n)$. 用摩尔投票法可以把空间复杂度降到$O(1)$.
50.第一个只出现一次的字符: HashMap<Character, Boolean> map = new HashMap<>();遍历添加, 最后遍历数组找到第一个符合要求的key, 没有则返回空. 那么上一轮的位置就是(0 + m) % 2. 2位倒数第二轮的数组长度. 一直递推到长度为n的数字序列, 就能知道最后这个数字所在的位置.
字符串
05.替换空格: 用StringBuilder解决, 复杂度$O(n)$.
48.最长不含重复字符的子字符串(3): 双指针, 开始时左右指针同时指向0, 用HashSet保存当前字母. 若重复, 则左指针向右移动, 否则右指针向右移动, 当前长度加1. 时间复杂度$O(n)$.
58-I.翻转单词顺序: 分隔再倒序, 用trim()去除收尾空格.
58-II.左旋转字符串: 用n切片, 再拼接. substring()是线性的, 所以复杂度是O(n).
67.把字符串转换成整数: 遍历即可, str = str.trim();去首尾空格.
贪心算法
14-II.剪绳子II(343): 不能像I题一样了, 否则越界. 用贪心做, 中间过程取模. 尽量每次都拆3出来, 剩下的再相乘.
位运算
15.二进制中1的个数(191): n不断无符号右移, 并与1, 结果为1, 则当前位为1. 终止条件是n != 0, 不能是n > 0, 否则符号位移动后会出问题.
56-I.数组中数字出现的次数: 数组中的数字互相异或, 那么剩下的一定是两个不同数字的异或a. 通过a可以知道这个两个数字哪一位不相等(为1的位), 用为1的这一位可以把原数组分成两组, 再把这两组分别异或, 最终的结果就是两个数字.
56-II.数组中数字出现的次数II: 统计每一位的1数量, 这个数字除以3余1的那一位就是唯一数字的答案.
排序
40.最小的k个数: 快排, 每次partition的时候进行判断, 如果p + 1 > k, 那么只用对左边排序, 反之对右边排序, 如果相等则数组的前k个最小.
45.把数组排成最小的数: 自定义排序, 比较字符串情况下的a + b和b + a的大小.
51.数组中的逆序对: 归并排序, 每次右数组大于左数组时, count += mid - i + 1. 复杂度$O(nlogn)$.
String,Integer等类型比较要用.equals()
其他
64.求1+2+…+n: 通过短路x = n > 1 && sumNums(n - 1) > 0;, 前面的x = n > 1不满足就不会执行后面的语句.
参考
- 剑指Offer
- leetcode剑指Offer
comments powered by Disqus