《剑指 Offer》学习笔记

面试题2:实现单例模式

静态属性中创建容易有多线程问题,加锁后效率不高。
应该用静态构造函数,在声明变量的时候就初始化实例。如果需要按需加载,可以通过嵌套内部类的方式。

面试题3:数组中重复的数字

要求返回数组中任意一个重复的数字。

解法一:排序后扫描,时间 O(nlogn)
解法二:用字典计数,时间 O(n) 空间 O(n)
解法三:交换数字与下标,直到发现重复的值

如果要求不能修改原数组,可以用二分查找,计数 < mid 和 > mid 的数量,然后逐渐收敛。
二分找重复数的缺陷是,置换的是找不出来的,比如 1 2 变成 2 2 就无法找到,只有数量上增加的那个才能确保找到。

Leetcode 有一道类似的题:287. Find the Duplicate Number,最佳方案是通过快慢指针的方式,把这道题转变为寻找链表中环的入口节点。

面试题4:二维数组中的查找 - 240. Search a 2D Matrix II

二维数组,左右上下增序,找指定数的坐标。

从左下到右上,如果 < target 就右移,如果 > target 就上移,直到找到或者越界退出。
从左上角走,往右或者往下都是递增,所以不确定往哪走。从左下角走,往上的递减,往右是递增,越界终止,复杂度 N(m+n)。选择起点和方向的时候需要具有确定性,才能逐渐逼近目标值。

面试题5:替换空格

把字符串中的空格替换成 %20

从前往后遍历,每次遇到空格,都需要往后移 2 格,时间复杂度 0(n^2)
可以先遍历一遍,算下一共有多少空格,然后提前分配好数组的空间,再从后向前遍历,移动元素,时间复杂度 0(n)

类似题目,两个有序数组合并:88. Merge Sorted Array。可以直接从后往前比较大小,然后放到目标位置即可。

面试题6:从尾到头打印链表

用栈或者递归,如果要求空间 O(1) 可以考虑把链表反转过来再打印。

面试题7:重建二叉树 - 105. Construct Binary Tree from Preorder and Inorder Traversal

输入前序和中序,重建二叉树。

前序遍历的特点是 preorder[0] 就是 root,拿到这个 root 去 inorder 里寻找 root index,从而获取 left count 和 right count ,再去递归

面试题8:二叉树的下一个节点

给定二叉树和其中一个节点,如何找出中序遍历序列的下一个节点。Node 包含一个 parent 指针。

  • 如果有 right,下一个节点就是右子树的最左子节点
  • 如果没有 right,即下一个节点不是当前节点的子节点
    • 如果它是 parent 的 left ,那下一个就是 parent
    • 如果它是 parent 的 right,就往 parent 找,直到找到一个 curr 不是 curr.parent.right 的节点

面试题9:用两个栈实现队列 - 232. Implement Queue using Stacks

有两种方法。
第一种方法是时刻保持 s1 是满的 s2 的空的,这样 push 是 O(n),pop 是 O(1)
第二种方法是需要 pop/peek 的时候再去用 s1 去填充 s2 ,这样 push 是 O(1) ,pop 是 O(1)

面试题10:斐波那契数列 - 509. Fibonacci Number

加个缓存即可,类似于 dp 问题,f(n) = f(n-1) + f(n-2)

变种1:70. Climbing Stairs
变种2:用 2x1 的矩形覆盖 2x8 的矩形

面试题11:旋转数组的最小数字 - 153. Find Minimum in Rotated Sorted Array

二分查找的经典应用场景之一:寻找边界。
二分查找的 L 指向左边的递增数组的结尾,R 指向右边的递增数组的开头,所以当 LR 相邻的时候就是找到边界的时候。
如果不是严格递增的数组,即存在相同的元素的时候,如果 L = R = MID 则按照顺序查找。

判断给定的矩阵中是否存在一条包含所有指定字符的路径。

用回溯法可以解决,通常用递归的方式实现。选中一个字符后,往上下左右试探,如果匹配,就移动到下个字符,并且重复该流程。

面试题13:机器人的运动范围

m 行 n 列的格子,机器人上下左右移动,但是不能进入行坐标和列坐标的各位数之和大于 k 的格子,问机器人能到达多少个格子。

同样是回溯法,可以用一个 visited 数组记录该坐标是否被统计过。

面试题14:剪绳子 - 343. Integer Break

一根长度为 n 的绳子,剪成几段,求问最大乘积是多少。

