# 算法
# leetcode
# 1. 两数之和 (opens new window)
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
# 暴力
两层for循环找
时间On2，空间O1
# 哈希表
边循环时边用个map记录当前值，map中有目标值-当前值的值时，即找到了
时间On，空间On
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0;i < nums.length; i++) {
const item = nums[i]
const val = target - item
if (map.has(val)) {
return [i, map.get(val)]
} else {
map.set(item, i)
}
}
};
# 2. 两数相加 (opens new window)
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
搞3个指针，相加，有进位就加上
var addTwoNumbers = function(l1, l2) {
const l3 = new ListNode(0)
let p1 = l1
let p2 = l2
let p3 = l3
let carry = 0
while(p1 || p2) {
const val1 = p1 ? p1.val : 0
const val2 = p2 ? p2.val : 0
const val = val1 + val2 + carry
carry = Math.floor(val / 10)
p3.next = new ListNode(val % 10)
if (p1) p1 = p1.next
if (p2) p2 = p2.next
p3 = p3.next
}
if (carry) {
p3.next = new ListNode(carry)
}
return l3.next
};
# 9.回文数 (opens new window)
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true
# 字符串翻转
const isPalindrome = function(x) {
if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
return x.toString() === x.toString().split('').reverse().join('');
};
# 反转一半数字
var isPalindrome = function(x) {
// 处理边界：负数直接返回 false；末尾为 0 的非零数不是回文
if (x < 0 || (x % 10 === 0 && x !== 0)) return false; // [1,2](@ref)
if (x < 10) return true; // 单个数字是回文
let reversed = 0;
while (x > reversed) {
reversed = reversed * 10 + x % 10; // 取末位加到反转数
x = Math.floor(x / 10); // 移除末位
}
// 比较：偶数位时 x === reversed；奇数位时 x === reversed/10（去除中位数）
return x === reversed || x === Math.floor(reversed / 10); // [1,2,6](@ref)
};
# 13.罗马数字转数字
左边比右边小就减
var romanToInt = function(s) {
// 1. 建立罗马数字到整数的映射关系
const romanMap = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
let total = 0; // 初始化结果变量
const n = s.length; // 字符串长度
// 2. 遍历字符串（注意循环到倒数第二个字符，因为我们会访问 i+1）
for (let i = 0; i < n; i++) {
const currentNum = romanMap[s[i]]; // 当前字符对应的数值
const nextNum = romanMap[s[i + 1]]; // 下一个字符对应的数值（可能为undefined）
// 3. 判断是否属于减法情况
if (nextNum && currentNum < nextNum) {
total -= currentNum; // 当前字符值小于下一个字符值，减去当前值
} else {
total += currentNum; // 否则，加上当前值
}
}
return total; // 返回最终结果
};
# 14. 最长公共前缀 (opens new window)
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs.length === 0) return ''
let first = strs[0] // flower
// 从左往右
// let res = ''
// for(let i = 0; i < first.length; i++) {
// // ["flower","flow","flight"]
// const flag = strs.every(item => {
// return item[i] === first[i]
// })
// if (flag) {
// res += first[i]
// } else {
// break
// }
// }
// return res
// 从右往左
while(first.length) {
const flag = strs.every(item => {
return item.indexOf(first) === 0
})
if (flag) {
break
} else {
first = first.substring(0, first.length - 1)
}
}
return first
};
# 15. 三数之和 (opens new window)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
# 暴力
三层for循环
时间O(n^3)
# 双指针
时间O(n^2)
var threeSum = function (nums) {
let res = []
let length = nums.length;
nums.sort((a, b) => a - b) // 先排个队，最左边是最弱（小）的，最右边是最强(大)的
if (nums[0] <= 0 && nums[length - 1] >= 0) { // 优化1: 整个数组同符号，则无解
for (let i = 0; i < length - 2;) {
if (nums[i] > 0) break; // 优化2: 最左值为正数则一定无解
let first = i + 1
let last = length - 1
do {
if (first >= last || nums[i] * nums[last] > 0) break // 两人选相遇，或者三人同符号，则退出
let result = nums[i] + nums[first] + nums[last]
if (result === 0) { // 如果可以组队
res.push([nums[i], nums[first], nums[last]])
}
if (result <= 0 ) { // 实力太弱，把菜鸟那边右移一位
while (first < last && nums[first] === nums[++first]){} // 如果相等就跳过
} else { // 实力太强，把大神那边左移一位
while (first < last && nums[last] === nums[--last]) {}
}
} while (first < last)
while (nums[i] === nums[++i]) {} // 跳过相同的
}
}
return res
}
# 19. 删除链表的倒数第 N 个结点 (opens new window)
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
双指针，一个先往后走n步，再同时走，先走的那个到底了，后走的那个就是倒数第n个。然后删掉下一个即可。
var removeNthFromEnd = function(head, n) {
var result = new ListNode(null, head)
var pre = result, cur = result
while(n--) {
cur = cur.next;
}
while(cur && cur.next) {
cur = cur.next;
pre = pre.next;
}
pre.next = pre.next.next;
return result.next
};
# 21. 合并两个有序链表 (opens new window)
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
哪边小就用哪边，一边走完后，直接用另一边
var mergeTwoLists = function(l1, l2) {
const res = new ListNode(0)
let p = res
let p1 = l1
let p2 = l2
while(p1 && p2) {
if (p1.val < p2.val) {
p.next = p1
p1= p1.next
} else {
p.next = p2
p2= p2.next
}
p = p.next
}
if (p1) {
p.next = p1
}
if (p2) {
p.next = p2
}
return res.next
};
# 26. 删除有序数组中的重复项 (opens new window)
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
# 后面相同就删除
var removeDuplicates = function(nums) {
let { length } = nums;
for (let i = 1; i < length; i++) {
if (nums[i] === nums[i - 1]) {
nums.splice(i, 1)
i--
length--
}
}
return nums.length
};
# 快慢指针
用个指针记录没重复的索引，没重复时直接顶掉前面的
var removeDuplicates = function(nums) {
if(!nums.length) return 0;
let i = 0;
for(let j = 1; j < nums.length; j++){
if(nums[j] !== nums[i]){
i++;
nums[i] = nums[j];
}
}
return i + 1;
};
# 27. 移除元素 (opens new window)
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
// 相等时将最后的移到第一个
var removeElement = function(nums, val) {
let ans = nums.length;
for (let i = 0; i < ans;) {
if (nums[i] == val) {
nums[i] = nums[ans - 1];
ans--;
} else {
i++;
}
}
return ans;
}
# 28.找出字符串中第一个匹配项的下标 (opens new window)
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
var strStr = function(haystack, needle) {
let index = -1;
const needLength = needle.length;
for (let i = 0; i < haystack.length; i++) {
if (haystack[i] === needle[0]) {
let flag = true;
for (let j = 1; j < needLength; j++) {
if (haystack[i + j] !== needle[j]) {
flag = false;
break;
}
}
if (flag) {
index = i;
break;
}
}
}
return index;
};
# 43.两数相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
function multiply(num1, num2) {
if (num1 === "0" || num2 === "0") return "0"; // 处理乘数为 0 的情况
// 构造数组
let m = num1.length, n = num2.length;
const res = new Array(m + n).fill(0);
// 累加+进位
for (let i = m - 1; i >=0; i--) {
for (let j = n - 1; j >=0; j--) {
const mul = num1[i] * num2[j];
const sum = mul + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j] += Math.floor(sum / 10);
}
}
let str = '';
let start = 0;
// 过滤0
while (res[start] === 0) {
start++;
}
// 拼接
for (let k = start; k < res.length; k++) {
str += String(res[k]);
}
return str;
}
# 54.螺旋矩阵 (opens new window)
不满足条件及时return掉
var spiralOrder = function(matrix) {
if (matrix.length === 0) return []; // 空矩阵直接返回
const res = [];
let top = 0, bottom = matrix.length - 1; // 上下边界
let left = 0, right = matrix[0].length - 1; // 左右边界
while (true) {
// 1. 从左向右遍历上边界
for (let i = left; i <= right; i++) {
res.push(matrix[top][i]);
}
top++; // 上边界下移
if (top > bottom) break; // 边界重叠时退出
// 2. 从上向下遍历右边界
for (let i = top; i <= bottom; i++) {
res.push(matrix[i][right]);
}
right--; // 右边界左移
if (left > right) break;
// 3. 从右向左遍历下边界
for (let i = right; i >= left; i--) {
res.push(matrix[bottom][i]);
}
bottom--; // 下边界上移
if (top > bottom) break;
// 4. 从下向上遍历左边界
for (let i = bottom; i >= top; i--) {
res.push(matrix[i][left]);
}
left++; // 左边界右移
if (left > right) break;
}
return res;
};
# 59.螺旋矩阵 II (opens new window)
function generateMatrix(n) {
let num = 1;
const arr = new Array(n).fill(0).map(() => new Array(n).fill(0));
let left = 0, right = n - 1, top = 0, bottom = n - 1;
while (num <= n * n) {
for(let i = left; i <= right; i++) {
arr[top][i] = num++
}
top++
for(let i = top; i <= bottom; i++) {
arr[i][right] = num++
}
right--
for(let i = right; i >= left; i--) {
arr[bottom][i] = num++
}
bottom--
for(let i = bottom; i >= top; i--) {
arr[i][left] = num++
}
left++
}
return arr;
}
# 61.旋转链表
function rotateRight(head, k) {
if (!head || !head.next || k === 0) return head;
// 计算链表长度 n 并定位尾节点
let tail = head;
let n = 1;
while (tail.next) {
tail = tail.next;
n++;
}
// 计算有效旋转步数
const rotate = k % n;
if (rotate === 0) return head;
// 链表成环
tail.next = head;
// 定位新尾节点（移动 n - rotate - 1 步）
let newTail = head;
for (let i = 0; i < n - rotate - 1; i++) {
newTail = newTail.next;
}
// 设置新头节点并断开环
const newHead = newTail.next;
newTail.next = null;
return newHead;
}
# 66. 加一 (opens new window)
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let { length } = digits;
var needAdd = false;
while(length > 0) {
if (digits[--length] === 9) {
digits[length] = 0
needAdd = true
} else {
digits[length] = digits[length] + 1;
needAdd = false
break
}
}
if (needAdd) {
digits.unshift(1)
}
return digits
};
# 89.格雷编码
直接数学公式解决
function grayCode(n) {
const res = [];
const total = 1 << n; // 总数为 2^n
for (let i = 0; i < total; i++) {
res.push(i ^ (i >> 1)); // 公式计算格雷码
}
return res;
}
# 118.杨辉三角 (opens new window)
给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
var generate = function(numRows) {
const res = [[1]];
for (let i = 1; i < numRows; i++) {
const length = i + 1;
const arr = new Array(length);
const top = res[i - 1] || [];
for (let j = 0; j < length; j++) {
arr[j] = (top[j - 1] || 0) + (top[j] || 0);
}
res.push(arr);
}
return res;
};
# 121.买卖股票的最佳时机 (opens new window)
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
var maxProfit = function(prices) {
if (prices.length < 2) return 0; // 少于2天无法交易
let minPrice = prices[0]; // 初始化最小价格为第一天价格
let maxProfit = 0; // 初始化最大利润为0
for (let i = 1; i < prices.length; i++) {
minPrice = Math.min(minPrice, prices[i]); // 更新历史最低价[1,2](@ref)
maxProfit = Math.max(maxProfit, prices[i] - minPrice); // 更新当前最大利润[2](@ref)
}
return maxProfit; // 返回最终计算结果
};
# 122. 买卖股票的最佳时机 II (opens new window)
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit = 0
for (let i = 1;i < prices.length; i++) {
// 只要后一天大于前一天，就卖出
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit
};
# 141. 环形链表 (opens new window)
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
# 加标记
var hasCycle = function(head) {
while (head !== null) {
if (head.repeat) {
return true
} else {
head.repeat = true
head = head.next
}
}
return false
};
# 快慢指针
var hasCycle = function(head) {
let fast = head, slow = head
while(slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
};
# 142.环形链表 II
# Set
var detectCycle = function(head) {
let next = head;
const set = new Set();
while (next) {
if (set.has(next)) {
return next
}
set.add(next, 1);
next = next.next;
}
return null;
};
# 快慢指针
数学证明：
设头节点到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c（环长 = b + c）。
- 第一次相遇时：
slow路程：a + bfast路程：a + b + k(b + c)（k为快指针绕环圈数）- 由速度关系：
2(a + b) = a + b + k(b + c) - 化简得：
a = c + (k-1)(b + c)
- 结论：头节点到入口的距离
a等于相遇点到入口的距离c加上(k-1)圈环长。因此，两指针分别从头节点和相遇点同速移动，必在环入口相遇
function detectCycle(head) {
if (!head || !head.next) return null; // 边界处理
let fast = head;
let slow = head;
let hasCycle = false;
// 第一阶段：检测环是否存在
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
hasCycle = true;
break;
}
}
// 无环则返回 null
if (!hasCycle) return null;
// 第二阶段：寻找环入口
slow = head; // slow 重置到头部
while (fast !== slow) {
fast = fast.next;
slow = slow.next;
}
return slow; // 或 return fast
}
# 146.LRUCache
# Map
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 缓存容量
this.cache = new Map(); // Map 自动维护插入顺序
}
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
// 删除并重新插入，使 key 成为最新访问项（位于 Map 末尾）
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
// 若 key 已存在，先删除以更新顺序
if (this.cache.has(key)) this.cache.delete(key);
// 插入新键值对（自动置于末尾）
this.cache.set(key, value);
// 容量超限时，删除 Map 的第一个键（最久未使用）
if (this.cache.size > this.capacity) {
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
}
}
# Map+双向链表
class ListNode {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // 映射 key -> ListNode
// 初始化哨兵头尾节点（简化链表操作）
this.head = new ListNode(-1, -1);
this.tail = new ListNode(-1, -1);
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 移动节点到链表头部（表示最新使用）
_moveToHead(node) {
this._removeNode(node);
this._addToHead(node);
}
// 删除节点
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 在头部添加节点
_addToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
// 删除尾节点（最久未使用）
_removeTail() {
const node = this.tail.prev;
this._removeNode(node);
return node; // 返回被删节点，用于清除 Map
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._moveToHead(node); // 更新为最近使用
return node.val;
}
put(key, value) {
if (this.cache.has(key)) {
// 更新值并移动到头部
const node = this.cache.get(key);
node.val = value;
this._moveToHead(node);
} else {
// 创建新节点
const newNode = new ListNode(key, value);
this.cache.set(key, newNode);
this._addToHead(newNode);
// 容量超限时删除尾节点
if (this.cache.size > this.capacity) {
const tailNode = this._removeTail();
this.cache.delete(tailNode.key);
}
}
}
}
# 148.排序链表 (opens new window)
# 自顶向下递归归并
// 合并两个有序链表
function merge(l1, l2) {
const dummy = new ListNode(0);
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 || l2; // 拼接剩余部分
return dummy.next;
}
function sortList(head) {
if (!head || !head.next) return head;
// 快慢指针找中点（slow 停在中点前一个节点）
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 分割链表
const mid = slow.next;
slow.next = null;
// 递归排序左右子链表
const left = sortList(head);
const right = sortList(mid);
// 合并有序链表
return merge(left, right); // 复用上述 merge 函数
}
# 自底向上归并排序
function sortList(head) {
if (!head || !head.next) return head;
// 1. 计算链表长度
let length = 0;
let node = head;
while (node) {
length++;
node = node.next;
}
// 2. 初始化哑节点用于连接合并后的链表
const dummy = new ListNode(0);
dummy.next = head;
// 3. 子链表长度从 1 开始，每次翻倍（1→2→4→8...）
for (let size = 1; size < length; size *= 2) {
let curr = dummy.next; // 当前待合并段的起始节点
let tail = dummy; // 已合并链表的尾部
while (curr) {
// 3.1 切割左子链表（长度为 size）
const left = curr;
const right = cut(left, size); // 切割右子链表
curr = cut(right, size); // 剩余链表作为下一段
// 3.2 合并左右子链表
tail.next = merge(left, right);
// 3.3 移动 tail 到合并后链表的末尾
while (tail.next) {
tail = tail.next;
}
}
}
return dummy.next;
}
// 从 head 开始切割长度为 n 的子链表，返回剩余部分的头节点
function cut(head, n) {
let node = head;
while (--n > 0 && node) {
node = node.next;
}
if (!node) return null;
const next = node.next;
node.next = null; // 切断链表
return next;
}
// 合并两个有序链表
function merge(l1, l2) {
const dummy = new ListNode(0);
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 || l2; // 拼接剩余部分
return dummy.next;
}
# 155.最小栈 (opens new window)
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
var MinStack = function() {
this.stack = []; // 主栈，存储所有元素
this.minStack = []; // 辅助栈，存储当前最小值
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
// 若辅助栈为空，或新值 ≤ 辅助栈栈顶值，则将其加入辅助栈
if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
const val = this.stack.pop();
// 若弹出的值等于辅助栈栈顶值（即当前最小值），则同步弹出辅助栈顶
if (val === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1]; // 返回主栈栈顶
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.minStack[this.minStack.length - 1]; // 返回辅助栈栈顶（即最小值）
};
# 160.相交链表
# Set
占用了空间
var getIntersectionNode = function(headA, headB) {
const visited = new Set();
let cur = headA;
while (cur) {
visited.add(cur);
cur = cur.next;
}
cur = headB;
while (cur) {
if (visited.has(cur)) return cur;
cur = cur.next;
}
return null;
};
# 双指针
如果长度一样，直接就能匹配出来
如果长度不一样，交替循环，类似快慢指针，也可以找出来
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; // 相遇点或 null
};
# 长度差
长度不一样的话，前面的肯定是没用的，直接走过去，再进行比较
const getListLen = (head) => {
let len = 0, cur = head;
while (cur) {
len++;
cur = cur.next;
}
return len;
};
var getIntersectionNode = function(headA, headB) {
let lenA = getListLen(headA), lenB = getListLen(headB);
let curA = headA, curB = headB;
// 长链表先走差值步
if (lenA > lenB) {
for (let i = 0; i < lenA - lenB; i++) curA = curA.next;
} else {
for (let i = 0; i < lenB - lenA; i++) curB = curB.next;
}
// 同步遍历找交点
while (curA !== curB) {
curA = curA.next;
curB = curB.next;
}
return curA;
};
# 190.颠倒二进制位 (opens new window)
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
**输入：**n = 43261596
**输出：**964176192
# 字符串操作
var reverseBits = function(n) {
// 将 n 转换为二进制字符串，并填充到 32 位
const binaryStr = n.toString(2).padStart(32, '0');
// 将字符串转换为数组，反转数组，再连接回字符串
const reversedStr = binaryStr.split('').reverse().join('');
// 将反转后的二进制字符串解析为整数
return parseInt(reversedStr, 2);
};
# 238.除自身以外数组的乘积 (opens new window)
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
# 左右乘积
左边开始的乘积，和右边开始的乘积
左右相乘即是当前位的左右乘积
function productExceptSelf(nums) {
const n = nums.length
const left = new Array(n).fill(1)
const right = new Array(n).fill(1)
for (let i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1]
}
for (let j = n - 2; j >= 0; j--) {
right[j] = right[j + 1] * nums[j + 1]
}
const res = [];
for (let k = 0; k < n; k++) {
res.push(left[k] * right[k])
}
return res;
}
# O(1)空间
左乘积依旧，右乘积边乘边算
function productExceptSelf(nums) {
const n = nums.length
const res = new Array(n).fill(1)
for (let i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1]
}
let R = 1
for (let j = n - 1; j >= 0; j--) {
res[j] *= R
R *= nums[j]
}
return res;
}
# 350. 两个数组的交集 II (opens new window)
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
// 1.map版
// const map = new Map()
// nums1.forEach(item => {
// if (map.has(item)) {
// map.set(item, map.get(item) + 1)
// } else {
// map.set(item, 1)
// }
// })
// const res = []
// nums2.forEach(item => {
// const itemNum = map.get(item)
// if (itemNum) {
// res.push(item)
// map.set(item, itemNum - 1)
// }
// })
// return res
// 2.双指针
nums1 = nums1.sort((a,b) => a - b)
nums2 = nums2.sort((a,b) => a - b)
let i = 0, j = 0, k = 0
while (i < nums1.length && j < nums2.length) {
const item1 = nums1[i]
const item2 = nums2[j]
if (item1 === item2) {
nums1[k] = item1
i++
j++
k++
} else if (item1 < item2) {
i++
} else if (item1 > item2) {
j++
}
}
return nums1.splice(0, k)
};
# 冒泡排序
const {length} = arr === length = arr.length
普通版
let j=0;j<length-1 不减去i
改进版
function sort (arr) {
const {length} = arr
for (let i=0;i<length-1;i++){
for (let j=0;j<length-1-i;j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(sort(arr))
# 选择排序
找到最小的那个与当前的交换
function selectionSort (arr) {
const {length} = arr
let indexMin
for (let i=0;i<length-1;i++){
indexMin = i
for (let j=i;j<length;j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j
}
}
if (i !== indexMin) {
[arr[indexMin], arr[i]] = [arr[i], arr[indexMin]]
}
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(selectionSort(arr))
# 插入排序
找到之前比本次小的，插到后面
function sort (arr) {
const {length} = arr
let temp
for (let i=1;i<length;i++){
let j = i
temp = arr[i]
while (j>0 && arr[j-1] > temp) {
arr[j] = arr[j-1]
j--
}
arr[j] = temp
}
return arr
}
let arr=[1,4,65,2,67,3,8,22,6]
console.log(sort(arr))
# 归并排序
Array.prototype.mergeSort = function() {
const rec = (arr) => {
if (arr.length === 1) return arr
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
const orderLeft = rec(left)
const orderRight = rec(right)
const res = []
while(orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderLeft.length) {
res.push(orderLeft.shift())
} else if (orderRight.length) {
res.push(orderRight.shift())
}
}
return res
}
rec(this)
}
const arr = [7,3,5,1]
arr.mergeSort()
function mergeSort (arr) {
const {length} = arr
if (length === 1) return arr
const mid = Math.floor(length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, length)
const orderLeft = mergeSort(left)
const orderRight = mergeSort(right)
let res = []
while (orderLeft.length > 0 || orderRight.length > 0) {
if (orderLeft.length > 0 && orderRight.length > 0) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderRight.length) {
res.push(orderRight.shift())
} else if (orderLeft.length) {
res.push(orderLeft.shift())
}
}
return res
}
# 快排
Array.prototype.quickSort = function() {
const rec = (arr) => {
if (arr.length === 0 || arr.length === 1) return arr
const mid = arr[0]
const left = []
const right = []
for (let i = 1; i< arr.length; i++) {
if (arr[i] <mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((n, i) => this[i] = n)
}
const arr = [7,3,5,1]
arr.quickSort()
function quickSort(arr) {
const {length} = arr
if ([0, 1].includes(length)) return arr
let mid = arr[0]
let left = []
let right = []
for (let i = 1; i < length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), mid, ...quickSort(right)]
}
# 斐波那契
# 方法一：普通递归
function fibonacci(n) {
if ([1, 2].includes(n)) return 1;
return fibonacci(n - 2) + fibonacci(n - 1);
}
f: 1901.197998046875 ms
缺点：存在重复计算，容易爆栈
# 方法二：改进递归，作为函数参数
function fibonacci(n) {
function fib(n, v1, v2) {
if (n === 1) {
return v1
} else if (n === 2) {
return v2
} else {
return fib(n - 1, v2, v1 + v2)
}
}
return fib(n, 1, 1)
}
f: 7.71484375 ms
# 方法三：改进递归，用数组记录
function fibonacci(n) {
let memo = [0, 1]
function fib(n) {
if (memo[n] === undefined) {
memo[n] = fib(n - 1) + fib(n - 2)
}
return memo[n]
}
return fib(n)
}
f: 14.156005859375 ms
# 方法四： for循环
function fibonacci(n) {
let n1 = 1, n2 = 1
for (let i = 2; i < n; i++) {
[n1, n2] = [n2, n1 + n2]
}
return n2
}
f: 5.817138671875 ms
# 运行耗时
let x = 1
console.time('f')
while (x < 10000) {
fibonacci(20)
x++
}
console.timeEnd('f')
普通递归>改进递归>for循环
# other
# 倒水问题
9l 4l 6l
得出x%9=6
找出x能整除4即可知道4往9倒多少次能得到6
# 非负整数组，拼出最大值
冒泡排序，比较当前值拼上前一个值的数是否大于前一个值的数拼上当前值
function findMaxNum (str) {
for (let i = 0; i < str.length; i++) {
for (let j = str.length - 1; j > i; j--) {
if (str[j] + '' + str[j-1] > str[j-1] + '' + str[j]) {
[str[j], str[j - 1]] = [str[j-1], str[j]]
}
}
}
return str.join('')
}
console.log(findMaxNum([10,50,54,45,9,7,8,5,5,4,44,46,456]))
# 去掉字符串中的空格并输出空格数
function empty (str) {
let num = 0
for (let i = 0; i < str.length; i++) {
const char = str[i]
if (char === ' ') {
str = str.substring(0, i) + str.substring(i + 1, str.length)
i--
num++
}
}
return {
str,
num
}
}
console.log(empty('s t t x'))
# 猴子吃桃
function monkey (n) {
let nums = 1
for (let i = n; i > 0; i--) {
nums = (nums + 1 ) * 2
}
console.log(nums)
}
monkey(9)
# 洗牌
一：简单版
缺点 改变原数组 且时间复杂度为O(n2)
function shuffle(arr) {
let random, result = []
while (arr.length) {
random = Math.floor(Math.random() * arr.length)
result.push(...arr.splice(random, 1))
}
return result
}
二：随机取前面一个与递减的最后一个交换
function shuffle(arr) {
let random, n = arr.length
while (n > 0) {
random = Math.floor(Math.random() * n--)
let temp = arr[n]
arr[n] = arr[random]
arr[random] = temp
}
return arr
}
# 寻找数组中，该元素大于左侧的所值，小于右侧的所有值
遍历找到当前位置的左侧最大值以及右侧最小值
当位置相同时则为解
function findNum (arr) {
const length = arr.length
let up = [], down = []
let max = 0, min = arr[length - 1]
let result = []
for (let i = 0; i < length; i++) {
max = Math.max(max, arr[i])
up.push(max)
}
for (let i = length - 1; i >= 0; i--) {
min = Math.min(min, arr[i])
down.push(min)
}
down.reverse()
for (let i = 0; i < length; i++) {
if (up[i] === down[i] && i !== length - 1) {
result.push(up[i])
}
}
return result.length ? result : -1
}
console.log(findNum([7,10,2,6,19,22,32]))
# 先投硬币
第一个人正面的概率
1-另一人没抛出的概率
等比前n项求和
1- (1/2 * 1/2 + 1/2 * 1/2 * 1/2 * 1/2 + ....) =
1- ((1/4) + (1/4)^2 + ... + (1/4)^(n/2)
= 1- (1/4)(1- (1/4) ^ (n/2)) / (1- 1/4)
在 n 趋于无穷大的时候，1-(1/4)^(n/2)为 1
所以上面的式子变成 1-1/3 = 2/3
# 有1000瓶水，其中有一瓶有毒 (opens new window)
给1000个瓶分别标上如下标签（10位长度）：
0000000001 （第1瓶） 0000000010 （第2瓶） 0000000011 （第3瓶） ...... 1111101000 （第1000瓶） 从编号最后1位是1的所有的瓶子里面取出1滴混在一起（比如从第一瓶，第三瓶，。。。里分别取出一滴混在一起）并标上记号为1。以此类推，从编号第一位是 1的所有的瓶子里面取出1滴混在一起并标上记号为10。现在得到有10个编号的混合液，小白鼠排排站，分别标上10，9，。。。1号，并分别给它们灌上对 应号码的混合液。24小时过去了，过来验尸吧： 从左到右，死了的小白鼠贴上标签1，没死的贴上0，最后得到一个序号，把这个序号换成10进制的数字，就是有毒的那瓶水的编号。
检验一下：假如第一瓶有毒，按照0000000001 （第1瓶），说明第1号混合液有毒，因此小白鼠的生死符为0000000001（编号为1的小白鼠挂了），0000000001二进制标签转换成十进 制=1号瓶有毒；假如第三瓶有毒，0000000011 （第3瓶），第1号和第2号混合液有毒，因此小白鼠的生死符为00000011（编号为1，2的鼠兄弟挂了），0000000011二进制标签转换成十进 制=3号瓶有毒。
至于这个算法的证明，大概的思路如下：有毒的水，喂食的那几条小狗肯定都会死，剩下的都不会死，只需要说明唯一性就可以了。10条小狗死亡情况的可能性，正好是2^10=1024，跟水瓶一一对应还是没问题的。
# 扔鸡蛋
100楼往下扔鸡蛋
1.从下往上
o(n)
2.二分查找
最坏时比1还多一次
3.每十层投一次
最多19次
# 判断两个升序数组其中一个是另外一个数组的子集
- 数组N的所有元素都能在数组M中找到；
- 数组N项中元素重复项的个数不能大于数组M中元素重复项的个数。
function isSubset(arrM,arrN){//两数组均为升序排序
let m = arrM.length;
let n = arrN.length;
let i = 0, j = 0;
while(m > n && i < m && j < n){
if(arrM[i] < arrN[j]){//M数组有重复项
i++;
}else if(arrM[i] > arrN[j]){//N数组重复项数大于M数组重复项数
return false;
}else{//两项相等
i++;
j++;
}
}
if(j < n){//N数组元素不全在M数组内
return false;
}else{
return true
}
}
let arrM = [1,2,2,3,3,4,4,5,5]
let arrN = [1,2,3,4,5]
console.log(isSubset(arrM,arrN))//true
# 扑克牌同花顺
现在有54张扑克牌，抽出5张牌，求出同花顺的概率，A代表1，且顺子不能重复
一种花色有9种可能a1234~910jqk
4种就有36种可能
所以是36/c54(5)
参考思路：
一把扑克除去大、小王，任意选3张或者5张出现同花顺的概率？任意选三张出现豹子的概率（三张同样数字）?任意三张组合有多少顺子？
五张与三张算法一样，只分析三张的情况：一副牌任选三张共有种组合。同花：共种组合；概率为1144/22100=0.05176顺子：假定顺子为A23到JQK共11个，不区分花色A23的顺子有种，同理任何固定顺序的顺子都是64种组合，这样一副牌有64*11=704个顺子；概率为704/22100=0.031855。同花顺：每个花色从A23到JQK有11个顺子，全副牌共44个同花顺；概率为44/22100=0.00199。豹子：共个；概率为52/22100=0.00235。
# 字符串找最长升序的数字
字符串，串中有字母也有阿拉伯数字，需要你从字符串中找到连续，是升序且串长度是符合前两个条件的前提下最长的串，比如说"abc123d2345f45e43"，将字符串"2345"找到并返回。
function findUpNumber (str) {
let left = 0, right = 0
let maxLeft = 0, maxRight = 0
for (let i = 0; i < str.length; i++) {
const char = str[i]
if (isNaN(char)) {
left = i + 1
} else {
// 是数字
const nextChar = str[i + 1]
// 下一个是数字且大于上一个
if (!isNaN(nextChar) && nextChar > char) {
right = i + 1
} else {
left = i + 1
right = i + 1
}
}
// 每次找完记录下最长的位置
if (right - left > maxRight - maxLeft) {
maxLeft = left
maxRight = right
}
}
return maxRight > maxLeft ? str.substring(maxLeft, maxRight + 1) : 'not valid data'
}
console.log(findUpNumber('ab43c1d234f4e43'))
# 货币格式化
正则
function numberWithCommas(n) {
// 正则解释: 匹配到 \B(非单词边界)后, 后面要匹配到 (\d{3})+(?!\d)
// (\d{3})+ 至少匹配到一次或多次三个数字
// (?!\d) 同时后面不是数字的话, 就匹配.
// 注意, 后面的(?=)那一段代码只是判断的规则, 匹配到后只替换掉\B
// 而\B 元字符匹配的是非单词边界
let num = n.toString().split('.');
num[0] = num[0].replace(/\B(?=(\d{3})+(?!\d))/g, ',');
return num.join('.');
}
console.log(numberWithCommas(12345678912.1234)) // "12,345,678,912.1234"ss
蠢方法
var dealNumber = function (money) {
if (money && money != null) {
money = String(money);
var left = money.split('.')[0], right = money.split('.')[1];
right = right ? (right.length >= 2 ? '.' + right.substr(0, 2) : '.' + right + '0') : '.00';
var temp = left.split('').reverse().join('').match(/(\d{1,3})/g);
console.log(temp)
return (Number(money) < 0 ? "-" : "") + temp.join(',').split('').reverse().join('') + right;
} else if (money === 0) { //注意===在这里的使用，如果传入的money为0,if中会将其判定为boolean类型，故而要另外做===判断
return '0.00';
} else {
return "";
}
};
console.log(dealNumber(12451331.22))
# 大整数相加
// bigNumberA和bigNumberB使用字符串存储，否则会自动转化为科学计数
let bigNumberAdd = (bigNumberA, bigNumberB) => {
let A = (bigNumberA + '').split('');
let B = (bigNumberB + '').split('');
let aLen = A.length, bLen = B.length, cLen = Math.max(aLen, bLen) + 1;
let result = [], prefix = 0;
for (let i = 0; i< cLen -1; i++ ) {
let a = aLen - i - 1 >= 0 ? parseInt(A[aLen - i - 1]) : 0, b = bLen - i - 1 >= 0 ? parseInt(B[bLen - i - 1]) : 0;
result[i] = (a + b + prefix) % 10;
prefix = Math.floor((a + b + prefix) / 10);
}
return result.reverse().join('');
};
bigNumberAdd('45486646468484544661134868968','544545867466464646');
# rgb排序
给定一个字符串里面只有"R" "G" "B" 三个字符，请排序 (opens new window)，最终结果的顺序是R在前 G中 B在后。时间复杂度为O(n),空间复杂度O(1)
function sortRGB(str) {
const length = str.length
let rLength = 0
let bLength = 0
for (let i = 0; i < length; i++) {
const char = str[i]
if (char === 'R') {
if (i !== rLength) {
str = str.substring(0, rLength) + 'R' + str.substring(rLength, i) + str.substring(i + 1, length)
}
rLength++
} else if (char === 'B') {
if (i < length - bLength) {
str = str.substring(0, i) + str.substring(i + 1, length) + 'B'
i--
}
bLength++
}
}
return str
}
console.log(sortRGB('BRGBRGRRGBBGBGR'))
function sortRGB(str) {
return str.split('').sort((a, b) => b > a ? 0 : -1).join('')
}
console.log(sortRGB('BRGBRGRRGBBGBGR'))
for循环记录次数
for循环拼出来
# 油漆比例
两桶油漆，A桶全是红色油漆，B桶全是蓝色油漆，将A桶中取一勺倒入B中，再从B桶中取一勺倒入A中，求A桶的蓝红比例和B桶的红蓝比例，是大于、小于还是等于？
x,y
然后算比例就可以了
最后是相等
# 扑克概率
52张扑克牌，取一张不放回，再取一张， 两张为相同颜色的概率是多少？
（1/4） * （12 /51）