题目集：https://leetcode.cn/studyplan/top-100-liked/
哈希
字母异位词分组
思路：
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
最长连续序列
思路：先使用Set去重，然后检查每个数是否存在后一个数即可
双指针
移动0
思路：使用快慢指针，慢指针指向第一个0的位置，快指针用来循环遍历（右指针左边直到左指针处均为零）。
盛最多水的容器
思路：左右指针分别指向数组的左右两端，不断向中间移动（规则是移动对应数字较小的那个指针），直到重合，比较其中面积的最大值。
滑动窗口
无重复字符的最长子串
思路：定义双指针（从最左侧开始，滑动窗口的边界）和一个Set（不断记录出现的字符，左指针移动的时候剔除字符，右指针移动的时候添加一个字符）
找到字符串中所有字母异位词
思路：使用长度为p.length的滑动窗口，和一个Map记录出现的字符以及其数量，当出现的字符的数量都为0的时候，就是符合的结果。
子串
和为 K 的子数组
思路：1、穷举法，两次循环遍历，然后求出子串的和，得到符合的结果；2、前缀和
普通数组
最大子数组和
思路：动态规划，定义np[i]为以第 i 个数结尾的「连续子数组的最大和」，则有递推关系式：np[i] = max(np[i-1] + nums[i], nums[i])
合并区间
思路：首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
- 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
- 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
除自身以外数组的乘积
思路：左右乘积列表
矩阵
矩阵置零
思路：1、我们可以用两个标记数组分别记录每一行和每一列是否有零出现。2、复用原始数组作为标记，但需要额外两个变量标记第一行、第一列是否有0.
螺旋矩阵
链表
相交链表
思路：方法一：哈希集合：首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。
反转链表
思路：迭代
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let prev = null
let curr = head
while (curr) {
const tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
}
return prev
};回文链表
思路：
方法一：将值复制到数组中，然后使用双指针（对应开头和结尾）进行比。
方法二：找到中间的节点，然后反转后半部分的链表，再逐一比较。
环形链表
思路：使用set存储访问过的节点
合并两个有序链表
思路：
一、递归
二、迭代
两数相加
思路：需要考虑进位
贪心
买卖股票的最佳时机
思路：用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
跳跃游戏
思路：
var jump = function(nums) {
let position = nums.length - 1;
let steps = 0;
while (position > 0) {
for (let i = 0; i < position; i++) {
if (i + nums[i] >= position) {
position = i;
steps++;
break;
}
}
}
return steps;
};划分字母区间
思路：由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。
- 从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。
- 对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 endc，则当前片段的结束下标一定不会小于 end c，因此令 end=max(end,endc)。
- 当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 [start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。
- 重复上述过程，直到遍历完字符串。
动态规划
打家劫舍
思路：动态规划values[i] = max( nums[i] + values[i-2], values[i-1] )
完全平方数
思路：动态规划，f[i] 表示最少需要多少个数的平方来表示整数 i，状态转移方程：f(i) = 1 + min(f(i - j*j))
零钱兑换
思路：动态规划，定义values[i]为组成金额为i的最小硬币数，状态转移方程values[i] = min( 1 + values[ i - coins[j] ] , values[i] )
单词拆分
思路：动态规划，定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串是否能被空格拆分成若干个字典中出现的单词。两次循环i、j，则状态转移方程：dp[i] = dp[j] && check(s[j..i−1])
最长递增子序列
思路：动态规划，定义dp[i] 为以nums[i]结尾的最长子序列的长度，计算dp[i]时，j在区间[0, i),如果nums[j] < nums[i]状态转移方程为dp[i] = max(dp[i], 1+dp[j])
乘积最大子数组
思路：动态规划，定义max[i]和min[i]分别为下标以num[i]结尾的乘积最大/最小的值，则动态转移方程为：
max[i] = Math.max(num * max[i - 1], num * min[i - 1], num)
min[i] = Math.min(num * max[i - 1], num * min[i - 1], num)
分割等和子集
思路：动态规划，「0 - 1」背包问题，是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半。dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j，状态转移方程为：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]（分别对应取/不取第i个数）
最长有效括号
思路：
1、栈，使用arr存储字符串对应的下标，遍历字符串s，碰到’(‘添加下标，碰到’)‘根据上一个字符串的情况更新结果。
2、动态规划
多维动态规划
不同路径
思路：动态规划，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
最小路径和
思路：动态规划，dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
最长回文子串
思路：动态规划，定义dp[l][r] 表示字符串从 i 到 j 这段是否为回文
最长公共子序列
思路：动态规划，定义dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度，则状态转移方程为：
编辑距离
思路：动态规划，定义D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离，状态转移方程为：
技巧
只出现一次的数字
思路：使用异或
var singleNumber = function (nums) {
return nums.reduce((tmp, item) => tmp ^ item)
};多数元素
思路：使用map记录每个数字出现的次数，如果大于n/2的话，就是答案
颜色分类
思路：两次遍历，第一次将0都放到前面，第二次将1都放到0后面
下一个排列
思路：
- 从右往左遍历，找到第一个非降序的数，[4,5,2,6,3,1]中的”2”，下标记为l。
- 找到了之后，再从右往左遍历，找到第一个大于
nums[l]的数，是一定能找到的。然后交换这两个数。 - 从l+1开始，后面的数字一定都是降序，改为升序。（直接双指针，依次交换头尾数字即可）
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
// 双指针
var nextPermutation = function (nums) {
const n = nums.length;
// 从右往左遍历，找到第一个非降序的数
// 1. [4,5,2,6,3,1]
// 2. [3,2,1]
let l = -1;
for (let i = n - 1; i >= 1; i--) {
if (nums[i - 1] < nums[i]) {
l = i - 1;
break;
}
}
// 1. [4,5,2,6,3,1]: l=2
// 2. [3,2,1]: l=-1
if (l !== -1) {
let r = -1;
// 找到了之后，再从右往l+1遍历，找到第一个大于nums[l]的数，一定能找到
// 1. [4,5,2,6,3,1]: r=4
for (let i = n - 1; i > l; i--) {
if (nums[i] > nums[l]) {
r = i;
break;
}
}
// 交换l和r的数字
// 1. [4,5,2,6,3,1] => [4,5,3,6,2,1]
[nums[l], nums[r]] = [nums[r], nums[l]];
}
// 从l+1开始，后面的数字一定都是降序，改为升序
// 降序改为升序，不需要快排、归并、堆排等方法，直接双指针，依次交换头尾数字即可
// 1. [4,5,3,6,2,1], 从下标[l+1=3]开始从降序改为升序
// 2. [3,2,1], 从下标[l+1=0]开始从降序改为升序
let i = l + 1,
j = n - 1;
while (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
j--;
}
};寻找重复数
思路：
求平方根
function sqrtCustom(number) {
let x = number;
let y = 1;
const epsilon = 1e-17; // 精度阈值
while (Math.abs(x - y) > epsilon) {
x = (x + y) / 2;
y = number / x;
x = (x + y) / 2; // 使用平均数作为下一次迭代的近似值
}
return x;
}
let number = 9;
let sqrt = sqrtCustom(number);
console.log(sqrt); // 输出: 3，接近于真实的平方根值function customSqrt(n, tolerance = 1e-17) {
if (n < 0) {
throw new Error("Cannot compute square root of a negative number.");
}
let guess = n / 2.0;
while (Math.abs(guess * guess - n) > tolerance) {
guess = (guess + n / guess) / 2.0;
}
return guess;
}
// 测试自定义平方根函数
let customRoot = customSqrt(16);
console.log(customRoot); // 输出: 接近4的值