总结我做nowcoder oj上剑指offer的66道题时的一些感想（分三天回顾一下）。总得来说这66题大部分还不错，字符串，链表，树，堆，栈，双端队列，动态规划，回溯，二分搜索都有涉及，但是题量还是小了些，比如回溯，初次接触的人可能会一脸懵逼。国内公司面试应该不会超出这个程度。
代码放在了github。
1. 二维数组中的查找 [打分: 5/10]
在一个每一行每一列都递增的二维数组里找一个数。trick是从左下角开始找。
-
替换空格 [打分: 3/10]
这题考的是c语言操作数组的技巧，c语言的话要先traverse一遍看有多少空格，然后定义新数组长度为oldnumber+replacenumber*2；Java可以用StringBuffer构造或者直接用String.replaceAll。 -
从尾到头打印链表[打分: 9/10]
这题要能给出多种思路。
Approach 1. 逆序链表。代码略
Approach 2. 用栈，空间O(n)。代码略
Approach 3. 递归，每次先打印后一个节点的值，缺点是可能stack overflow -
重建二叉树[打分: 8/10]
思路是定位root在inorder的数组中的位置，递归构建。 -
用两个栈实现队列[打分: 7/10]
代码短但是有一定的技巧。值得再做。 -
旋转数组的最小数字[打分: 8/10]
Leetcode高分题。值得做。 -
斐波那契数列 [打分: 7/10]
经典动态规划(DP)，早年fb面实习生签到题。 -
跳台阶[打分: 7/10]
经典DP，思路同斐波那契。leetcode原题。 -
变态跳台阶[打分: 7/10]
上一题的followup。 -
矩形覆盖[打分: 7/10]
同样是斐波那契数列。转移方程: dp [n] = dp[n-1] + dp[n - 2] -
二进制中1的个数[打分: 4/10]
位运算。看看就好。 -
数值的整数次方[打分: 6/10]
递归。 -
调整数组顺序使奇数位于偶数前面[打分: 7.5/10]
有点巧妙，类似插入排序(稳定)。不要用额外空间。 -
链表中倒数第k个结点[打分: 7/10]
快慢指针，写起来需要注意细节。
15.反转链表[打分: 7.5/10]
经典老题。迭代好写，递归难写。
-
合并两个排序的链表[打分: 7.5/10]
leetcode原题，去东京的飞机上写过。迭代好写，递归难写。 -
树的子结构 [打分: 7.5/10]
leetcode原题。子树和子结构不同。 -
二叉树的镜像 [打分: 7/10]
难倒brew作者的easy题。 -
顺时针打印矩阵 [打分: 3/10]
没啥意思的一道题。 -
包含min函数的栈 [打分: 7/10]
跟第5题两个栈实现一个队列一样有点tricky。 -
栈的压入、弹出序列 [打分: 8/10]
借助一个栈来模拟操作。有一定思维技巧，值得重复做。leetcode946题。 -
从上往下打印二叉树 [打分: 8/10]
BFS。送分题。不谈了。 -
二叉搜索树的后序遍历序列 [打分: 8/10]
这题好多种解法，我一开始是通过重建二叉树来做的，后来发现递归有更巧妙做法。值得重做。 -
二叉树中和为某一值的路径 [打分: 8/10]
一道回溯题。跟BinaryTreePaths和CombinationSum的解法类似。需要注意的就是target的判断和不要多remove一次。 -
复杂链表的复制[打分: 6/10]
leetcode原题。解法比较固定。
第一步，在旧链表中创建新链表，此时不处理新链表的next和random（因为random指向的节点可能还没初始化出来）
第二步，初始化新链表的random
第三步，分离两个链表 -
二叉搜索树与双向链表 [打分: 6/10]
把BST转换成双向链表。这题我不是很理解，也没说要返回head。它的意思大概是说把tree.left当做node.prev吧，那就中序遍历，把cur.left指向prev，prev.right指向cur。 -
字符串的排列 [打分: 10/10]
leetcode原题。经典backtracking。 -
数组中出现次数超过一半的数字[打分: 7/10]
这题是典型的有点tricky的题，要记住。借助额外空间当然简单但是不是面试官想看到的答案。 -
最小的K个数 [打分: 10/10]
PriorityQueue与最小堆的应用。 -
连续子数组的最大和 [打分: 9/10]
经典DP。Leetcode53题。Maximum SubArray。 -
整数中1出现的次数（从1到n整数中1出现的次数） [打分: 0/10]
这题直接放弃了 Math的题，实在不想看。LeetCode 233题。 -
把数组排成最小的数 [打分: 7/10]
这题就是LeetCode 179. Largest Number。简单方法用一个Comparator来比较o1 + o2和o2 + o1的大小就行。另有一种奇淫巧技。 -
丑数 [打分: 7.5/10]
这题是leetcode 264. Ugly Number II。brute force会TLE。要用DP。 -
第一个只出现一次的字符位置 [打分: 4/10]
用Map就行。至少要遍历一次。这题leetcode也有，一道easy题。 -
数组中的逆序对 [打分: 7/10]
考察merge sort。在merge sort基础上加一行即可。值得做。 -
两个链表的第一个公共结点 [打分: 8/10]
方法1，Map，空间O(n)，不太好。
方法2，找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走。值得重复做。 -
数字在排序数组中出现的次数 [打分: 8/10]
重复进行二分搜索。另有新颖解法。 -
二叉树的深度 [打分: 7/10]
DFS或者BFS都行。做烂了。 -
平衡二叉树 [打分: 7.5/10]
这题也比较tricky，要post order，否则多走很多路。 -
数组中只出现一次的数字 [打分: 6/10]
这题考察XOR操作。 -
和为S的连续正数序列[打分: 9/10]
滑动窗口法。值得做。 -
和为S的两个数字[打分: 8/10]
这题跟two sum的区别就是这题是sorted array，所以可以用two pointers。 -
左旋转字符串[打分: 7/10]
用substring就行。不过这题面试官应该想看的是两个字符串拼接再substring的解法。 -
翻转单词顺序列[打分: 7.5/10]
这题9月面试的时候问到，我直接用split来做，面试官一直提示我直接操作字符；现在想想他想看的是剑指offer上的解法，先翻转每个单词，再翻转整个句子；或者先翻转整个句子，再翻转每个单词。
证明一件事情：无论你想的答案复杂度如何，面试官想看的永远是他看过的那个答案。 -
扑克牌顺子[打分: 7/10]
我重新描述一下题目: 给一个数组里面有5个非负整数，其中0可以看做任何数，问这五个数能否组成连续序列。解法是one pass hashset。不用排序。 -
孩子们的游戏(圆圈中最后剩下的数)[打分: 8/10]
约瑟夫环问题。
编号0 ~ n - 1的小朋友围成圆圈，从0开始依次数m - 1个数，第m - 1个不再参与游戏；然后下一个人继续从0开始数，求最后剩下的人的序号。
用Java的话可以用linkedlist模拟，可以模拟remove。linkedlist比arraylist插入删除效率高，因为不用arraycopy。也可以用数组。 -
求1+2+3+...+n[打分: 3/10]
这题看了下书上，本意是用一些c++特性来求解。用Java的话可以用递归和&&。 -
不用加减乘除做加法。[打分: 3/10]
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。位运算。 -
把字符串转换成整数[打分: 5/10]
这题是leetcode第8题。那题差评率高。解法没啥意思，就是按位累乘。 -
数组中重复的数字[打分: 8/10]
approach1, sort 复杂度高。
approach2, map/set 需要额外空间。
approach3, inplace substitution。无需额外空间，利用「长度为n的数组里的所有数字都在0到n-1的范围内」这个条件。思路是把nums[nums[i]]上的数字+length，这样下次如果发现nums[nums[i]]已经＞=length了，说明已经加过一次了。有一定思维难度。 -
构建乘积数组[打分: 7/10]
这题要画图才能做出来。有一定的思维技巧。 -
正则表达式匹配 [打分: 7/10]
剑指offer上唯一一道hard题。对应leetcode第10题。递归求解。 -
表示数值的字符串 [打分: 0/10]
很没价值的一题。如果这题因为漏了corner case而不能AC，无需责备自己。 -
字符流中第一个不重复的字符 [打分: 5/10]
这题要用额外空间。我用了LinkedHashMap，然后对map.entrySet()做遍历。也可以直接用HashMap。 -
链表中环的入口结点[打分: 7/10]
最简单的方法，找第一个重复的内存，需要O(n)空间。
最标准的解法，leetcode142、287题的快慢指针方法。 -
删除链表中重复的结点[打分: 7/10]
runner和walker操作。 -
二叉树的下一个结点[打分: 7//10]
多重情况要考虑，需要画图。 -
对称的二叉树[打分: 8/10]
代码很巧妙，DFS或BFS都行。leetcode有。 -
按之字形顺序打印二叉树[打分:7/10]
BFS送分题。
-
把二叉树打印成多行[打分:7/10]
BFS送分题。 -
序列化二叉树[打分: 8/10]
leetcode经典题，第二道hard。 -
二叉搜索树的第k个结点[打分: 7.5/10]
inorder DFS即可，需要再写一遍。 -
数据流中的中位数[打分: 9/10]
这题非常巧妙，用两个PriorityQueue.
网友评论