力扣
回溯：带有状态的递归 剪枝：回溯中基于约束条件去做选择
动态规划：每一步都是用前面已经算过的结果推出来的
- 自上而下的递归+备忘录（重复子问题）
- 自下而上的迭代
3. 无重复字符的最长子串 - 力扣（LeetCode）
滑动窗口实现
function lengthOfLongestSubstring(s) {
// 记录最大长度
let maxLen = 0;
// 当前窗口中的元素
const temp = [];
for (let right = 0; right < s.length; ++right) {
// 只要当前窗口中有最新的元素就出队一个元素
while (temp.includes(s[right])) {
temp.shift();
}
// 入队最新的元素
temp.push(s[right]);
// 如果最大长度小于当前元素的长度就覆盖
if (maxLen < temp.length) {
maxLen = temp.length;
}
}
return maxLen;
}165. 比较版本号 - 力扣（LeetCode）
切割字符串并转换成数字类型 还可以使用生成器返回迭代器的方式优化性能
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
function compareVersion(version1, version2) {
const arr1 = version1.split(".");
const arr2 = version2.split(".");
while (arr1.length && arr2.length) {
const v1 = parseInt(arr1.shift());
const v2 = parseInt(arr2.shift());
if (v1 > v2) return 1;
if (v1 < v2) return -1;
}
if (arr1.length) {
return arr1.every((v) => v == 0) ? 0 : 1;
}
if (arr2.length) {
return arr2.every((v) => v == 0) ? 0 : -1;
}
return 0;
}88. 合并两个有序数组 - 力扣（LeetCode）
三指针从后往前遍历，避免数据覆盖。
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
function merge(nums1, m, nums2, n) {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (i >= 0 && j >= 0) {
nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
while (i >= 0) {
nums1[k--] = nums1[i--];
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}415. 字符串相加 - 力扣（LeetCode）
从后往前遍历字符串，将字符转换成数字相加 也可以在位数不足的前面补上0
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function (num1, num2) {
let result = "";
let i = Math.max(num1.length, num2.length);
let j = 1;
let carry = 0;
while (j <= i) {
const n1 = num1[num1.length - j] ? parseInt(num1[num1.length - j]) : 0;
const n2 = num2[num2.length - j] ? parseInt(num2[num2.length - j]) : 0;
const sum = n1 + n2 + carry;
const res = sum % 10;
carry = Math.floor(sum / 10);
result = res + result;
++j;
}
if (carry) {
result = carry + result;
}
return result;
};20. 有效的括号 - 力扣（LeetCode）
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
const stack = [];
for (let i = 0; i < s.length; ++i) {
if (["(", "[", "{"].includes(s[i])) {
stack.push(s[i]);
} else if (["}", "]", ")"].includes(s[i])) {
if (stack.length === 0) {
return false;
} else {
const top = stack.pop();
if (
(top === "(" && s[i] === ")") ||
(top === "[" && s[i] === "]") ||
(top === "{" && s[i] === "}")
) {
continue;
}
return false;
}
}
}
return stack.length === 0;
};1. 两数之和 - 力扣（LeetCode）
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; ++i) {
for (let j = i + 1; j < nums.length; ++j) {
if(nums[i] + nums[j] === target){
return [i, j];
}
}
}
};46. 全排列 - 力扣（LeetCode）
回溯：有状态的递归
使用回溯法 递归进行深搜，遍历数字数组，如果当前元素存在于状态数组中表示当前元素已经在结果数组中了就跳过，如果不在就添加入状态数组中，继续递归，当递归出来后将当前元素从状态数组中取出（修改状态）
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const result = [];
function bfs(arr) {
if (arr.length === nums.length) {
// 防止引用传递
result.push(JSON.parse(JSON.stringify(arr)));
return;
} else {
for (let i = 0; i < nums.length; ++i) {
if (arr.includes(nums[i])) {
continue;
} else {
arr.push(nums[i]);
bfs(arr);
arr.pop();
}
}
}
}
bfs([]);
return result;
};206. 反转链表 - 力扣（LeetCode）
双指针，在反转时需要构造一个temp做中转
class ListNode {
constructor(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
let cur = head;
let pre = null;
while (cur) {
const temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}53. 最大子数组和 - 力扣（LeetCode）
每次遍历查看上次的和是否大于0，如果大于0表示此前的和相加是有益的，就相加，否则就将和赋值为当前值，再与保存的最大和比较
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let sum = 0;
let ans = nums[0];
for (let i = 0; i < nums.length; ++i) {
if (sum > 0) {
sum += nums[i];
} else {
sum = nums[i];
}
ans = Math.max(sum, ans);
}
return ans;
};102. 二叉树的层序遍历 - 力扣（LeetCode）
每次遍历传递当前层级数，层级数的索引就是自己在二维结果数组中对应的数组
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
function helper(node, level) {
if (!node) return;
if (!res[level]) {
res[level] = [];
}
res[level].push(node.val);
helper(node.left, level + 1);
helper(node.right, level + 1);
}
const res = [];
helper(root, 0);
return res;
};15. 三数之和 - 力扣（LeetCode）
一次遍历+双指针 先排序整个数组，让数组有序，每次遍历在当前值的前一个位置设置一个指针，在数组末尾设置第二个指针，如果值相加大于则右指针前移再比较，如果大于则左指针后移，如果等于则直接添加到结果数组中并两个指针都相向移动一次，再再次循环中循环左指针的值是否小
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const result = [];
nums = nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; ++i) {
if (nums[i] === nums[i - 1]) {
continue;
} else {
let l = i + 1,
r = nums.length - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] === 0) {
result.push([nums[i], nums[l], nums[r]]);
++l;
--r;
while (l < r && nums[l] === nums[l - 1]) {
++l;
}
} else if (nums[i] + nums[l] + nums[r] < 0) {
++l;
} else {
--r;
}
}
}
}
return result;
};121. 买卖股票的最佳时机 - 力扣（LeetCode）
记录买入价值，和当前利润 遍历数组，如果当前值比此前的买入价值小则将当前值记录为买入价值，否则的话就尝试卖出，取当前卖出利润和此前的利润的最大值
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let buy_price = prices[0];
let max_profit = 0;
for (let i = 0; i < prices.length; ++i) {
if (buy_price > prices[i]) {
buy_price = prices[i];
} else {
max_profit = Math.max(max_profit, prices[i] - buy_price);
}
}
return max_profit;
};141. 环形链表 - 力扣（LeetCode）
快慢指针，快指针一次走两步，慢指针一次走异步，如果快指针遇到null则无环，如果遇到慢指针则有环
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
let fast = head,
slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
return true;
}
}
return false;
};112. 路径总和 - 力扣（LeetCode）
回溯：带状态的递归 每次递归传递上次的目标值减去当前值，也就是后续节点要达到的目标总值，遇到叶子节点则返回判断
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function (root, targetSum) {
if (!root) {
return false;
} else if (!root.left && !root.right) {
return root.val === targetSum;
} else {
return (
hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val)
);
}
};70. 爬楼梯 - 力扣（LeetCode）
类似斐波那契数列，单独递归会栈溢出，需要存储之前的状态 如果台阶等于1只有一种方式，如果等于2则有两种方式，因此初始的f(1)和f(2)的值就可求出 后续的每个台阶所包含的方法就是前一次和前两次所能达到方法的和，也就是满足：f(n)=f(n-1)+f(n-2)
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
if (n <= 2) return n;
let prev1 = 1;
let prev2 = 2;
for (let i = 3; i <= n; ++i) {
const cur = prev1 + prev2;
prev1 = prev2;
prev2 = cur;
}
return prev2;
};21. 合并两个有序链表 - 力扣（LeetCode）
构建一个虚拟头节点指向新链表，并在两个链表中各设置一个指针，将相对较小的添加到新链表队尾，最后返回虚拟头节点的下一个节点
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
const head = new ListNode(0);
let cur = head;
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 || list2;
return head.next;
};215. 数组中的第K个最大元素 - 力扣（LeetCode）
将数组排序后取第k个值（索引为k-1）
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
function findKthLargest(nums, k) {
const temp = nums.sort((a, b) => b - a);
return temp[k - 1];
}912. 排序数组 - 力扣（LeetCode）
归并排序符合O(nlogn)
// 归并排序
function mergeSort(arr) {
function _mergeSort(left, right) {
if (left >= right) return;
let mid = Math.floor((left + right) / 2);
_mergeSort(left, mid);
_mergeSort(mid + 1, right);
let i = left,
j = mid + 1;
const temp = [];
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i++]);
} else {
temp.push(arr[j++]);
}
}
while (i <= mid) {
temp.push(arr[i++]);
}
while (j <= right) {
temp.push(arr[j++]);
}
for (let k = 0; k < temp.length; ++k) {
arr[left + k] = temp[k];
}
}
_mergeSort(0, arr.length - 1);
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
mergeSort(nums);
return nums;
};146. LRU 缓存 - 力扣（LeetCode）
使用map做缓存，调用get时如果元素存在就删除后再添加进去
class LRU {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
} else {
return -1;
}
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else {
if (this.cache.size >= this.capacity) {
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
}
this.cache.set(key, value);
}
}5. 最长回文子串 - 力扣（LeetCode）
每次遍历一个字符就从当前字符开始分别向左右设置一个指针，根据判断是否相等 每次遍历要执行两种情况：i和i+1，因为回文子串有两种：bab、baab
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
let max = "";
for (let i = 0; i < s.length; ++i) {
let str = helper(i, i);
if (str.length > max.length) {
max = str;
}
str = helper(i, i + 1);
if (str.length > max.length) {
max = str;
}
}
function helper(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) {
--l;
++r;
}
return s.slice(l + 1, r);
}
};200. 岛屿数量 - 力扣（LeetCode）
双层遍历二维数组，如果遇到值为1的则先加上岛屿数量，接着深搜向四周扩散，如果遇到值为1的则将值置为0表示已经遍历过了，并继续向四周扩散，如果越界或者遇到0则返回。 必须向四周扩散，不能只向右或下，因为深搜是从后往前跳出执行栈的，如果只向左或向右会人为地跳过相连的1，后面再计算岛屿数时污染数据
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function (grid) {
let res = 0;
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[i].length; ++j) {
if (grid[i][j] === "1") {
++res;
dfs(grid, i, j);
}
}
}
return res;
};
function dfs(grid, x, y) {
if ( x < 0 || y < 0 || x >= grid.length || y >= grid[x].length || grid[x][y] === "0") {
return;
} else {
grid[x][y] = "0";
// 向左扩散
dfs(grid, x, y - 1);
// 向上扩散
dfs(grid, x - 1, y);
// 向右扩散
dfs(grid, x, y + 1);
// 向下扩散
dfs(grid, x + 1, y);
}
}54. 螺旋矩阵 - 力扣（LeetCode）
在上下左右各设置一个边界，以一定顺序按边界执行，每次循环遍历这个边界上的值，循环结束后缩小边界，直到某个边界与它对应的边界接触后就跳出循环
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function (matrix) {
let left = 0, top = 0, bottom = matrix.length - 1, right = matrix[0].length - 1
const res = []
while (true) {
for (let i = left; i <= right; ++i) {
res.push(matrix[top][i])
}
if (++top > bottom) break
for (let i = top; i <= bottom; ++i) {
res.push(matrix[i][right])
}
if (--right < left) break
for (let i = right; i >= left; --i) {
res.push(matrix[bottom][i])
}
if (--bottom < top) break
for (let i = bottom; i >= top; --i) {
res.push(matrix[i][left])
}
if (++left > right) break
}
return res
};56. 合并区间 - 力扣（LeetCode）
先将区间数组按照开始区间正序排列 遍历区间数组，判断区间重叠
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
const merge = (intervals) => {
intervals = intervals.sort((a, b) => a[0] - b[0]) //排序
const res = [] // 结果数组
let temp = [] // 临时存储区间
for (let i = 0; i < intervals.length; ++i) {
const cur = intervals[i]
if (temp.length === 0) {
// 如果临时区间为空，直接存储当前区间
temp = cur
} else {
// 否则判断是否有重叠
if (temp[1] >= cur[0]) {
// 有重叠，更新临时区间的结束位置
temp[1] = Math.max(temp[1], cur[1])
} else {
// 无重叠，存储临时区间到结果数组，并更新临时区间为当前区间
res.push(temp)
temp = cur
}
}
}
if (temp.length) {
// 循环结束后，存储最后一个临时区间
res.push(temp)
}
return res
}300. 最长递增子序列 - 力扣（LeetCode）
动态规划，设置一个数组作为每一项前面递增子序列长度，默认值都是1 遍历每一项，对比每一项如果大于前面的某一项则最长子序列长度取当前项子序列长度与该项长度+1的最大值
/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = (nums) => {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i]=Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
};704. 二分查找 - 力扣（LeetCode）
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
const n = nums.length;
let left = 0, right = n - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};129. 求根节点到叶节点数字之和 - 力扣（LeetCode）
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function (root) {
let result = 0
const dfs = (node, path) => {
if (!node) return
path += node.val
if (!node.left && !node.right) {
result += Number(path)
return
}
dfs(node.left, path)
dfs(node.right, path)
}
dfs(root, "")
return result
};93. 复原 IP 地址 - 力扣（LeetCode）
三叉决策树结合回溯
function restoreIpAddresses(s: string): string[] {
const res: string[] = []
const temp: string[] = []
function dfs(subStr: string) {
// 如果结果数组达到四位且字符串没有切割完的情况下或者字符串切割完但结果数组达不到四位的情况下跳出
if ((temp.length == 4 && subStr.length > 0) || (subStr.length == 0 && temp.length < 4)) return
// 字符串切割完，结果数组长度也等于4表示合法ip地址
if (subStr.length == 0 && temp.length == 4) {
res.push(temp.join('.'))
return
}
// 遍历切割方案
for (let i = 1; i <= 3; ++i) {
// 如果i大于subStr.length再切割得到的str1就等于切割的subStr.length和之前的重复就跳出
if (i > subStr.length) break
const str1 = subStr.slice(0, i)
const str2 = subStr.slice(i, subStr.length)
// 如果str1不等于0并且以0开头则跳出
if (str1.length > 1 && str1.startsWith('0')) break
if (parseInt(str1) <= 255) {
temp.push(str1)
dfs(str2)
temp.pop()
}
}
}
dfs(s)
return res
};322. 零钱兑换 - 力扣（LeetCode）
回溯超时，需要使用自上而下的动态规划，设置一个dp数组，对每一项索引为i的值任取一枚面值为coin的硬币均符合dp[i-coin]，后面的每一项都利用前一步的计算结果
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(amount + 1)
dp[0] = 0
for (let i = 1; i <= amount + 1; ++i) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount]
};22. 括号生成 - 力扣（LeetCode）
直接全部变量并对每一项进行括号合法判断超时 使用剪枝回溯，当左括号数量小于组数n时就可以添加左括号，当右括号小于左括号数时才可添加右括号，选择性的生成
function generateParenthesis(n: number): string[] {
const res: string[] = []
let temp = ''
function dfs(temp: string, left: number, right: number) {
if (left >= n && right >= n) {
res.push(temp)
return
}
if (left < n) {
dfs(temp + '(', left + 1, right)
}
if (left > right) {
dfs(temp + ')', left, right + 1)
}
}
dfs(temp, 0, 0)
return res
};LCR 140. 训练计划 II
快慢指针，让慢指针落后cnt位，当快指针为null时慢指针达到倒数第cnt位
function trainingPlan(head: ListNode | null, cnt: number): ListNode | null {
let fast = head
let slow = head
for (let i = 0; i < cnt; ++i) {
if (fast === null) {
return null
} else {
fast = fast.next
}
}
while (fast !== null) {
fast = fast.next
slow = slow!.next
}
return slow
};104. 二叉树的最大深度 - 力扣（LeetCode）
function maxDepth(root: TreeNode | null): number {
let res = 0
function dfs(node: TreeNode | null, deep: number) {
if (!node) {
res = Math.max(res, deep)
return
}
dfs(node.left,deep+1)
dfs(node.right,deep+1)
}
dfs(root,0)
return res
};不使用递归需要借助一个栈存储节点实现
function inorderTraversal(root: TreeNode | null): number[] {
const res: number[] = []
const temp: TreeNode[] = []
let cur = root
while (cur || temp.length > 0) {
while (cur) {
temp.push(cur)
cur = cur.left
}
cur = temp.pop()!
res.push(cur.val)
cur = cur.right
}
return res
};LCR 126. 斐波那契数 - 力扣（LeetCode）
直接递归会导致重复计算过长超时，需要对之前的结果进行缓存
function fib(n: number): number {
if (n === 0) return 0
if (n === 1) return 1
if (n === 2) return 1
let pre1 = 0
let pre2 = 1
for (let i = 2; i < n; ++i) {
const temp = pre2 % 1000000007
pre2 += pre1
pre1 = temp
}
return (pre1 + pre2) % 1000000007
};695. 岛屿的最大面积 - 力扣（LeetCode）
解法和岛屿数量相似
function maxAreaOfIsland(grid: number[][]): number {
let area = 0
let temp=0
function dfs(x: number, y: number) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 0) {
return
} else {
grid[x][y]=0
++temp
dfs(x, y - 1)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x + 1, y)
}
}
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[0].length; ++j) {
if (grid[i][j] === 1) {
temp=0
dfs(i, j)
area=Math.max(area,temp)
}
}
}
return area
};42. 接雨水 - 力扣（LeetCode）
对任意一个位置，它可以承载的水量等于它左边最高和右边最高中取最小值减去它本身的高度
function trap(height: number[]): number {
const left: number[] = Array.from(height) // 左边最高柱子
const right: number[] = Array.from(height) //右边最高柱子
let water = 0
for (let i = 1; i < height.length; ++i) {
left[i] = Math.max(left[i - 1], left[i])
}
for (let i = height.length - 2; i >= 0; --i) {
right[i] = Math.max(right[i + 1], right[i])
}
for (let i = 0; i < height.length; ++i) {
water += Math.min(left[i], right[i]) - height[i]
}
return water
};1143. 最长公共子序列 - 力扣（LeetCode）
二维动态规划 dp表行数是第一个字符串的长度+1，列数是第二个字符串的长度+1，第0行和第0列的值都为0表示空字符串的情况，表格中dp[i][j]代表第一个字符的前i个字符和第二个字符串的前j个字符的最长公共子序列长度。如果s1[i]===s2[j]则dp[i][j]赋值为dp[i-1][j-1]+1也就是它左上角各自最长公共子序列长度+1表示发现了新的匹配字符，如果不想等则dp[i][j]赋值为max(dp[i-1][j],dp[i][j-1])去左边或上边的最大值表示跳过当前字符，依次把整张表填完，结果即为dp表右下角的值 
function longestCommonSubsequence(text1: string, text2: string): number {
const dp: number[][] = []
// 填充数组
for (let i = 0; i < text1.length + 1; ++i) {
dp.push(new Array(text2.length + 1).fill(0))
}
// 动态规划
for (let i = 1; i < text1.length + 1; ++i) {
for (let j = 1; j < text2.length + 1; ++j) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
console.log(dp)
return dp[text1.length][text2.length]
};贡献者
PinkDopeyBug版权所有
版权归属：
