知识点

LeetCode算法题

1. LeetCode算法题

   1. 复习

      1. 543.【二叉树的直径】

      2. 113.【路径总和 II】

         解题思路：

         回溯算法

      3. 99.【恢复二叉搜索树】

         解题思路：

         根据二叉搜索树中序遍历的递增性质解题。

      4. 95.【不同的二叉搜索树 II】

      5. 687.【最长同值路径】

   2. 学习

      1. 54.【螺旋矩阵】

         解题思路：

         首先，想到是否可以使用dfs来做题，结果是不行的。

         因此，该题目应该思考如何模拟该过程，结果发现，一开始遍历方向是向右方的，如果碰到了界限或者遍历过的元素，则转向然后遍历。因此，关键就是转向和判断是否出界或者碰到遍历过的元素。

      2. 41.【缺失的第一个正数】

         解题思路：

         首先，描述题目：长度为len的int数组，没排序，找最小的正整数。

         正整数，就是从1开始往后计数。因此，如果长度为len的int数组中存储了[1, len]的全部数字，则最小的正整数，肯定是len + 1；如果长度为len的int数组中没有全部存储[1, len]的数字，则最小正整数肯定是里面缺失的最小的数字。

         如果不规定空间复杂度，直接用哈希表，结合上述的查找思路，即可解题。

         如果不规定时间复杂度，我们可以先排序数组，然后用二分查找解题。

         但是规定了空间复杂度为O(1)且时间复杂度为O(n)，因此，我们要用到原地哈希的技巧。

         首先，哈希表其实本身也是一个数组，通过对元素的不同哈希函数确定元素在数组上的位置。

         因此，对于该题目，如果我们定义一个哈希函数，保证元素1对应数组索引0，元素2对应索引1，...，即元素i映射到数组索引i+1上即可。

         我们定义好哈希函数后，遍历数组，运用哈希函数让数组中正整数都回到应该在的位置。

         然后我们遍历一次数组，如果都正确则返回len + 1；如果出现第一个错误位置，则返回i + 1