可以用动态规划,f(n) = max(f(i) * f(n-i)),0 < i < n,时间 O(n^2) 空间 O(n)
最好用贪婪算法,尽量剪 3 ,剩 4 的时候剪 2 ,因为当 n >= 5 的时候,3 * (n-3) > 2 * (n-2),所以尽量 3 就好。

面试题15:二进制中 1 的个数 - 191. Number of 1 Bits

比较慢的位运算,是 n&1 == 1 然后 n>>1 做计数,复杂度 O(n),但是右移会引起死循环,可以用 flag=1 然后把 flag 左移来计数。
优化一下,是 n&n-1 做计数,有几个 1 就可以减几次。

面试题16:数值的整数次方 - 50. Pow(x, n)

简单的写法是 for 循环 rx,但是 n < 1 要单独处理(0 和负数)
优化方案:通过 pow(x
x, n//2) 来提高效率,O(n) 变 O(logn)了。

面试题17:打印 1 到最大的 n 位数

用字符串模拟加法,避免整数溢出。本质上就是全排列问题。

面试题18:在 O(1) 时间删除链表节点 - 237. Delete Node in a Linked List

把 next 值给自己,然后删掉 next ,在 val 上相当于删除了,内存上其实删除了 next node ,注意如果要删除的节点是最后一个节点,还是需要从 head 往后遍历。

面试题19:正则表达式匹配 - 10. Regular Expression Matching

实现一个函数来匹配包含 . 和 * 的正则表达式。

面试题20:表示数值的字符串

实现一个函数来判断字符串是否表示数值,例如:+100、5e2,但是 12e、1a3 就不是。

面试题21:调整数组顺序使奇数位于偶数前面 - 905. Sort Array By Parity

前后双指针,如果遇到偶数在奇数前面就互换。

面试题22:链表中倒数第 k 个节点 - 19. Remove Nth Node From End of List

第一个指针先走 k-1 步,然后从第 k 步开始,第二个指针一起走。当第一个指针走到 n-1 的时候,第二个指针刚好是倒数第 k 个节点。
需要注意边界情况:k >= n 和 head 不为空

面试题23:链表中环的入口点 - 142. Linked List Cycle II

两个链表,快的走两步慢的走一步,等重合的时候,快的比慢点多走了一个环。此时从 head 开始再和 slow 一起走,head 比 slow 慢了一个环的距离,等到他们再次重合的时候,就是在环入口点的时候。

面试题24:反转链表 - 206. Reverse Linked List

常规操作,俩指针即可

面试题25:合并两个排序的链表 - 21. Merge Two Sorted Lists

可以递归求解。先把较小的那个节点拎出来,然后把剩下的递归处理放在 next 里。

面试题26:树的子结构 - 572. Subtree of Another Tree

注意 isEqual !+ isSubtree,容易导致一些边界情况的问题

面试题27:二叉树的镜像 - 226. Invert Binary Tree

递归即可

面试题28:对称的二叉树 - 101. Symmetric Tree

递归即可

面试题29:顺时针打印矩阵 - 54. Spiral Matrix

直接遍历,边界条件比较复杂,可以考虑只打印最外围的圆环,然后递归执行里面的内容。

面试题30:包含 min 函数的栈 - 155. Min Stack

对应存个最小值的辅助栈做缓存。

面试题31:栈的压入弹出序列 - 946. Validate Stack Sequences

输入两个整数序列,第一个表示压入的顺序,判断第二个有没有可能是该栈的弹出顺序

如果下一个弹出刚好是栈顶数字,则直接弹出;如果下一个弹出不在栈顶,则继续压栈,直到压到下一个需要的数字为止。如果所有数字都压入还是没找到下一个弹出的数字,则不可能是一个弹出序列。

面试题32:从上往下打印二叉树 - 102. Binary Tree Level Order Traversal

逐层遍历,用一个 queue 存一下每层的 node,下个迭代清空后存 children

面试题33:二叉搜索树的后序遍历序列 - 255. Verify Preorder Sequence in Binary Search Tree

判断某个数组是否是二叉搜索树的后续遍历序列。

选中最后一个元素,这个是 root 节点。从前往后遍历,left 应该都比 root 小,right 应该都比 root 大,校验通过后,递归 left right 验证均为二叉搜索树。

面试题34:二叉树中和为某一值的路径 - 113. Path Sum II

递归

面试题35:复杂链表的复制 - 138. Copy List with Random Pointer

先遍历一边做 deep copy,再遍历一遍赋值 random ,时间复杂度是 O(n^2)。
可以通过一个 N -> N' 的映射字典把寻找 random 的时间复杂度降到 O(n),代价是 O(n) 的空间复杂度。
如果要进一步优化到 O(1) 的空间复杂度,可以直接在原链表上做 copy ,把新节点 N' 放到 N 的后面,这样 N' 的 random 指针就是 N 的 next 的 random 指针。然后再按照奇偶,把大链表拆分开即可。

面试题36:二叉搜索树与双向链表 - 426. Convert Binary Search Tree to Sorted Doubly Linked List

中序遍历+递归

面试题37:序列化二叉树 - 297. Serialize and Deserialize Binary Tree

通过前序遍历+递归的方式,用 $ 之类的符号代表叶子节点的空指针。

面试题38:字符串的排列 - 46. Permutations

选出一个数然后把剩下的数组迭代

面试题39:数组中出现次数超过一半的数字 - 169. Majority Element

通过 set 计数 c > n/2 直接做出现次数的统计。
也可以通过 quick select 方法找出中位数,类似于快排的操作,随机选择一位,然后调整数字顺序,使得比它小的在左边,比它大的在右边,如果刚好是 n/2 那就是中位数,否则,下标大于 n/2 就去左边递归,下标小于 n/2 就去右边递归。

面试题40:最小的 k 个数 - 215. Kth Largest Element in an Array

排序后可以得到 N(nlogn) 的解。
可以用 quick select 的方法优化,时间复杂度 O(n) ,代价是修改输入数组。
也可以用一个大小为 k 的容器(最大堆或者红黑树)来存放最小的 k 个数字。每次读入,如果数字少于 k 个就直接放到容器里,如果大于 k 个就比较 k 个数中的最大值与这个数值的大小关系,更小就取出最大值然后把读入的数字塞到容器里。时间复杂度 O(nlogk) 。

面试题41:数据流中的中位数 - 295. Find Median from Data Stream

数据结构 插入的时间复杂度 得到中位数的时间复杂度
没有排序的数组 O(1) O(n)
排序的数组 O(n) O(1)
排序的链表 O(n) O(1)
二叉搜索树 O(logn) O(logn)
AVL 树 O(logn) O(1)
最大堆和最小堆 O(logn) O(1)

面试题42:连续子数组的最大和 - 53. Maximum Subarray

经典 DP 问题:F(n) = n > 0 ? n + F(n-1) : F(n-1)

面试题43:从 1 到 n 整数中 1 出现的次数 - 233. Number of Digit One

从数学规律着手,去掉最高位然后递归求解。

面试题44:数字序列中某一位的数字 - 400. Nth Digit

数字以 012345678910111213... 的格式序列化到一个字符串中,求第 n 位的数字。

一样的思路,统计数学规律然后递归。

面试题45:把数组排成最小的数 - 179. Largest Number

其实是自定义一个排序规则,然后按这个规则排序即可。
自定义规则是:两个数字 m 和 n,如果 mn < nm 则打印 mn ,也就是 m 在 n 前面,按照字符串大小规则比较 mn nm 即可。

面试题46:把数字翻译成字符串 - 91. Decode Ways

给定一个数字,按照如下规则翻译成字符串:0-> A,1->B...问给定一个数字,有多少种可能的结果。

递归求解

面试题47:礼物的最大价值 - 64. Minimum Path Sum

在一个 m*n 的棋盘里,每一格都有一个数字代表价值,从左上角开始拿礼物,直到右下角,计算最多能拿到多少礼物。

二维的动态规划可以求解,优化空间复杂度的方式是不保存无用的 dp 数据。

面试题48:最长不含重复字符的子字符串 - 3. Longest Substring Without Repeating Characters

动态规划,通过一个 26 字母的表来存储该字母最后一次出现的位置,从而确定状态转移方程。
或者通过 word count + 滑动窗口一趟获取最优解

面试题49:丑数 - 264. Ugly Number II

按照传统的 2x 3x 5x 的方式往后填充 ugly number,最大的问题是不知道 length 应该是多少,如果发现 nth 达不到,就需要从头重新填充。
优化的思路是:ugly number 里的每一个数,都会被 235 乘一遍,所以存一下 235 分别乘到哪里了,然后每次取 3 个算出最小值后加入 ugly number 即可。

面试题50:第一个只出现一次的字符 - 387. First Unique Character in a String

387. First Unique Character in a String
https://leetcode.com/problems/first-unique-character-in-a-string/
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

word count 之后找到 value 为 1 的字符即可

面试题51:数组中的逆序对 - 493. Reverse Pairs

如果前面一个数字大于后面一个数字,则这两个数字组成一个逆序对。输入一个数组,求逆序对的总数。

归并排序的过程中统计逆序对的数量,相比暴利破解,时间复杂度 O(nlogn),空间复杂度 O(n)。计数一次逆序对之后就互换,这样就是从小到大排序,直到整个数组是有序的,那就数完了所有的逆序对。

面试题52:两个链表的第一个公共节点 - 160. Intersection of Two Linked Lists

用两个栈存这两个链表的节点,然后从后往前 pop ,直到不相等,就找到了最后一个公共节点。
优化方案是:双指针从 AB 出发,先到终点后,互换起点继续,重合的时候就是第一个公共节点。其实就是直接走一遍,统计长度,然后让长节点先走一下差的节点数,再继续一起走。这样第一个相同的节点就是重合的节点了。

面试题53:数字在排序数组中出现的次数 - 34. Find First and Last Position of Element in Sorted Array

两边都进行二分查找即可。二分查找的边界处理是个问题,可以套用模板。

面试题54:二叉搜索树的第 k 大节点 - 230. Kth Smallest Element in a BST

中序遍历的第 k-1 个元素

面试题55.1:二叉树的深度 - 104. Maximum Depth of Binary Tree

递归即可

面试题55.2:平衡二叉树 - 110. Balanced Binary Tree

计算出 height 之后,递归即可。注意,会有很多重复运算,可以通过后序遍历的方式,遍历子树的同时记录下子树的高度。

面试题56.1:数组中只出现一次的数字 - 260. Single Number III

数组中除两个数字外,其他都出现了两次

简单的做法是用 set 计数,存在就 remove 不存在就 add。
正确的做法是位运算,先通过异或找到 a^b ,然后通过 n&~(n-1) 找到最后一位 1 的二进制数 m,然后通过 m 把数组分组,分别做异或运算,最后剩下的 n1 n2 就是结果

面试题56.2:数组中只出现一次的数字 - 137. Single Number II

数组中除一个数字外,其他都出现了三次

二进制逐位统计 1 的数量,如果能被 3 整除,这一位就是 0,否则就是 1。

面试题57.1:和为 s 的两个数字 - 167. Two Sum II - Input array is sorted

增序数组中找两个数字,和为 s ,返回这两个数字。

和 Two Sum I 一样用 set 解比较快。由于是 sorted 所以多了一个 left right 指针的做法。

面试题57.2:和为 s 的连续正数序列

输入一个正数 s ,打印所有和为 s 的连续正数序列

small 从 1 开始,big 从 2 开始,如果和小于就 big 增加,如果和大于就 small 增加。

面试题58.1:翻转单词顺序 - 151. Reverse Words in a String

用 split+reverse 比较简单,也可以先翻句子再翻词。

面试题58.2:左旋转字符串 - 189. Rotate Array

O(1) 的空间复杂度就需要用轮换的方式来做,先全部翻转,再分别翻转左右两个部分。

面试题59.1:滑动窗口的最大值 - 239. Sliding Window Maximum

维护一个队列,存放最大值的下标,如果下一个数字比它大,就 pop 掉然后 push 进去,如果比它小,就直接 push 进去。维护这个队列即可。

面试题59.2:队列的最大值 - 155. Min Stack

同步维护一个最大值队列即可。

面试题60:N 个骰子的点数 - 1155. Number of Dice Rolls With Target Sum

求 N 个骰子点数和为 s 的概率

简单粗暴的方式就是递归求解。
优化的方案可以基于循环,逐渐增加骰子,记录出现的次数。

面试题61:扑克牌中的顺子

大小王可以是任意牌,抽五张牌,判断是否是顺子

先定义哈希表,然后把五张牌放进去,然后再看看空档能否用大小王填充上。

面试题62:圆圈中最后剩下的数字 - 390. Elimination Game

0~n-1 组成环,从 0 开始,每次删除第 m 个数字,求最后剩下的数字。

方法一:直接用数组或者链表模拟
方法二:推导公式,得出: f(n) = (f(n-1)+m) % n

面试题63:股票的最大利润

只能卖卖一次,求最大利润

记录最小值,然后更新最小值后算当前值距离最小值的最大值。

相关题:

面试题65:不用加减乘除做加法 - 371. Sum of Two Integers

不用加减乘除做加减乘除是一系列位运算的题目。在这一题里是用位运算模拟进位加一,只要 num2 > 0 就重复 num1 = num1^num2,num2 = (num1&num2)<<1 即可

面试题67:把字符串转成整数 - 8. String to Integer (atoi)

就是把字符串变成数字,做好最大最小值的边界判断,空格处理,正负处理即可

面试题68:树中两个节点的最低公共祖先 - 236. Lowest Common Ancestor of a Binary Tree

分别找到两个节点,保存根节点往下的路径,然后再找两个路径的公共节点