剑指offer错题总结

365. 二进制中有多少个1
思路
num & (num - 1)即可消去一个1
错误
while (num != 0) 写成了 while (num & (num - 1) != 0) 这样写的话 num 没办法更新

35. 翻转链表
思路
两根指针改变下结点的指向
错误
while 中的判断条件应该为 while (head != null) 而不应该写成 while (head.next != null) 后者写法会漏掉最后一个结点

73. 前序遍历和中序遍历树构造二叉树
思路
前序遍历的第一个元素为根结点，在中序遍历数组中寻找根结点位置，分别将前序数组和中序数组分为左右子树两部分，用递归构建二叉树
错误

1. 寻找位置方法写错，for 循环的起始应该是传入的形参 start 和 end，for (int i = start; i <= end; i++)， 如果写成 for (int i = 0; i <= array.length; i++)可能会使问题规模无法降低，出现 stackoverflow 的错误。
2. 注意在递归时传入的前序形参要减去 instart

38. 搜索二维矩阵 II
思路
从左下角或者右上角开始一次排除一行或者一列
错误
x 的初始赋值写错，忘记写减 1

合并两个排序链表
错误
最后两个应该用 if，用 while 会死循环

顺时针打印矩阵
思路
以 count 值从 0 开始作为起点，分为四步：从左到右打印一行，从上往下打印一列，从右往左打印一行，从下往上打印一列，执行第二步的前提是至少有两行，执行第三步的前提是至少有两行两列，执行第四步的前提是至少有三行两列
错误

1. 打印循环判定条件没记住，应该是 while (count * 2 < row && count * 2 < col)
2. 四个转角点的坐标没设定好，出现了重复打印

连续子数组的最大和
思路
前缀和
错误
minSum 的更新要写在 max 的后面

二叉树中和为某一值的路径
思路
递归 + 分治
错误

1. 结果加入 results 要 deep copy
2. 每一个递归结束要回溯， path.remove(path.size() - 1)，path.remove() 用法记错

数组中只出现一次的数字
思路
异或 + differ &= -differ(得到最后一位的1)
错误

1. 最后 for 循环分别异或求两个数时不能用两个 if 要用 if else 因为两个 if 会造成两个不同数再次异或到一起
2. 最后for 循环中 if else 判断条件是 (nums[i] & differ) == 0，写 == 1 纠错了