[数据结构与算法]Leetcode 做题思路总结笔记

206. 反转链表

方法一：迭代

在遍历链表时，将当前节点的next指针改为指向前一个节点。

由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

方法二：递归

递归的两个条件：

终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句

head.next.next = head
很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

1480. 一维数组的动态和

方法：原地修改

每个元素等于前面所有元素的和加上当前元素
可以从下标1开始遍历nums 数组

724. 寻找数组的中心下标

方法：前缀和

记数组的全部元素之和为 total，当遍历到第 i个元素时，设其左侧元素之和为leftsum，因为左右侧和相等，利用此题的公式规律【2*leftsum+nums[i]=total】

当中心索引左侧或右侧没有元素时，即为零个项相加，这在数学上称作「空和」（empty?sum）。在程序设计中我们约定「空和是零」。

因为可能是第一个元素，for循环里需要先if判断，再进行相加求leftsum

21. 合并两个有序链表

方法一：递归解法
根据以上规律考虑本题目：

终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）

方法二：迭代
我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，
当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

876. 链表的中间结点

方法：快慢指针
快指针每次走2步，慢指针每次走1步，当快指针走到末尾时慢指针正好走到中间。

如果有两个中间结点，则返回第二个中间结点。
快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。

如果题目要求「在两个中间结点的时候，返回第一个中间结点」
此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空。

217. 存在重复元素

方法一：哈希表? unordered_set

遍历判断是否在哈希表中已经存在，若不存在则存入哈希表，已存在则有重复元素

方法二：排序

排序后，遍历判断是否前后之前有相等的元素

1. 两数之和

方法一：暴力求解

两次遍历循环数组，nums[i]+nums[j]==target时返回答案

方法二：哈希表
方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此需要能够快速寻找数组中是否存在目标元素。如果存在，需要找出它的索引。
?使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
创建一个哈希表，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

88. 合并两个有序数组

方法一：直接合并后排序

先将数组 nums?2放进数组 nums?1的尾部，然后直接对整个数组进行排序。

方法二：双指针

方法一没有利用数组nums 1与 nums 2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。

53. 最大子数组和

方法一：暴力求解（超时）
双重遍历寻找所有可能的子序和，求得其中最大值

方法二：动态规划
dp[i]表示nums中以nums[i]结尾的最大子序和
dp[i]=max(dp[i-1]+nums[i],nums[i])
dp[i]不是当前数字，就是与前面的最大子序和的和

方法三：贪心法
从左往右迭代，一个个数字过去如果sum<0,重新开始找子序串

141. 环形链表

方法一：哈希表

遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

方法二：快慢指针
定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。
初始时，慢指针在位置 head，而快指针在位置 head->next。
如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

142. 环形链表 II

方法一：哈希表
遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

方法二：快慢指针

当发现slow 与fast 相遇时，再额外使用一个指针ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

349. 两个数组的交集

方法：哈希表
nums1遍历进哈希表中去重，遍历nums2依次判断在哈希表中已存在，存在就存入nums3，并且清除哈希表中记录。

350. 两个数组的交集 II

方法：哈希表
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

121. 买卖股票的最佳时机

方法一：暴力求解（超时）

方法二：DP (dynamic programming)

DP的思路： 利用原问题与子问题的关系，将其变成 大问题的解 = 小问题的解的函数， 从而将问题变成size的扩展即可，当size到达最大后，原问题解决了。

用一个变量记录一个历史最低价格 minprice，可以假设股票是在那天买的。那么在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，就得到了最好的答案。