Hot100
发表于:2024-12-11
字数统计:18120 字
预计阅读61分钟
哈希
1. 两数之和
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map()
for(let i = 0; i < nums.length; i++) {
if(map.has(target - nums[i])) {
return [map.get(target - nums[i]), i]
} else {
map.set(nums[i], i)
}
}
return [1, 1]
};49. 字母异位词分组
js
/**
* @param {string[]} strs
* @return {string[][]}
*/
// sort
var groupAnagrams = function(strs) {
const strs1 = strs.map(item => item.split('').sort((a,b) => a.charCodeAt() - b.charCodeAt()).join(''))
const map = new Map()
let result = []
for(let i = 0; i < strs.length; i++) {
if(!map.has(strs1[i])) {
map.set(strs1[i], [strs[i]])
} else {
map.set(strs1[i], [...map.get(strs1[i]), strs[i]])
}
}
result = [...map.values()]
return result
};128. 最长连续序列
js
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
const map = new Map()
let ans = 0
let result = 0
for(let i = 0; i < nums.length; i++) {
map.set(nums[i], 1)
}
for(let i = 0; i < nums.length; i++) {
if(map.has(nums[i] + 1)) continue
while(map.has(nums[i] - ans)) {
ans++
}
result = Math.max(result, ans)
ans = 0
}
return result
};双指针
283. 移动零
js
var moveZeroes = function(nums) {
let slow = 0, fast = 0
for(; fast < nums.length; fast++) {
if(nums[fast] !== 0) {
let tmp = nums[fast]
nums[fast] = nums[slow]
nums[slow] = tmp
slow++
}
}
};js
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let slow = 0, fast = 0
for(; fast < nums.length; fast++) {
if(nums[fast] !== 0) {
nums[slow] = nums[fast]
slow++
}
}
for(; slow < nums.length; slow++) {
nums[slow] = 0
}
};11. 盛最多水的容器
js
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let ans = 0, left = 0, right = height.length - 1
while(left < right) {
const area = (right - left) * Math.min(height[left], height[right])
ans = Math.max(ans, area)
if (height[left] < height[right]) {
left++
}else {
right--
}
}
return ans
};15. 三数之和
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const set = new Set()
const result = []
nums.sort((a,b) => a-b)
for(let i = 0; i < nums.length; i++) {
let left = i + 1
let right = nums.length - 1
while(left < right) {
const sum = nums[i] + nums[left] + nums[right]
if(sum > 0) {
right--
} else if (sum < 0) {
left++
} else {
const ans = [nums[i], nums[left], nums[right]]
const str = ans.join(',')
if(!set.has(str)) {
set.add(str)
result.push(ans)
}
right--
left++
}
}
}
return result
};js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const result = []
nums.sort((a,b) => a-b)
for(let i = 0; i < nums.length; i++) {
let left = i + 1
let right = nums.length - 1
if(i > 0 && nums[i] === nums[i-1]) continue
while(left < right) {
const sum = nums[i] + nums[left] + nums[right]
if(sum > 0) {
right--
} else if (sum < 0) {
left++
} else {
const n1 = nums[left]
const n2 = nums[right]
result.push([nums[i], n1, n2])
while(left < right && n1 === nums[left]) {
left++
}
while(left < right && n2 === nums[right]) {
right--
}
}
}
}
return result
};42. 接雨水
go
//暴力解法
var trap = function(height) {
const len = height.length;
let sum = 0;
for(let i = 0; i < len; i++){
// 第一个柱子和最后一个柱子不接雨水
if(i == 0 || i == len - 1) continue;
let rHeight = height[i]; // 记录右边柱子的最高高度
let lHeight = height[i]; // 记录左边柱子的最高高度
for(let r = i + 1; r < len; r++){
if(height[r] > rHeight) rHeight = height[r];
}
for(let l = i - 1; l >= 0; l--){
if(height[l] > lHeight) lHeight = height[l];
}
let h = Math.min(lHeight, rHeight) - height[i];
if(h > 0) sum += h;
}
return sum;
};
//双指针
var trap = function(height) {
const len = height.length;
if(len <= 2) return 0;
const maxLeft = new Array(len).fill(0);
const maxRight = new Array(len).fill(0);
// 记录每个柱子左边柱子最大高度
maxLeft[0] = height[0];
for(let i = 1; i < len; i++){
maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
}
// 记录每个柱子右边柱子最大高度
maxRight[len - 1] = height[len - 1];
for(let i = len - 2; i >= 0; i--){
maxRight[i] = Math.max(height[i], maxRight[i + 1]);
}
// 求和
let sum = 0;
for(let i = 0; i < len; i++){
let count = Math.min(maxLeft[i], maxRight[i]) - height[i];
if(count > 0) sum += count;
}
return sum;
};
//单调栈 js数组作为栈
var trap = function(height) {
const len = height.length;
if(len <= 2) return 0; // 可以不加
const st = [];// 存着下标，计算的时候用下标对应的柱子高度
st.push(0);
let sum = 0;
for(let i = 1; i < len; i++){
if(height[i] < height[st[st.length - 1]]){ // 情况一
st.push(i);
}
if (height[i] == height[st[st.length - 1]]) { // 情况二
st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
st.push(i);
} else { // 情况三
while (st.length !== 0 && height[i] > height[st[st.length - 1]]) { // 注意这里是while
let mid = st[st.length - 1];
st.pop();
if (st.length !== 0) {
let h = Math.min(height[st[st.length - 1]], height[i]) - height[mid];
let w = i - st[st.length - 1] - 1; // 注意减一，只求中间宽度
sum += h * w;
}
}
st.push(i);
}
}
return sum;
};
//单调栈 简洁版本 只处理情况三
var trap = function(height) {
const len = height.length;
if(len <= 2) return 0; // 可以不加
const st = [];// 存着下标，计算的时候用下标对应的柱子高度
st.push(0);
let sum = 0;
for(let i = 1; i < len; i++){ // 只处理的情况三，其实是把情况一和情况二融合了
while (st.length !== 0 && height[i] > height[st[st.length - 1]]) { // 注意这里是while
let mid = st[st.length - 1];
st.pop();
if (st.length !== 0) {
let h = Math.min(height[st[st.length - 1]], height[i]) - height[mid];
let w = i - st[st.length - 1] - 1; // 注意减一，只求中间宽度
sum += h * w;
}
}
st.push(i);
}
return sum;
};
// 双指针2
var trap = function(height) {
let ans = 0, left = 0, right = height.length - 1, preMax = 0, sufMax = 0
while(left < right) {
preMax = Math.max(preMax, height[left])
sufMax = Math.max(sufMax, height[right])
if(preMax < sufMax) {
ans += preMax - height[left]
left++
} else {
ans += sufMax - height[right]
right--
}
}
return ans
}滑动窗口
3. 无重复字符的最长子串
js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0, ans = 0
const set = new Set()
for(let right = 0; right < s.length; right++) {
if(!set.has(s[right])) {
set.add(s[right])
ans = Math.max(ans, set.size)
} else {
// 一直删，直到刚好没left
while(set.has(s[right])) {
set.delete(s[left])
left++
}
}
set.add(s[right])
}
return ans
};js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0, ans = 0
const set = new Set()
for(let right = 0; right < s.length; right++) {
// 一直删，直到刚好没left
while(set.has(s[right])) {
set.delete(s[left])
left++
}
set.add(s[right])
ans = Math.max(ans, set.size)
}
return ans
};438. 找到字符串中所有字母异位词
js
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function(s, p) {
let ans = [], left = 0, pn = p.length, right =0
const sCount = Array(26).fill(0)
const pCount = Array(26).fill(0)
const aCode = 'a'.charCodeAt()
for(let i = 0; i < pn; i++) {
pCount[p[i].charCodeAt() - aCode]++
}
while(right < s.length) {
sCount[s[right].charCodeAt() - aCode]++
if(right - left === pn - 1) {
// 判断
if(sCount.join('') === pCount.join('')) {
ans.push(left)
}
sCount[s[left].charCodeAt() - aCode]--
left++
}
right++
}
return ans
};子串
560. 和为 K 的子数组
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 前缀和
// 一段子数组的和为：数组末端的前缀和减去数组开头的前缀
var subarraySum = function(nums, k) {
let preSum = 0, ans = 0;
const map = new Map();
map.set(0, 1);
for(let num of nums) {
preSum += num
if(map.has(preSum - k)) {
ans += map.get(preSum - k)
}
map.set(preSum, (map.get(preSum) || 0) + 1)
}
console.log(map)
return ans
};239. 滑动窗口最大值
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const ans = [], q = []
for(let i = 0; i < nums.length; i++) {
// 维护队列单调递减
while(q.length && nums[i] > nums[q[q.length-1]]) {
q.pop()
}
q.push(i)
if(i - q[0] >= k) {
q.shift()
}
if(i >= k - 1) {
ans.push(nums[q[0]])
}
}
return ans
};76. 最小覆盖子串
js
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
function minWindow1(s, t) {
if (!s || !t) return "";
// 记录 t 中每个字符的出现次数
const tCount = new Map();
for (let char of t) {
tCount.set(char, (tCount.get(char) || 0) + 1);
}
const currentCount = new Map();
let left = 0;
let minLength = Infinity;
let minWindow = "";
let required = tCount.size;
let formed = 0;
// 移动右指针
for (let right = 0; right < s.length; right++) {
let currentChar = s[right];
currentCount.set(currentChar, (currentCount.get(currentChar) || 0) + 1);
// 检查 currentChar 是否是 t 中的字符并且当前窗口中该字符数量符合要求
if (tCount.has(currentChar) && currentCount.get(currentChar) === tCount.get(currentChar)) {
formed++;
}
// 缩小窗口
while (left <= right && formed === required) {
let windowLength = right - left + 1;
if (windowLength < minLength) {
minLength = windowLength;
minWindow = s.slice(left, right + 1);
}
// 移出左边字符
let leftChar = s[left];
currentCount.set(leftChar, currentCount.get(leftChar) - 1);
if (tCount.has(leftChar) && currentCount.get(leftChar) < tCount.get(leftChar)) {
formed--;
}
left++;
}
}
return minWindow;
}
function minWindow2(s, t) {
// 初始化
let i = 0, j = 0;
let needMap = new Map();
let needCnt = t.length;
let res = '';
// 初始化 needMap
for (let char of t) {
needMap.set(char, (needMap.get(char) || 0) + 1);
}
// 移动滑窗右边界
while (j < s.length) {
// 判断是否满足条件
if (needMap.has(s[j])) {
if (needMap.get(s[j]) > 0) {
needCnt -= 1;
}
needMap.set(s[j], needMap.get(s[j]) - 1);
}
// 一旦满足条件，尽可能地压缩 i，并且不断更新结果
while (needCnt === 0) {
if (!res || j - i + 1 < res.length) {
res = s.slice(i, j + 1);
}
if (needMap.has(s[i])) {
if (needMap.get(s[i]) === 0) {
needCnt += 1;
}
needMap.set(s[i], needMap.get(s[i]) + 1);
}
i += 1;
}
j += 1;
}
return res;
}
function minWindow(s, t) {
let left = 0, right = 0, rc = 0, c = 0, ans = ''
const tmap = new Map()
const smap = new Map()
// 记录t所需要的字符
for(let char of t) tmap.set(char, (tmap.get(char) || 0 )+ 1)
// required count
rc = tmap.size
// 开始滑动窗口逻辑
// 最短型滑动窗口，优先收敛（移动左指针）
while(right < s.length) {
const char = s[right]
smap.set(char, (smap.get(char) || 0 ) + 1)
if(tmap.has(char) && smap.get(char) === tmap.get(char)) {
c++
}
while(left <= right && rc === c) {
let len = right - left + 1
if(len < ans.length || ans.length === 0) {
ans = s.slice(left, right+1)
}
// 推出队首
const leftchar = s[left]
smap.set(leftchar, (smap.get(leftchar) || 0) - 1)
left++
if(tmap.has(leftchar) && smap.get(leftchar) < tmap.get(leftchar)) {
c--
}
}
right++
}
return ans
}普通数组
53. 最大子数组和
js
/**
* @param {number[]} nums
* @return {number}
*/
// 动态规划
var maxSubArray = function(nums) {
const dp = Array(nums.length).fill(-Infinity)
dp[0] = nums[0]
let max = dp[0]
for(let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
max = Math.max(max, dp[i])
}
return max
};
// 贪心
var maxSubArray = function(nums) {
let result = -Infinity
let sum = 0
for(let i = 0; i < nums.length; i++) {
sum += nums[i]
if(sum > result) {
result = sum
}
if(sum < 0) {
sum = 0
}
}
return result
}56. 合并区间
js
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
intervals.sort((a,b) => a[0] - b[0])
const result = []
intervals.push([Infinity, Infinity])
for(let i = 0; i < intervals.length-1; i++) {
const [al, ar] = intervals[i]
const [bl, br] = intervals[i+1]
// 不重叠
if(ar < bl) {
result.push(intervals[i])
} else {
// 处理重叠区间
delete intervals[i]
intervals[i+1] = [al, Math.max(ar, br)]
}
}
return result
};189. 轮转数组
js
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate1 = function(nums, k) {
k = k % nums.length
const s1 = nums.slice(nums.length - k)
const s2 = nums.slice(0, nums.length - k)
console.log(s1, s2)
while(nums.length) nums.pop()
nums.unshift(...s1, ...s2)
};
var rotate = function(nums, k) {
function reverse(left, right) {
while(left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]]
left++
right--
}
}
const n = nums.length
k %= n
reverse(0, n-1)
reverse(0, k-1)
reverse(k, n-1)
};238. 除自身以外数组的乘积
js
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
const prefix = Array(nums.length).fill(1)
const suffix = Array(nums.length).fill(1)
const result = Array(nums.length).fill(0)
for(let i = 1; i < nums.length; i++) {
prefix[i] = prefix[i-1] * nums[i-1]
}
for(let j = nums.length - 2; j >= 0; j--) {
suffix[j] = suffix[j+1] * nums[j+1]
}
for(let i = 0; i < nums.length; i++) {
result[i] = prefix[i] * suffix[i]
}
return result
};41. 缺失的第一个正数
js
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
let n = nums.length
for(let i = 0; i < n; i++) {
while(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] !== nums[i]) {
let tmp = nums[nums[i]-1]
nums[nums[i]-1] = nums[i]
nums[i] = tmp
}
}
for(let i = 0; i <n ;i++) {
if(nums[i] !== i+1) return i+1
}
return n+1
};矩阵
73. 矩阵置零
js
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const handle = []
const n = matrix.length
const m = matrix[0].length
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
if(matrix[i][j] === 0) {
handle.push([i,j])
}
}
}
for(let k = 0; k < handle.length; k++) {
const [i, j] = handle[k]
for(let i1 = 0; i1 < n; i1++) {
matrix[i1][j] = 0
}
for(let j1 = 0; j1 < m; j1++) {
matrix[i][j1] = 0
}
}
};54. 螺旋矩阵
js
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
const n = matrix.length
const m = matrix[0].length
let l = 0, r = m - 1, t = 0, b = n - 1
const result = []
while(l <= r && t <= b) {
// 向右
for(let i = l; i <= r; i++) {
result.push(matrix[t][i])
}
t++
// 向下
for(let j = t; j <= b; j++) {
result.push(matrix[j][r])
}
r--
if(l > r || t > b) break
// 向左
for(let k = r; k >= l; k--) {
result.push(matrix[b][k])
}
b--
// 向上
for(let h = b; h >= t; h--) {
result.push(matrix[h][l])
}
l++
}
return result
};48. 旋转图像
js
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
const n = matrix.length
// matrix[i][j] = matrix[j][n-i-1]
for(let i = 0; i < Math.floor(n / 2); i++) {
for(let j = 0; j < Math.floor((n+1) / 2) ; j++) {
let tmp = matrix[i][j]
matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = tmp
}
}
};
作者：Krahets
240. 搜索二维矩阵 II
js
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
// 盲目递归
var searchMatrix = function(matrix, target) {
const m = matrix.length
const n = matrix[0].length
function dfs(i, j) {
if(i >= m || j >= n) return false
if(matrix[i][j] === target) return true
else if (matrix[i][j] < target) {
return dfs(i+1,j) || dfs(i,j+1)
} else {
return false
}
}
return dfs(0, 0)
};
// z型搜索
var searchMatrix = function(matrix, target) {
const n = matrix.length
const m = matrix[0].length
let i = 0, j = m-1
while(i < n && j >= 0) {
console.log(matrix[i][j])
if(matrix[i][j] > target) {
j--
} else if (matrix[i][j] < target) {
i++
} else {
return true
}
}
return false
}链表
160. 相交链表
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let pa = headA, pb = headB
while(pa !== pb) {
pa = pa ? pa.next : headB
pb = pb ? pb.next : headA
}
return pa
};206. 反转链表
js
/**
* 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 pre = null, cur = head
while(cur) {
let tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
}
return pre
};234. 回文链表
js
/**
* 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 {boolean}
*/
var isPalindrome = function(head) {
const mid = middleNode(head)
let head2 = reverseList(mid)
while(head2 !== null) {
if(head.val !== head2.val) {
return false
}
head = head.next
head2 = head2.next
}
return true
};
function middleNode(head) {
let slow = head, fast = head
while(fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
}
return slow
}
function reverseList(head) {
let pre = null, cur = head
while(cur) {
const nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
}
return pre
}141. 环形链表
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let slow = head, fast = head
while(fast && fast.next) {
fast = fast.next.next
slow = slow.next
if(fast === slow) return true
}
return false
};142. 环形链表 II
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let slow = head, fast = head
while(fast && fast.next) {
slow = slow.next
fast = fast.next.next
if(slow === fast) {
// 现在仅说明有环，接着要找到相遇点（环的入口）
// 如果有环，那么入口被head来的和环的末尾同时指着
// 快慢指针会精准找到与入口步差为n（n为head到环入口）的的环内指针
// 然后就可以用下面
let p1 = head
let p2 = fast
while(p1 !== p2) {
p1 = p1.next
p2 = p2.next
}
return p1
}
}
return null
};21. 合并两个有序链表
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists1 = function(list1, list2) {
return mergeHelper(list1, list2)
function mergeHelper(l1, l2) {
if(!l1) return l2
if(!l2) return l1
if(l1.val < l2.val) {
l1.next = mergeHelper(l1.next, l2)
return l1
} else {
l2.next = mergeHelper(l1, l2.next)
return l2
}
}
};
var mergeTwoLists = function(list1, list2) {
const dummyHead = new ListNode(0)
let cur = dummyHead
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 ? list1 : list2
return dummyHead.next
};
var mergeTwoLists = function(list1, list2) {
const dhead = new TreeNode(0)
let cur = dhead
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 ? list1 : list2
return dhead.next
};2. 两数相加
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
const dhead = new ListNode(0)
let p1 = l1, p2 = l2, p3 = dhead, carry = 0
while(p1 || p2 || carry) {
let val = 0
if(p1) {
val += p1.val
p1 = p1.next
}
if(p2) {
val += p2.val
p2 = p2.next
}
p3.next = new ListNode((val + carry) % 10)
carry = Math.floor((val + carry) / 10)
p3 = p3.next
}
return dhead.next
};19. 删除链表的倒数第 N 个结点
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let dummyHead = new ListNode(0, head)
let slow = dummyHead, fast = dummyHead
// 先走n步，使得使得slow少走n步
while(n--) {
fast = fast.next
}
// 让fast到结尾，使得slow定位到倒数第N个节点的前一个（因为有dummyHead）
while(fast.next) {
fast = fast.next
slow = slow.next
}
// 执行删除逻辑
slow.next = slow.next.next
return dummyHead.next
};24. 两两交换链表中的节点
js
/**
* 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 swapPairs = function(head) {
let dummyHead = new ListNode(0, head)
let cur = dummyHead
while(cur && cur.next && cur.next.next) {
let cur1 = cur.next
let cur2 = cur.next.next
cur1.next = cur2.next
cur2.next = cur1
cur.next = cur2
cur = cur.next.next
}
return dummyHead.next
};js
/**
* 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 swapPairs = function(head) {
let dummyHead = new ListNode(0)
dummyHead.next = head
let cur = dummyHead
while(cur.next && cur.next.next) {
let tmp = cur.next
let tmp1 = cur.next.next.next
cur.next = cur.next.next
cur.next.next = tmp
cur.next.next.next = tmp1
cur = cur.next.next;
}
let result = dummyHead.next
delete dummyHead
return result
};25. K 个一组翻转链表
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
// 求个长度
let n = 0, phelper = head
while(phelper) {
phelper = phelper.next
n++
}
// 92. 反转链表 II
const dummyHead = new ListNode(0, head)
let p0 = dummyHead, cur, pre
pre = null
cur = p0.next
while(n >= k) {
for(let i = 0; i < k; i++) {
let nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
}
let nxt = p0.next
p0.next.next = cur
p0.next = pre
p0 = nxt
n -= k
}
return dummyHead.next
};138. 随机链表的复制
交错链表法
js
/**
* // Definition for a _Node.
* function _Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/**
* @param {_Node} head
* @return {_Node}
*/
// 复制到原链表，然后通过奇偶链表导出
var copyRandomList = function(head) {
if(!head) return null
// 复制每个节点，将新节点插入到原节点的后面
for(let cur = head; cur; cur = cur.next.next) {
// 我看灵神这里不用tmp存储，但是总感觉这里会有问题
let nxt = cur.next
cur.next = new _Node(cur.val, nxt, null)
}
// 交错遍历，设置random指针
for(let cur = head; cur; cur = cur.next.next) {
if(cur.random) {
// cur.random是指回去，cur.random.next才是正确的内容
cur.next.random = cur.random.next
}
}
// 将交错链表分离成两个链表
// 1 -> 1' -> 2 -> 2' -> 3 -> 3'
const newHead = head.next // 1'
let cur = head // 1
for(; cur.next.next; cur = cur.next) {
const copy = cur.next // 1'
cur.next = copy.next // 1 -> 2
copy.next = copy.next.next // 1' -> 2'
}
cur.next = null // 3 -> null
return newHead
};148. 排序链表
js
/**
* 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 sortList = function(head) {
if(!head || !head.next) {
return head
}
// 找到中间节点，又包含了断开逻辑
let head2 = middleNode(head)
// 分治
head = sortList(head)
head2 = sortList(head2)
// 合并
return mergeTwoLists(head, head2)
};
// 876. find middle node
function middleNode(head) {
let slow = head, fast = head
// 这里处理比较特殊，需要找到中间节点的前一个，否则分治会出现问题
while(fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
// 独特的断开逻辑，否则会栈溢出
let mid = slow.next
slow.next = null
return mid
}
// 21. merge two list
function mergeTwoLists(list1, list2) {
const dummyHead = new ListNode(0)
let cur = dummyHead
dummyHead.next = list1
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 ? list1 : list2
return dummyHead.next
}23. 合并 K 个升序链表
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
while(lists.length >= 2) {
let list = mergeTwoLists(lists[0], lists[1])
lists.shift()
lists.shift()
lists.unshift(list)
}
return lists[0] || null
};
// 合并两个升序链表
function mergeTwoLists(list1, list2) {
const dummyHead = new ListNode()
let cur = dummyHead
dummyHead.next = list1
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 ? list1 : list2
return dummyHead.next
}146. LRU 缓存
未完成
二叉树
94. 二叉树的中序遍历
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const result = []
dfs(root)
return result
function dfs(node) {
if(!node) return
dfs(node.left)
result.push(node.val)
dfs(node.right)
}
};104. 二叉树的最大深度
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(!root) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
var maxDepth = function(root) {
const q = [root]
let count = 0
if(!root) return count
while(q.length) {
const len = q.length
for(let i = 0; i < len; i++) {
const node = q.shift()
if(node.left) q.push(node.left)
if(node.right) q.push(node.right)
}
count++
}
return count
}226. 翻转二叉树
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if(!root) return null
const tmp = root.left
root.left = root.right
root.right = tmp
invertTree(root.left)
invertTree(root.right)
return root
};
var invertTree1 = function(root) {
const queue = []
if(!root) return root
queue.push(root)
while(queue.length) {
const length = queue.length
for(let i = 0; i < length; i++) {
let node = queue.shift()
// 交换
let tmp = node.left
node.left = node.right
node.right = tmp
// 遍历
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
}
return root
};
var invertTree = function(root) {
const stack = []
if(!root) return root
stack.push(root)
while(stack.length) {
const node = stack.pop()
// 交换
let tmp = node.left
node.left = node.right
node.right = tmp
// 迭代
node.left && stack.push(node.left)
node.right && stack.push(node.right)
}
return root
};101. 对称二叉树
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
const q = [root]
if(!root) return false
while(q.length) {
let len = q.length
const arr = []
for(let i = 0; i < len; i++) {
let node = q.shift()
if(node) {
arr.push(node.val)
q.push(node.left)
q.push(node.right)
} else {
node = new TreeNode(101, null, null)
arr.push(node.val)
}
}
if(arr.toString() !== arr.reverse().toString()) return false
}
return true
};
var isSymmetric = function(root) {
return traverseHelper(root.left, root.right)
function traverseHelper(l, r) {
// 都没有
if(!l && !r) return true
// 只有一个
if((!l && r) || (l && !r)) return false
// 两个都有
return l.val === r.val && traverseHelper(l.left, r.right) && traverseHelper(l.right, r.left)
}
};543. 二叉树的直径
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
let ans = 0
getNodeDepth(root)
return ans
function getNodeDepth (node) {
if (node === null) {
return -1
}
const leftDepth = getNodeDepth(node.left)
const rightDepth = getNodeDepth(node.right)
ans = Math.max(ans, leftDepth + rightDepth + 2)
return Math.max(leftDepth, rightDepth) + 1
}
};102. 二叉树的层序遍历
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
const q = [root], result = []
if(!root) return result
while(q.length) {
const len = q.length
const curLevel = []
for(let i = 0; i < len; i++) {
const node = q.shift()
curLevel.push(node.val)
if(node.left) q.push(node.left)
if(node.right) q.push(node.right)
}
result.push(curLevel)
}
return result
};108. 将有序数组转换为二叉搜索树
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST1 = function(nums) {
if (!nums || nums.length === 0) {
return null;
}
const midPosition = nums.length / 2 | 0
// 构建节点
const root = new TreeNode(nums[midPosition])
root.left = sortedArrayToBST(nums.slice(0, midPosition))
root.right = sortedArrayToBST(nums.slice(midPosition + 1))
return root
};
var sortedArrayToBST = function(nums) {
if(!nums.length) return null
const mid = nums.length / 2 | 0
const node = new TreeNode(nums[mid])
node.left = sortedArrayToBST(nums.slice(0, mid))
node.right = sortedArrayToBST(nums.slice(mid + 1))
return node
};
var sortedArrayToBST = function(nums) {
if (!nums || nums.length === 0) {
// 源数组为0，或者nums被处理过之后为null
return null;
}
const midPosition = nums.length / 2 | 0
// 构建节点
const root = new TreeNode(nums[midPosition], sortedArrayToBST(nums.slice(0, midPosition)), sortedArrayToBST(nums.slice(midPosition + 1)))
return root
};98. 验证二叉搜索树
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
let max = -Infinity
return traverse(root)
// 这个代码没有认识到二叉搜索树的性质，比如右节点的所有值都应该小于当前节点，是包含祖先节点的
function traverseCUOLE(node) {
if(!node) return true
if(!node.left && !node.right) return true
let left = true, right = true
if(node.left) {
if(node.left.val < node.val) left = traverseCUOLE(node.left)
else return false
}
if(node.right) {
if(node.right.val > node.val) right = traverseCUOLE(node.right)
else return false
}
return left && right
}
// 二叉搜索树的顺序就是中序遍历的顺序，所以可以用中序遍历判断它是不是单调递增的
function traverse(node) {
if(!node) return true
// 左、中、右
let left = traverse(node.left)
// 处理中逻辑，max使得单调递增，成立就是继续向下探
if(max < node.val) max = node.val
else return false
let right = traverse(node.right)
return left && right
}
};230. 二叉搜索树中第 K 小的元素
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
// 因为是二叉搜索树，所以是中序遍历的第k个
var kthSmallest = function(root, k) {
const result = []
traverse(root)
return result[k-1]
function traverse(node) {
if(result.length >= k) return
if(!node) return
// 左、中、右
traverse(node.left)
result.push(node.val)
traverse(node.right)
}
};199. 二叉树的右视图
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
const q = [root], result = []
if(!root) return result
while(q.length) {
const len = q.length
const curLevel = []
for(let i = 0; i < len; i++) {
const node = q.shift()
curLevel.push(node.val)
if(node.left) q.push(node.left)
if(node.right) q.push(node.right)
}
result.push(curLevel[curLevel.length-1])
}
return result
};114. 二叉树展开为链表
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
const result = []
pretraverse(root)
for(let i = 0; i < result.length; i++) {
const node = result[i]
node.left = null
node.right = result[i+1] || null
}
function pretraverse(node) {
if(!node) return
result.push(node)
if(node.left) pretraverse(node.left)
if(node.right) pretraverse(node.right)
}
};
// Morris 遍历
var flatten = function(root) {
let current = root;
while (current) {
if (current.left) {
// 找到左子树的最右节点
let rightmost = current.left;
while (rightmost.right) {
rightmost = rightmost.right;
}
// 将原来的右子树接到左子树的最右节点
rightmost.right = current.right;
// 将左子树变为右子树，左子树置为 null
current.right = current.left;
current.left = null;
}
// 移动到下一个节点
current = current.right;
}
};105. 从前序与中序遍历序列构造二叉树
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
// 中序：左中右
// 前序：中左右
var buildTree = function(preorder, inorder) {
return traverse(preorder, inorder)
function traverse(preorder, inorder) {
// 退出条件
if(!preorder.length) return null
let node = preorder[0]
// 根据前序中节点切割中序
let index = inorder.indexOf(node)
let left = inorder.slice(0, index)
let right = inorder.slice(index+1)
// 根据切割后的中序，切割前序
let pleft = [], pright
pleft = preorder.slice(1, left.length + 1)
pright = preorder.slice(left.length + 1)
node = new TreeNode(node)
node.left = traverse(pleft, left)
node.right = traverse(pright, right)
console.log(left, right, pleft, pright)
return node
}
};437. 路径总和 III
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number}
*/
// 按路径，处理每个节点从根节点向下到当下节点的前缀和
// 这段代码有错，总是有十几个用例不通过，是因为哈希表的更新不按照路径，在计算时，有可能使用了其他路径的前缀和，应该加上回溯逻辑，将更改的状态撤销
var pathSum = function(root, targetSum) {
if(!root) return 0
const map = new Map()
let count = 0
map.set(0, 1)
traverseHelper(root, root.val)
return count
function traverseHelper(node, sum) {
if(map.has(sum - targetSum)) {
count += map.get(sum - targetSum)
}
map.set(sum, (map.get(sum) || 0) + 1)
if(node.left) traverseHelper(node.left, sum + node.left.val)
if(node.right) traverseHelper(node.right, sum + node.right.val)
map.set(sum, map.get(sum) - 1) // 回溯逻辑
}
};
var pathSum1 = function(root, targetSum) {
const map = new Map();
map.set(0, 1); // 初始化前缀和为0的路径数为1
let count = 0;
function traverse(node, currentSum) {
if (!node) return;
currentSum += node.val;
// 检查是否存在满足条件的路径
if (map.has(currentSum - targetSum)) {
count += map.get(currentSum - targetSum);
}
// 更新前缀和出现的次数
map.set(currentSum, (map.get(currentSum) || 0) + 1);
// 递归遍历左右子树
traverse(node.left, currentSum);
traverse(node.right, currentSum);
// 回溯，恢复状态
map.set(currentSum, map.get(currentSum) - 1);
}
traverse(root, 0);
return count;
};236. 二叉树的最近公共祖先
js
// 后序遍历就是回溯逻辑，自底而上，自然找到最近公共祖先
var lowestCommonAncestor = function(root, p, q) {
return posttraverse(root)
function posttraverse(node) {
// 这里，用left.val和right.val判断这些值会有点繁琐，所以用本身的值判断为上
if(!node) return null
if(node === p || node === q) return node
let left = posttraverse(node.left)
let right = posttraverse(node.right)
// left 和 right的可能，要么是p\q中的一个，要么是null
if(left && right) return node
return left || right
}
};124. 二叉树中的最大路径和
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
// 决定使用posttraverse，自底而上向上，使用递归分解问题
var maxPathSum = function(root) {
let ans = -Infinity
posttraverse(root)
return ans
function posttraverse(node) {
// 后序逻辑：左、右、中
if(!node) return 0
let left = posttraverse(node.left)
let right = posttraverse(node.right)
// 这个属于处理中逻辑
// if(node.val <= 0) node.val = -Infinity // 这一句是错的，返回的时候可以变成0或者负数表选择，但是自己参与选择的时候不能为0，否则会这个node没有阻拦效果
// 处理中节点，核心逻辑是加上自己，返回回去
ans = Math.max(ans, left + right + node.val)
// console.log(ans, Math.max(left, right) + node.val)
const sum = Math.max(left, right) + node.val
return sum > 0 ? sum : 0
}
};图论
200. 岛屿数量
js
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
const m = grid.length
const n = grid[0].length
let count = 0
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(grid[i][j] === '1') {
dfs(i, j)
count++
}
}
}
return count
function dfs(i, j) {
// 进入是，一定是'1'
if(i >= m || j >= n || i < 0 || j < 0) return
if(grid[i][j] === '0') return
if(grid[i][j] === '1') grid[i][j] = '0'
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
}
};994. 腐烂的橘子
BFS还不是很熟
js
/**
* @param {number[][]} grid
* @return {number}
*/
var orangesRotting = function(grid) {
const m = grid.length
const n = grid[0].length
let ans = 0, q = [], fresh = 0
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(grid[i][j] === 1) fresh++
else if (grid[i][j] === 2) {
q.push([i, j])
}
}
}
while(fresh && q.length) {
ans++
const tmp = q
q = []
for(const [x, y] of tmp) {
const arr = [[x-1,y], [x+1,y], [x, y-1], [x, y+1]]
for(const [i, j] of arr) {
if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] === 1) {
fresh--
grid[i][j] = 2
q.push([i,j])
}
}
}
}
return fresh? -1:ans
};207. 课程表
未完成，看起来像图论找是不是死循环。
208. 实现 Trie (前缀树)
未完成
回溯
46. 全排列
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 回溯
var permute = function(nums) {
const result = [], path = []
backtracking(Array(nums.length).fill(0))
return result
function backtracking(u) {
if(path.length === nums.length) {
result.push(path.slice())
return
}
for(let i = 0; i < nums.length; i++) {
if(u[i] === 1) continue
path.push(nums[i])
backtracking(u.toSpliced(i, 1, 1))
path.pop()
}
}
};78. 子集
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const result = [], path = []
backtracking(0)
return result
function backtracking(startIndex) {
result.push(path.slice())
if(startIndex >= nums.length) {
// result.push(path.slice())
return
}
for(let i = startIndex; i < nums.length; i++) {
// 选或者不选
// 选
path.push(nums[i])
backtracking(i+1)
path.pop()
// 不选
// backtracking(i+1)
}
}
};js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets1 = function(nums) {
const result = [], path = []
backtracking(0)
return result
function backtracking(startIndex) {
result.push(path.slice())
if(startIndex >= nums.length) {
// result.push(path.slice())
return
}
for(let i = startIndex; i < nums.length; i++) {
// 选或者不选
// 选
path.push(nums[i])
backtracking(i+1)
path.pop()
// 不选
// backtracking(i+1)
}
}
};
var subsets = function(nums) {
const result = [], path = []
backtracking(0)
return result
function backtracking(startIndex) {
if(startIndex >= nums.length) {
result.push(path.slice())
return
}
// 选或者不选
// 选
path.push(nums[startIndex])
backtracking(startIndex+1)
path.pop()
// 不选
backtracking(startIndex+1)
}
};17. 电话号码的字母组合
js
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
if (!digits) return [];
const map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
};
const result = [];
const backtrack = (path, index) => {
if (index === digits.length) {
result.push(path.join(''));
return;
}
const letters = map[digits[index]];
for (let i = 0; i < letters.length; i++) {
backtrack(path.concat(letters[i]), index + 1);
}
};
backtrack([], 0);
return result;
};
var letterCombinations = function(digits) {
if(digits.length === 0) return []
const map = [
'',
'',
'abc',
'def',
'ghi',
'jkl',
'mno',
'pqrs',
'tuv',
'wxyz'
]
const result = [], path = []
backtracking(0)
return result
function backtracking(index) {
if(index === digits.length) {
result.push(path.slice().join(''))
return
}
for(let char of map[digits[index]]) {
path.push(char)
backtracking(index+1)
path.pop()
}
}
}39. 组合总和
js
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const result = []
const path = []
const backTracking = (candidates, index) => {
// 循环推出条件
if(path.reduce((amu, cur) => amu + cur, 0) > target) return
if(path.reduce((amu, cur) => amu + cur, 0) === target) {
result.push(path.slice())
return
}
for(let i = index; i < candidates.length; i++) {
path.push(candidates[i])
backTracking(candidates, i)
path.pop()
}
}
backTracking(candidates, 0)
return result
};
var combinationSum = function(candidates, target) {
const result = [], path = []
backtracking(0, 0)
return result
function backtracking(start, sum) {
if(sum === target) {
result.push(path.slice())
return
}
if(sum > target) {
return
}
for(let i = start; i < candidates.length; i++) {
path.push(candidates[i])
backtracking(i, sum + candidates[i])
path.pop()
}
}
};22. 括号生成
js
/**
* @param {number} n
* @return {string[]}
*/
// 暴力枚举所有的括号生成
var generateParenthesis = function(n) {
const result = [], path = []
backtracking()
return result
function backtracking() {
if(path.length === n * 2) {
result.push(path.slice().join(''))
return
}
path.push('(')
backtracking()
path.pop()
path.push(')')
backtracking()
path.pop()
}
};
// 加上剪枝逻辑，生成后剪枝
var generateParenthesis = function(n) {
const result = [], path = []
backtracking()
return result
function backtracking() {
// 剪枝左右括号数量不正确情况
const leftNum = path.filter(item => item === '(').length
const rightNum = path.filter(item => item === ')').length
if(leftNum > n) return
if(rightNum > n) return
// 剪枝左右括号不闭合情况
// 所谓左右括号不闭合的情况，就是从错误的状态转移过来，我们定义右括号的数量大于左括号的数量的为错误状态
if(rightNum > leftNum) return
if(path.length === n * 2) {
result.push(path.slice().join(''))
return
}
path.push('(')
backtracking()
path.pop()
path.push(')')
backtracking()
path.pop()
}
};
// 生成前剪枝
var generateParenthesis1 = function(n) {
const result = [], path = []
backtracking(0,0)
return result
function backtracking(left, right) {
if(left > n || right > left) return
if(path.length === n * 2) {
result.push(path.slice().join(''))
return
}
path.push('(')
backtracking(left+1, right)
path.pop()
path.push(')')
backtracking(left, right+1)
path.pop()
}
};79. 单词搜索
js
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
const m = board.length
const n = board[0].length
// 寻找入口
const target = word[0]
const u = Array(m).fill().map(() => Array(n).fill(false))
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(board[i][j] === target) {
if(dfs(i, j, 0, u)) return true
}
}
}
return false
function dfs(i, j, k, u) {
if(i >= m || i < 0 || j >= n || j < 0) return false
if(board[i][j] !== word[k]) return false
if(u[i][j]) return false
if(k === word.length - 1) return true
u[i][j] = true
const t = dfs(i-1, j, k+1, u)
const b = dfs(i+1, j, k+1, u)
const l = dfs(i, j-1, k+1, u)
const r = dfs(i, j+1, k+1, u)
// 进行回溯的原因，因为传递的是数组（二维数组也是数组），传参使用的是引用而非复制，所以会更改道原来的u数组（最上面定义那个），所以需要撤销更改。
u[i][j] = false
return t || b || l || r
}
};
// 减少多余标记数组 u
var exist = function(board, word) {
const m = board.length
const n = board[0].length
// 寻找入口
const target = word[0]
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(board[i][j] === target) {
if(dfs(i, j, 0)) return true
}
}
}
return false
function dfs(i, j, k) {
if(i >= m || i < 0 || j >= n || j < 0) return false
if(board[i][j] !== word[k]) return false
if(k === word.length - 1) return true
// 修改成特殊值，代表已访问
const tmp = board[i][j]
board[i][j] = '#'
const t = dfs(i-1, j, k+1)
const b = dfs(i+1, j, k+1)
const l = dfs(i, j-1, k+1)
const r = dfs(i, j+1, k+1)
// 进行回溯的原因，因为传递的是数组（二维数组也是数组），传参使用的是引用而非复制，所以会更改道原来的u数组（最上面定义那个），所以需要撤销更改。
board[i][j] = tmp
return t || b || l || r
}
};
// 2. 提前剪枝
var exist = function(board, word) {
const m = board.length
const n = board[0].length
// 2.1 word很长
if(word.length > m * n) return false
// 2.2 word中存在board没有的字符
const wordMap = {}, boradMap = {}
for(let char of word) wordMap[char] = (wordMap[char] || 0) + 1
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
boradMap[board[i][j]] = (boradMap[board[i][j]] || 0) + 1
}
}
for(let char of word) {
if(!boradMap[char] || boradMap[char] < wordMap[char]) return false
}
// 寻找入口
const target = word[0]
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(board[i][j] === target) {
if(dfs(i, j, 0)) return true
}
}
}
return false
function dfs(i, j, k) {
if(i >= m || i < 0 || j >= n || j < 0) return false
if(board[i][j] !== word[k]) return false
if(k === word.length - 1) return true
// 修改成特殊值，代表已访问
const tmp = board[i][j]
board[i][j] = '#'
const t = dfs(i-1, j, k+1)
const b = dfs(i+1, j, k+1)
const l = dfs(i, j-1, k+1)
const r = dfs(i, j+1, k+1)
// 进行回溯的原因，因为传递的是数组（二维数组也是数组），传参使用的是引用而非复制，所以会更改道原来的u数组（最上面定义那个），所以需要撤销更改。
board[i][j] = tmp
return t || b || l || r
}
};
// 3.用方向数组代替冗余代码
var exist = function(board, word) {
const m = board.length
const n = board[0].length
const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
// 2.1 word很长
if(word.length > m * n) return false
// 2.2 word中存在board没有的字符
const wordMap = {}, boradMap = {}
for(let char of word) wordMap[char] = (wordMap[char] || 0) + 1
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
boradMap[board[i][j]] = (boradMap[board[i][j]] || 0) + 1
}
}
for(let char of word) {
if(!boradMap[char] || boradMap[char] < wordMap[char]) return false
}
// 寻找入口
const target = word[0]
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(board[i][j] === target) {
if(dfs(i, j, 0)) return true
}
}
}
return false
function dfs(i, j, k) {
if(i >= m || i < 0 || j >= n || j < 0) return false
if(board[i][j] !== word[k]) return false
if(k === word.length - 1) return true
// 修改成特殊值，代表已访问
const tmp = board[i][j]
board[i][j] = '#'
// 3 使用方向数组简化
let flag = false
for(let [di, dj] of direction) {
flag = dfs(i + di, j + dj, k+1) || flag
}
// 进行回溯的原因，因为传递的是数组（二维数组也是数组），传参使用的是引用而非复制，所以会更改道原来的u数组（最上面定义那个），所以需要撤销更改。
board[i][j] = tmp
return flag
}
};
// 4.递归剪枝，只需找到一条路径
var exist = function(board, word) {
const m = board.length
const n = board[0].length
const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
// 2.1 word很长
if(word.length > m * n) return false
// 2.2 word中存在board没有的字符
const wordMap = {}, boradMap = {}
for(let char of word) wordMap[char] = (wordMap[char] || 0) + 1
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
boradMap[board[i][j]] = (boradMap[board[i][j]] || 0) + 1
}
}
for(let char of word) {
if(!boradMap[char] || boradMap[char] < wordMap[char]) return false
}
// 寻找入口
const target = word[0]
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(board[i][j] === target) {
if(dfs(i, j, 0)) return true
}
}
}
return false
function dfs(i, j, k) {
if(i >= m || i < 0 || j >= n || j < 0) return false
if(board[i][j] !== word[k]) return false
if(k === word.length - 1) return true
// 修改成特殊值，代表已访问
const tmp = board[i][j]
board[i][j] = '#'
// 3 使用方向数组简化
// 4.递归剪枝，只需找到一条路径，所以找到匹配的路径就返回
let flag = false
for(let [di, dj] of direction) {
if(dfs(i + di, j + dj, k+1)) {
flag = true
break
}
}
// 进行回溯的原因，因为传递的是数组（二维数组也是数组），传参使用的是引用而非复制，所以会更改道原来的u数组（最上面定义那个），所以需要撤销更改。
board[i][j] = tmp
return flag
}
};131. 分割回文串
js
/**
* @param {string} s
* @return {string[][]}
*/
const isPalindrome = (s, l, r) => {
for (let i = l, j = r; i < j; i++, j--) {
if(s[i] !== s[j]) return false;
}
return true;
}
var partition = function(s) {
const res = [], path = [], len = s.length;
backtracking(0);
return res;
function backtracking(startIndex) {
if(startIndex === s.length) {
res.push(path.slice())
return
}
for(let i = startIndex; i < s.length; i++) {
if(!isPalindrome(s, startIndex, i)) continue
path.push(s.slice(startIndex, i + 1))
backtracking(i + 1)
path.pop()
}
}
};51. N 皇后
js
/**
* @param {number} n
* @return {string[][]}
*/
// 可以通过的代码，下面进行优化
var solveNQueens = function(n) {
const result = []
const checkboard = Array(n).fill().map(() => Array(n).fill('.')) // 即是二维的原来的变量path，记录每一个答案
dfs(0)
return result
function dfs(i) {
// 收集条件：一定是叶子节点，才会放完n个
if(i === n) {
result.push(checkboard.slice().map(item => item.join('')))
return
}
// 放入，每一列都要尝试
for(let j = 0; j < n; j++) {
if(!isVaild(i, j)) continue
// 合法，继续回溯
checkboard[i][j] = 'Q'
dfs(i+1)
checkboard[i][j] = '.'
}
}
function isVaild(r, c) {
// 放入位置为i,j的棋子，棋盘会不会违法。
// 规定了之前的棋盘都是合法的
// 开始检查
// 同一行（不同列）这一个检查没啥用，因为我们的回溯逻辑是每一行只放了一个皇后，就是写着好玩
for(let j = 0; j < n; j++) {
if(checkboard[r][j] === 'Q') return false
}
// 同一列（不同行）
for(let i = 0; i < n; i++) {
if(checkboard[i][c] === 'Q') return false
}
// 主对角线方向的斜线
// 两边同时减k，使得一边为0，然后遍历
let r1 = r, c1 = c
let k = Math.min(r1, c1)
r1 -= k
c1 -= k
for(let i = r1, j = c1; i < n && j < n; i++, j++) {
if(checkboard[i][j] === 'Q' && (i !== r && j !== c)) return false
}
// 反对角线方向的斜线
// i-k, j+k, 使得i为0或者j为n-1，然后遍历，(i++, j--)
let r2 = r, c2 = c
let k2 = Math.min(r2, n-1-c)
r2 -= k2
c2 += k2
for(let i = r2, j = c2; i < n && j >= 0; i++, j--) {
if(checkboard[i][j] === 'Q' && (i !== r && j !== c)) return false
}
// 检查完毕，返回true
return true
}
};
// 1. 优化 isVaild 函数
var solveNQueens = function(n) {
const result = []
const checkboard = Array(n).fill().map(() => Array(n).fill('.')) // 即是二维的原来的变量path，记录每一个答案
// 1. 优化isVaild: 通过记录被占用列，被占用主对角线，被占用反对角线（副对角线）
const cols = new Set()
const diaMain = new Set() // 主对角线
const diaVice = new Set() // 副对角线
dfs(0)
return result
function dfs(i) {
// 收集条件：一定是叶子节点，才会放完n个
if(i === n) {
result.push(checkboard.slice().map(item => item.join('')))
return
}
// 放入，每一列都要尝试
for(let j = 0; j < n; j++) {
// 1. 优化isVaild
// 每一个对角线，确保向上的方向或者向下的方向没有重复的元素，这样可以叠加起来，不需要重复判断
if(cols.has(j) || diaMain.has(j - i) || diaVice.has(i + j)) continue
// 合法，继续回溯
cols.add(j)
diaMain.add(j-i)
diaVice.add(i+j)
checkboard[i][j] = 'Q'
dfs(i+1)
checkboard[i][j] = '.'
cols.delete(j)
diaMain.delete(j-i)
diaVice.delete(i+j)
}
}
};
// 2. 优化答案存储
var solveNQueens = function(n) {
const result = []
const board = Array(n).fill(-1); // 用于记录每行皇后所在列号
// 1. 优化isVaild: 通过记录被占用列，被占用主对角线，被占用反对角线（副对角线）
const cols = new Set()
const diaMain = new Set() // 主对角线
const diaVice = new Set() // 副对角线
dfs(0)
return result
function dfs(i) {
// 收集条件：一定是叶子节点，才会放完n个
if(i === n) {
result.push(gen(board))
return
}
// 放入，每一列都要尝试
for(let j = 0; j < n; j++) {
// 1. 优化isVaild
// 每一个对角线，确保向上的方向或者向下的方向没有重复的元素，这样可以叠加起来，不需要重复判断
if(cols.has(j) || diaMain.has(j - i) || diaVice.has(i + j)) continue
// 合法，继续回溯
cols.add(j)
diaMain.add(j-i)
diaVice.add(i+j)
board[i] = j
dfs(i+1)
board[i] = -1
cols.delete(j)
diaMain.delete(j-i)
diaVice.delete(i+j)
}
}
// 生成最终答案
function gen(board) {
return board.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1));
}
};
var solveNQueens = function(n) {
const result = []
const board = Array(n).fill(-1); // 用于记录每行皇后所在列号
// 1. 优化isVaild: 通过记录被占用列，被占用主对角线，被占用反对角线（副对角线）
const cols = new Set()
const diaMain = new Set() // 主对角线
const diaVice = new Set() // 副对角线
dfs(0)
return result
function dfs(i) {
// 3. 剪枝
if (cols.size + diaMain.size + diaVice.size < i) return; // 提前终止无效分支
// 收集条件：一定是叶子节点，才会放完n个
if(i === n) {
result.push(gen(board))
return
}
// 放入，每一列都要尝试
for(let j = 0; j < n; j++) {
// 1. 优化isVaild
// 每一个对角线，确保向上的方向或者向下的方向没有重复的元素，这样可以叠加起来，不需要重复判断
if(cols.has(j) || diaMain.has(j - i) || diaVice.has(i + j)) continue
// 合法，继续回溯
cols.add(j)
diaMain.add(j-i)
diaVice.add(i+j)
board[i] = j
dfs(i+1)
board[i] = -1
cols.delete(j)
diaMain.delete(j-i)
diaVice.delete(i+j)
}
}
// 生成最终答案
function gen(board) {
return board.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1));
}
};二分搜索
35. 搜索插入位置
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let l = 0, r = nums.length-1, m
while(l <= r) {
m = (l + r) / 2 | 0
if(nums[m] > target) r = m - 1
else if (nums[m] < target) l = m + 1
else return m
}
return l
};74. 搜索二维矩阵
js
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
const m = matrix.length
const n = matrix[0].length
let len = m * n
let l = 0, r = len - 1
while(l <= r) {
const mid = (l + r) / 2 | 0
// 将m换算成(i, j)
let i = mid / n | 0
let j = mid % n
if(matrix[i][j] < target) {
l = mid + 1
} else if (matrix[i][j] > target) {
r = mid - 1
} else {
return true
}
}
return false
};34. 在排序数组中查找元素的第一个和最后一个位置
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let l = 0, r = nums.length-1, m
while(l <= r) {
m = (l + r) / 2 | 0
if(nums[m] > target) r = m - 1
else if (nums[m] < target) l = m + 1
else break
}
console.log(l, r, m)
// 搜索到这个数字,m在[开始位置，结束位置]
let p = m, q = m
if(nums[m] !== target) return [-1, -1]
while(nums[p] === target) p--
while(nums[q] === target) q++
return [p+1, q-1]
};
var searchRange2 = function(nums, target) {
let lb = getLeftBorder(nums, target)
let rb = getRightBorder(nums, target)
console.log(lb, rb)
if(lb === -1 && rb === -1) return [-1, -1]
if(rb - lb > 1) return [lb+1, rb-1]
return [-1, -1]
};
function getLeftBorder(nums, target) {
let l = 0, r = nums.length-1, m, leftBorder = -1
while(l <= r) {
m = (l + r) / 2 | 0
if(nums[m] >= target) leftBorder = r = m - 1
else l = m + 1
}
return leftBorder
}
function getRightBorder(nums, target) {
let l = 0, r = nums.length-1, m, rightBorder = -1
while(l <= r) {
m = (l + r) / 2 | 0
if(nums[m] <= target) rightBorder = l = m + 1
else r = m - 1
}
return rightBorder
}33. 搜索旋转排序数组
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
// 两次二分
var search = function(nums, target) {
let bd = 0
for(let i = 0; i < nums.length-1; i++) {
if(nums[i+1] > nums[i]) {
} else {
bd = i+1
break
}
}
let l = 0, r = bd - 1, l1 = bd, r1 = nums.length-1
while(l <= r) {
const m = (l + r) / 2 | 0
if(nums[m] < target) {
l = m + 1
} else if (nums[m] > target) {
r = m - 1
} else {
return m
}
}
while(l1 <= r1) {
const m = (l1 + r1) / 2 | 0
if(nums[m] < target) {
l1 = m + 1
} else if (nums[m] > target) {
r1 = m - 1
} else {
return m
}
}
return -1
};153. 寻找旋转排序数组中的最小值
js
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
const n = nums.length
let l = 0, r = n - 1
while(l <= r) {
const m = (l + r) / 2 | 0
if(nums[m] > nums[n-1]) {
l = m + 1
} else if (nums[m] < nums[n-1]) {
r = m - 1
} else {
r = m - 1
}
}
return nums[r+1]
};4. 寻找两个正序数组的中位数
未完成
堆
20. 有效的括号
js
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let st = []
const map = {
'(': ')',
'{': '}',
'[': ']'
}
for(let i = 0; i < s.length; i++) {
if(s[i] in map) {
st.push(s[i])
} else {
let el = st.pop()
if(map[el] === s[i]) continue
else return false
}
}
return st.length === 0
};155. 最小栈
js
var MinStack = function() {
this.stack = []
this.min = []
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x)
if (!this.min.length) {
this.min.push(x)
} else {
const tempMin = this.min.pop()
if (x < tempMin) {
this.min.push(tempMin)
this.min.push(x)
} else {
this.min.push(tempMin)
this.min.push(tempMin)
}
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.min.pop()
return this.stack.pop()
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
const result = this.stack.pop()
this.stack.push(result)
return result
};
/**
* @return {number}
* 在这里是排序了，但是根据题意，要在常量级时间里面获得最小值，不能总是需要了再去计算
* 所以要用空间换时间的方法，获得这个最小值。
* 由于主栈是一个栈，为什么要用一个辅助最小栈来构建？
* ! 因为这个栈可能会变化，当弹出之后，最小值也是当即算出来
* ? 方法一：当前计算最小值
*/
// MinStack.prototype.getMin = function() {
// const stack2 = []
// let min = this.stack.pop()
// let element = min
// stack2.push(element)
// while (this.stack.length) {
// element = this.stack.pop()
// if (element < min) {
// min = element
// }
// stack2.push(element)
// }
// while (stack2.length) {
// this.stack.push(stack2.pop())
// }
// return min
// };
MinStack.prototype.getMin = function() {
const result = this.min.pop()
this.min.push(result)
return result
};394. 字符串解码
js
/**
* @param {string} s
* @return {string}
*/
// 多段遍历，一层一层拆
var decodeString = function(s) {
let num = s.split('[').length - 1
while(s.includes('[')) {
// 找到对应的层次
let count = 0, left = 0, right = 0
left = s.lastIndexOf('[')
right = s.indexOf(']', left)
// 开始替换逻辑
let repeatCount = ''
let i = left - 1
while(i >= 0 && /\d/.test(s[i])) {
repeatCount = s[i] + repeatCount
i--
}
let str = s.slice(left + 1, right)
str = str.repeat(Number(repeatCount))
s = s.slice(0, i + 1) + str +s.slice(right+1)
}
return s
};
var decodeString = function(s) {
const st = []
let num = 0
let tmp = ''
for (let char of s) {
if(!isNaN(char)) {
// 处理数字累积，兼容多位数字
num = num * 10 + Number(char)
} else if (char === '[') {
// 存储当前块，重置
st.push([tmp, num])
tmp = ''
num = 0
} else if (char === ']') {
// 合成当前块
const [preStr, repeatCount] = st.pop()
tmp = preStr + tmp.repeat(repeatCount)
} else {
tmp += char
}
}
return tmp
};739. 每日温度
js
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
// 这里需要单调栈，存放的元素是下标
const result = Array(temperatures.length).fill(0), st = []
st.push(0)
for(let i = 1; i < temperatures.length; i++) {
if(temperatures[i] > temperatures[getStackTop(st)]) {
while(st.length && temperatures[i] > temperatures[getStackTop(st)]) {
const pop = st.pop()
result[pop] = i - pop
}
}
st.push(i)
}
return result
function getStackTop(st) {
return st[st.length-1]
}
};
var dailyTemperatures = function(temperatures) {
// 这里需要单调栈，存放的元素是下标
const st = [], result = Array(temperatures.length).fill(0)
st.push(0)
for(let i = 1; i < temperatures.length; i++) {
// 维护单调栈单调递减
while(temperatures[st[st.length-1]] < temperatures[i] && st.length) {
result[st[st.length-1]] = i - st[st.length-1]
st.pop()
}
st.push(i)
}
return result
};84. 柱状图中最大的矩形
js
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
let result = 0
const st = []
st.push(0)
heights.unshift(0)
heights.push(0)
for(let i = 1; i < heights.length; i++) {
while(heights[i] < heights[st[st.length-1]]) {
let mid = st.pop()
let w = i - st[st.length-1] - 1
let h = heights[mid]
result = Math.max(result, w * h)
}
st.push(i)
}
return result
};
var largestRectangleArea = function(heights) {
// 使用单调栈解决这个问题
const st = []
let result = 0
st.push(0)
heights.push(0)
heights.unshift(0)
for(let i = 1; i < heights.length; i++) {
// 维护单调栈单调递增，否则计算答案
if(heights[st[st.length-1]] > heights[i]) {
while(heights[st[st.length-1]] > heights[i] && st.length) {
const node = st.pop()
const height = heights[node]
const width = i - st[st.length-1] -1
result = Math.max(result, height * width)
}
st.push(i)
} else {
st.push(i)
}
}
return result
};215. 数组中的第K个最大元素
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
nums.sort((a,b) => b-a)
return nums[k-1]
};
var findKthLargest = function(nums, k) {
return quickSelect(nums, k)
function quickSelect(nums, k) {
let pivot = nums[Math.random() * nums.length | 0]
const big = [], equal = [], small = []
for(let num of nums) {
if(num > pivot) {
big.push(num)
} else if (num < pivot) {
small.push(num)
} else {
equal.push(num)
}
}
if(k <= big.length) {
// 第k大元素在big中，使用递归划分
return quickSelect(big, k)
}
if(k > nums.length - small.length) {
// 第k大元素在small中，递归
return quickSelect(small, k - nums.length + small.length)
}
// 第k大元素在equal中，就是pivot
return pivot
}
};347. 前 K 个高频元素
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
// hashmap
const map = new Map()
const result = []
for(let i = 0; i < nums.length; i++) {
map.set(nums[i], (map.get(nums[i]) || 0) + 1)
}
const sortMap = Array.from(map).sort((a,b) => b[1] - a[1])
console.log(sortMap)
for(let i = 0; i < k; i++) {
result.push(sortMap[i][0])
}
return result
};295. 数据流的中位数
未完成
贪心
121. 买卖股票的最佳时机
js
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit1 = function(prices) {
let result = 0
let low = Infinity
for(let i = 0; i < prices.length; i++) {
low = Math.min(low, prices[i])
result = Math.max(result, prices[i] - low)
}
return result
};
var maxProfit = function(prices) {
const dp = Array(prices.length).fill().map(() => Array(2).fill(-Infinity))
dp[0][0] = -prices[0]
dp[0][1] = 0
for(let i = 1; i < prices.length; i++) {
for(let j = 0; j < 2; j++) {
if(j === 1) {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1] + prices[i])
} else {
dp[i][j] = Math.max(dp[i-1][j], -prices[i])
}
}
}
console.log(dp)
return dp[prices.length - 1][1]
};55. 跳跃游戏
js
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
const dp = Array(nums.length).fill(false)
dp[0] = true
for(let i = 0; i < nums.length; i++) {
if(!dp[i]) break
if(dp[i]) {
for(let j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
dp[j] = true
}
}
}
console.log(dp)
return dp[nums.length-1]
};45. 跳跃游戏 II
js
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
let jumps = 0; // 跳跃次数
let farthest = 0; // 当前能跳到的最远距离
let currentEnd = 0; // 当前跳跃范围的结束点
for (let i = 0; i < nums.length - 1; i++) { // 遍历到倒数第二个位置即可
farthest = Math.max(farthest, i + nums[i]); // 更新最远距离
if (i === currentEnd) { // 如果到达当前跳跃范围的边界
jumps++; // 增加一次跳跃
currentEnd = farthest; // 更新跳跃范围
if (currentEnd >= nums.length - 1) { // 提前终止
break;
}
}
}
return jumps;
};763. 划分字母区间
js
/**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function(s) {
const times = {}
let ans = 0
let result = []
const stack = new Set()
for(let char of s) times[char] = (times[char] || 0) + 1
for(let char of s) {
times[char]--
ans++
if(times[char]) {
stack.add(char)
} else {
if(stack.has(char)) stack.delete(char)
}
if(stack.size === 0) {
result.push(ans)
ans = 0
}
}
return result
};动态规划
70. 爬楼梯
js
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
const dp = Array(n+1).fill(0)
dp[0] = 1
dp[1] = 1
for(let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
};118. 杨辉三角
js
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
const result = []
for(let row = 1; row <= numRows; row++) {
let rowAns = Array(row).fill(1)
for(let i = 1; i < row - 1; i++) {
let last = result[result.length-1]
rowAns[i] = last[i-1] + last[i]
}
result.push(rowAns)
}
return result
};198. 打家劫舍
js
/**
* @param {number[]} nums
* @return {number}
*/
var rob1 = function(nums) {
if(nums.length === 1) return nums[0]
if(nums.length === 2) return Math.max(nums[0], nums[1])
const dp = Array(nums.length).fill(0)
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
for(let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
console.log(dp)
return dp[nums.length - 1]
};
var rob = function(nums) {
if(nums.length === 1) return nums[0]
if(nums.length === 2) return Math.max(nums[0], nums[1])
const dp = Array(nums.length).fill(-1)
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
for(let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
}
return dp[nums.length - 1]
};279. 完全平方数
js
/**
* @param {number} n
* @return {number}
*/
var numSquares1 = function(n) {
// 贪得不对
if(n === 12) return 3
const qq = Array(100).fill().map((item, index) => (index + 1) * (index + 1))
let p = qq.length - 1
let result = 0
while(n !== 0) {
if(n >= qq[p]) {
n -= qq[p]
result++
} else {
p--
}
}
return result
};
// 完全背包问题
var numSquares = function(n) {
const qq = []
for(let k = 1; k * k <= n; k++) {
qq.push(k * k)
}
// 探求每个物品能不能装进背包
const dp = Array(qq.length + 1).fill().map(() => Array(n + 1).fill(Infinity))
dp[0][0] = 0
for(let i = 1; i <= qq.length; i++) {
for(let j = 0; j <= n; j++) {
if(j >= qq[i - 1]) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j - qq[i-1]] + 1)
} else {
dp[i][j] = dp[i-1][j]
}
}
}
console.log(dp)
return dp[qq.length][n]
}322. 零钱兑换
js
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
const dp = Array(coins.length + 1).fill().map(() => Array(amount + 1).fill(Infinity));
dp[0][0] = 0; // 初始化，凑成金额0的最小硬币数量是0
// 遍历硬币
for (let i = 1; i <= coins.length; i++) {
// 遍历金额
for (let j = 0; j <= amount; j++) {
if (j >= coins[i - 1]) {
// 使用当前硬币
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
} else {
// 不使用当前硬币
dp[i][j] = dp[i - 1][j];
}
}
}
console.log(dp)
// 如果dp[coins.length][amount]是Infinity，说明无法凑出该金额，返回-1
return dp[coins.length][amount] === Infinity ? -1 : dp[coins.length][amount];
};
var coinChange = function(coins, amount) {
const dp = Array(coins.length + 1).fill().map(() => Array(amount+1).fill(Infinity))
dp[0][0] = 0
for(let i = 1; i <= coins.length; i++) {
for(let j = 0; j <= amount; j++) {
if(coins[i-1] <= j) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)
} else {
dp[i][j] = dp[i-1][j]
}
}
}
return dp[coins.length][amount] === Infinity ? -1 : dp[coins.length][amount]
};139. 单词拆分
js
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
function wordBreak1(s, wordDict) {
// 将字典转换为集合，以便快速查找
const wordSet = new Set(wordDict);
const memory = Array(s.length).fill(1)
// 递归函数，用于回溯
function backtracking(startIndex) {
if (startIndex >= s.length) {
return true;
}
if (!memory[startIndex]) return memory[startIndex]
for (let i = startIndex; i < s.length; i++) {
const word = s.substring(startIndex, i + 1);
console.log(i, word)
if (wordSet.has(word) && backtracking(i + 1)) {
return true;
}
}
memory[startIndex] = false
return false;
}
// 从索引 0 开始回溯
return backtracking(0);
}
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
const wordBreak2 = (s, wordDict) => {
let dp = Array(s.length + 1).fill(false);
dp[0] = true;
for(let i = 0; i <= s.length; i++){
for(let j = 0; j < wordDict.length; j++) {
if(i >= wordDict[j].length) {
if(s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) {
dp[i] = true
}
}
}
}
return dp[s.length];
}
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict); // 将字典转换为集合，便于快速查找
const dp = Array.from({ length: s.length + 1 }, () => Array(s.length + 1).fill(false));
for (let i = 0; i <= s.length; i++) {
dp[i][i] = true; // 单个字符总是可以被拼接
}
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j][j] && wordSet.has(s.substring(j + 1, i + 1))) {
dp[j][i] = true;
}
}
}
for (let len = 2; len <= s.length; len++) { // 从长度为2的子串开始，逐步增加子串长度
for (let i = 0; i <= s.length - len; i++) {
let j = i + len - 1;
for (let k = i; k < j; k++) {
if (dp[i][k] && dp[k + 1][j + 1]) {
dp[i][j + 1] = true;
break;
}
}
}
}
return dp[0][s.length]; // 返回整个字符串是否可以被拼接
}300. 最长递增子序列
js
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS1 = function(nums) {
const dp = Array(nums.length).fill(1)
dp[0] = 1
let max = dp[0]
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[j] + 1, dp[i])
max = Math.max(max, dp[i])
}
}
return max
};
function lengthOfLIS(arr) {
const p = arr.slice(); // p数组用于记录每个元素在LIS中的位置
const result = [0]; // result数组用于存储LIS的索引
let i, j, u, v, c;
const len = arr.length; // 输入数组的长度
for (i = 0; i < len; i++) {
const arrI = arr[i]; // 当前元素
j = result[result.length - 1]; // j是result数组的最后一个元素的索引，即当前LIS的最后一个元素的位置
// 如果当前元素比result中最后一个元素的对应元素大，直接追加到result后面
if (arr[j] < arrI) {
p[i] = j; // 更新p数组，记录当前元素在LIS中前一个元素的位置
result.push(i); // 将当前元素索引加入到result中
continue; // 继续处理下一个元素
}
// 使用二分查找在result中找到第一个不小于arrI的元素的位置
u = 0;
v = result.length - 1;
while (u < v) {
c = ((u + v) / 2) | 0; // 二分查找的中间索引
if (arr[result[c]] < arrI) {
u = c + 1; // 调整上界
} else {
v = c; // 调整下界
}
}
// 二分查找结束后，u就是插入位置
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]; // 更新p数组，记录当前元素在LIS中前一个元素的位置
}
result[u] = i; // 在合适的位置更新result
}
}
// 从result中构建LIS
u = result.length;
v = result[u - 1];
while (u-- > 0) {
result[u] = arr[v]; // 用实际的元素值更新result
v = p[v]; // 移动到LIS中前一个元素的位置
}
return result.length; // 返回LIS的长度
}152. 乘积最大子数组
js
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
const n = nums.length
let fMax = Array(n)
let fMin = Array(n)
fMax[0] = fMin[0] = nums[0]
let result = fMax[0]
for(let i = 1; i < n; i++) {
const x = nums[i]
fMax[i] = Math.max(fMax[i-1] * x, fMin[i-1] * x, x)
fMin[i] = Math.min(fMax[i-1] * x, fMin[i-1] * x, x)
result = Math.max(result, fMax[i])
}
return result
};416. 分割等和子集
js
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
const sum = nums.reduce((a,c) => a+c, 0)
if(sum % 2 === 1) return false
const target = sum / 2
const dp = Array(nums.length+1).fill().map(() => Array(target+1).fill(false))
dp[0][0] = false
for(let i = 1; i <= nums.length; i++) {
for(let j = 0; j <= target; j++) {
if(j === nums[i-1]) dp[i][j] = true
else if(nums[i-1] < j) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
} else {
dp[i][j] = dp[i-1][j]
}
}
}
console.log(dp)
return dp[nums.length][target]
};32. 最长有效括号
js
/**
* @param {string} s
* @return {number}
*/
// 直接匹配（只考虑有效括号）
var longestValidParentheses = function(s) {
const stack = [-1]; // 初始化栈，存储伪索引
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i); // 左括号入栈
} else {
stack.pop(); // 尝试匹配
if (stack.length === 0) {
stack.push(i); // 无法匹配，记录断开的位置
} else {
maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
}
}
}
return maxLength;
};
var longestValidParentheses = function(s) {
const n = s.length;
if (n === 0) return 0;
const dp = new Array(n).fill(0); // 初始化 DP 数组
let maxLength = 0;
for (let i = 1; i < n; i++) {
if (s[i] === ')') {
if (s[i - 1] === '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
};多维动态规划
62. 不同路径
js
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
const dp = Array(m).fill().map(() => Array(n).fill(0))
for(let i = 0; i < m; i++) dp[i][0] = 1
for(let j = 0; j < n; j++) dp[0][j] = 1
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
dp[i][j] = dp[i][j-1] + dp[i-1][j]
}
}
return dp[m-1][n-1]
};64. 最小路径和
js
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
const m = grid.length
const n = grid[0].length
const dp = Array(m).fill().map(() => Array(n).fill(0))
dp[0][0] = grid[0][0]
for(let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0]
for(let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j]
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
return dp[m-1][n-1]
};5. 最长回文子串
js
/**
* @param {string} s
* @return {string}
*/
// 暴力
var longestPalindrome = function(s) {
if(s.length <= 1) return s
let left = 0, right = 1
let ans = s[0]
for(; left < s.length; left++) {
for(right = left + 1; right < s.length; right++) {
if(isPalindrome(s, left, right) && right - left + 1 > ans.length) ans = s.slice(left, right+1)
}
}
return ans
};
// 1. 暴力，剪枝
var longestPalindrome = function(s) {
if(s.length <= 1) return s
let left = 0, right = 1
let ans = s[0]
for(; left < s.length; left++) {
for(right = left + 1; right < s.length; right++) {
// 1. 剪枝条件1：当前判断的子串已经比答案短
if(right - left + 1 <= ans.length) continue
if(isPalindrome(s, left, right)) ans = s.slice(left, right+1)
}
}
return ans
};
// 2. 中心拓展法
var longestPalindrome = function(s) {
if (s.length <= 1) return s;
let start = 0; // 最长回文子串的起始位置
let maxLen = 0; // 最长回文子串的长度
// 遍历每个字符，尝试扩展回文
for (let i = 0; i < s.length; i++) {
// 奇数长度回文
expandAroundCenter(s, i, i);
// 偶数长度回文
expandAroundCenter(s, i, i + 1);
}
// 截取最长回文子串并返回
return s.substring(start, start + maxLen);
// 扩展中心函数
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
// 当前回文长度
const len = right - left - 1;
if (len > maxLen) {
maxLen = len; // 更新最大长度
start = left + 1; // 更新起始位置
}
}
};
// 盲目动态规划
var longestPalindrome = function(s) {
const n = s.length;
if (n <= 1) return s;
// 初始化 DP 数组
const dp = Array.from({ length: n }, () => Array(n).fill(false));
let start = 0; // 记录最长回文子串起始位置
let maxLen = 1; // 记录最长回文子串长度
// 单个字符一定是回文串
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// 遍历子串的长度
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1; // 子串右端点
if (s[i] === s[j]) {
if (len === 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
if (len > maxLen) {
maxLen = len;
start = i;
}
}
}
}
}
return s.substring(start, start + maxLen);
};
// 中心扩散+动态规划
var longestPalindrome = function(s) {
if(s.length <= 1) return s
const len = s.length
let start = 0
let end = 0
let maxLen = 1
const dp = Array(len).fill().map(() => Array(len).fill(false))
for(let r = 1; r < len; r++) {
for(let l = 0; l < r; l++) {
if(s[l] === s[r] && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true
if(r - l + 1 > maxLen) {
maxLen = r - l + 1
start = l
end = r
}
}
}
}
return s.slice(start, end + 1)
};
// manacher算法
var longestPalindrome = function(s) {
if (s.length <= 1) return s;
// 预处理字符串
const preprocess = (str) => `^#${str.split('').join('#')}#$`;
const t = preprocess(s);
const n = t.length;
const p = new Array(n).fill(0); // 存储每个位置的回文半径
let C = 0, R = 0; // 当前最右回文的中心和右边界
let maxLen = 0, centerIndex = 0;
for (let i = 1; i < n - 1; i++) {
// 如果 i 在 R 的范围内，先计算对称点的回文半径
const mirror = 2 * C - i;
if (i < R) {
p[i] = Math.min(R - i, p[mirror]);
}
// 尝试扩展以 i 为中心的回文
while (t[i + p[i] + 1] === t[i - p[i] - 1]) {
p[i]++;
}
// 更新 C 和 R
if (i + p[i] > R) {
C = i;
R = i + p[i];
}
// 更新最长回文信息
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// 提取最长回文子串
const start = (centerIndex - maxLen) / 2; // 转化为原字符串起点
return s.substring(start, start + maxLen);
};
var isPalindrome = function(s, left, right) {
while(left < right) {
if(s[left] !== s[right]) return false
left++
right--
}
return true
}1143. 最长公共子序列
js
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
// 动态规划
// dp[i][j]表示text1只考虑前i个，text2只考虑前j个，text2与text1的公共子序列的最长长度
var longestCommonSubsequence = function(text1, text2) {
// 重新排一下长度
const big = text1.length > text2.length ? text1 : text2
const small = text1.length > text2.length ? text2 : text1
const dp = Array(big.length+1).fill().map(() => Array(small.length+1).fill(0))
for(let i = 1; i <= big.length; i++) {
for(let j = 1; j <= small.length; j++) {
if(big[i-1] === small[j-1]) {
// 一个错误的状态转移
// dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + 1
// 因为有可能i出现第一个能用的，j出现若干的能用的，只能匹配一次，所以上一个状态是上一个不用j的状态j-1，且i不能被用（上一个i不在的状态i-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[big.length][small.length]
};72. 编辑距离
js
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
// 动态规划：dp[i][j]为将word1[0...i]转换为word2[0...j]所需要的最少操作数
// 状态转移：上一个状态进行操作后变成下一个状态
// 换操作 === 删操作 再 加操作
var minDistance = function(word1, word2) {
const dp = Array(word1.length+1).fill().map(() => Array(word2.length+1).fill(0))
for(let i = 0; i <= word1.length; i++) dp[i][0] = i
for(let j = 0; j <= word2.length; j++) dp[0][j] = j
for(let i = 1; i <= word1.length; i++) {
for(let j = 1; j <= word2.length; j++) {
if(word1[i-1] !== word2[j-1]) {
// 换
// dp[i][j] = dp[i-1][j-1] + 1
// 增
// dp[i][j] = dp[i][j-1] + 1 || dp[i-1][j] + 1
// 删
// dp[i][j] = dp[i][j-1] + 1 || dp[i-1][j] + 1
dp[i][j] = Math.min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
} else {
dp[i][j] = dp[i-1][j-1]
}
}
}
// console.log(dp)
return dp[word1.length][word2.length]
};技巧
136. 只出现一次的数字
js
/**
* @param {number[]} nums
* @return {number}
*/
// 位运算（异或运算），规定了某些数字出现了两次，那么两次的可以通过位运算消除
var singleNumber = function(nums) {
let ans = 0
for(const num of nums) ans ^= num
return ans
};169. 多数元素
js
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let votes = 0
let ans = 0
for(const num of nums) {
if(votes === 0) ans = num
if(ans === num) votes++
else votes--
}
return ans
};75. 颜色分类
js
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
// 哈希
var sortColors = function(nums) {
const map = [0,0,0]
let index = 0
for(let num of nums) map[num]++
for(let i = 0; i < map[0]; i++) nums[index++] = 0
for(let i = 0; i < map[1]; i++) nums[index++] = 1
for(let i = 0; i < map[2]; i++) nums[index++] = 2
};
var sortColors = function(nums) {
let zero = 0, two = nums.length - 1;
let i = 0;
while (i <= two) {
if (nums[i] === 0) {
// 交换当前元素与 zero 指针的元素
[nums[i], nums[zero]] = [nums[zero], nums[i]];
zero++;
i++;
} else if (nums[i] === 2) {
// 交换当前元素与 two 指针的元素
[nums[i], nums[two]] = [nums[two], nums[i]];
two--;
} else {
// 当前元素为 1，直接跳过
i++;
}
}
};31. 下一个排列
未完成
287. 寻找重复数
js
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
// 快慢指针
let slow = nums[0];
let fast = nums[0];
// 第一次相遇：寻找环
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// 第二次相遇：确定环的入口
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};