【算法】算法错题集

发表于2021-12-17更新于2022-03-12字数统计1.9k阅读时长10分阅读次数

错题集

  • 剑指 Offer 30. 包含min函数的栈：记得 Integer 类型的比较要用 equals() 方法
  • 34. 在排序数组中查找元素的第一个和最后一个位置：注意边界为 -1 时可能越界。可以参考题解中的复用思想
  • 剑指 Offer 35. 复杂链表的复制：必须先遍历一遍设置 copy.next，再遍历一遍设置 random，如果依次遍历同时设置，则前面设置的 random 会被后面设置的 copy 给覆盖
  • 剑指 Offer 53 - II. 0～n-1中缺失的数字：题解里的思路很好，将数组分为左子数组和右子数组，右子数组的首位元素就是答案
  • 162. 寻找峰值：自己的思路里，注意退出循环时要判断 left 和 right 谁的值更大（可能出现左侧降序时 left 停在了索引为 1 的位置；右侧升序时 left 停在了索引为最大值的位置。这时前者是错误的，后者是正确的。所以需要额外判断停止时到底是哪种情况。或者直接用题解里的合并思路）
  • 剑指 Offer 26. 树的子结构：区分两个递归 isSubStructer() 和 recur() 的区别
  • 746. 使用最小花费爬楼梯：注意题目的意思，需要引入天台和地平线的概念来理解，dp[] 的长度要包含最后的天台。到达天台才是答案要求的值
  • 55. 跳跃游戏：贪心
  • 45. 跳跃游戏 II：贪心。注意逻辑起跳的概念（提前预约起跳，但还没真正起跳），只是记录了下次起跳后能到达的最远位置，并未真正起跳
  • 740. 删除并获得点数：本质上是打家劫舍问题
  • 剑指 Offer 63. 股票的最大利润：动态规划问题。规定当前天必须卖出的情况下的收益最，与前 i-1 天内的最大收益间的最大值
  • 438. 找到字符串中所有字母异位词：题解中的两种思路都不错。需要注意题目场景符合固定长度的数组，可以限制好每次都对比当前长度的 s 数组与 p 数组是否相同
  • 剑指 Offer 47. 礼物的最大价值：记得使用压缩技巧的话，在每个 loop 里都需要先给 dp[0] 更新值
  • 剑指 Offer 46. 把数字翻译成字符串：记住博客里记录的代码思路。也可以从右往左遍历，使用求余的方式计算当前 i 位置的值，从而省掉 String 的空间
  • 141. 环形链表：需要先判断一下链表的长度是否小于等于 2，然后在 while 循环里需要判断 quick != null && quick.next != null。因为每次 quick 都移动两步，所以必须保证 quick.next != null，否则就会空指针异常
  • 90. 子集 II：策略：先排序。如果当前值等于前一个值。那么判断前一个值是否被选中。如果被选中，则当前值可以被选中，也可以不被选中；如果没被选中，则当前值不能被选中（因为这种情况会和第一种中的某一个情况重复，例如前选中，后没选中）
  • 713. 乘积小于K的子数组：每次移动一次 right，然后迭代 left 直到找到 [left, right] 区间内为符合条件的区间，然后更新该子区间内的新增子数组个数（规定每次必须以 right 位置为子数组的末尾，这样就不会重复计算）
  • 209. 长度最小的子数组：该题和上面那题都体现为一种滑动窗口的模板：外层的循环不断增加 right，在内层使用 while 不断循环更新 left 直到满足条件后退出，此时更新了 left。
  • 剑指 Offer 12. 矩阵中的路径：DFS 问题。经典套路是主函数里遍历图中每一个位置，以其作为开头进行递归，判断当前位置作为第一个元素时能否成功找到目标字符串，剪枝操作为：修改已访问过的成功字符串为’ ’
  • 剑指 Offer 13. 机器人的运动范围：注意机器人只能从[0,0]位置出发，所以不能使用for循环遍历每一个位置，和上一题还不一样（上一题可以从任意位置出发寻找目标字符串）
  • Pow(a, b)
  • 剑指 Offer 34. 二叉树中和为某一值的路径：需要在叶子节点时判断，而不是在 null 时判断。并且记得在叶子结点处也要加上当前的数字到集合中
  • 剑指 Offer 36. 二叉搜索树与双向链表：记得退出循环时将链表头 head 和尾 pre 也连接起来
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III：每层判断奇偶，据此决定是添加到当前层的 last 还是 first（注意 tmp 需要设置为 LinkedList 类型，否则没有 addFirst 方法）。左右节点的添加还是一致的先左后右，只是添加到 list 时顺序需要判断奇偶。如果题目要求的不是保存到 list 而是打印，则这种思路就不行，因为这种思路遍历的顺序还是原顺序，只是在保存时使用技巧使得奇偶不一致。此时仍需要双端队列，每次打印两层。
  • 剑指 Offer 41. 数据流中的中位数：大小根堆，始终保证大的一半的堆保存的数据比小的一半的堆多一个，添加时都是先加入到其中的一个堆里，过滤一下后再将堆顶的元素弹出放到另一个堆里。并且计算中位数时一定要保证是 double 类型，要用 (a + b) / 2.0。
  • 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先：利用好搜索和唯一的特性，根据 p 和 q 的值与 root 值的关系判断公共祖先节点在 root 的左还是右

更优解

重点

链表题目里，翻转的题目：