算法题
本文最后更新于：2022年4月21日 上午
两数之合
function twoSum(arr, target) {
let res = [];
let map = new Map();
// 使用数值->索引建立map
// 每次循环计算得出当前差值
// 在map中查找这个差值既能得出索引
for (let i = 0; i < arr.length; i++) {
let k = target - arr[i];
if (map.has(k)) {
res.push([map.get(k), i]);
}
map.set(arr[i], i);
}
return res.length === 1 ? res[0] : res;
}
排序数组的两数之和
function twoSum(nums, target) {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const curSum = nums[l] + nums[r];
if (curNum === target) return [nums[l], nums[r]];
if (curNum > target) {
r--;
} else {
l++;
}
}
return false;
}
三数之合
求出数组中三个数之和等于 target 的所有组合
function threeSum(arr, target) {
let res = [];
let len = arr.length;
if (len < 3) return res;
arr = arr.sort((a, b) => a - b);
// 按大小排序
// 开始循环
for (let i = 0; i < len; i++) {
if (arr[i] >= target) break;
// 第一个值就大于target后面不用想了
if (arr[i] === arr[i - 1]) continue;
// 跳过重复的值
let first = i,
second = i + 1,
third = len - 1;
while (second < third) {
const sum = arr[first] + arr[second] + arr[third];
if (sum === target) {
res.push([arr[first], arr[second], arr[third]]);
second++;
third--;
// 移动一次指针再跳过重复项
while (arr[second] === arr[second - 1]) {
second++;
}
while (arr[third] === arr[third + 1]) {
third--;
}
}
//移动指针
if (sum > target) third--;
if (sum < target) second++;
}
}
return res;
}
最大面积
给定数组，按数组 index 为 x 轴坐标,value 为 y 轴坐标在二纬坐标系画线，连接哪两条线时得到最大面积
> 面积 = 两直线中较短的高度 \* 两线间距离
function maxArea(height) {
let l = 0;
let r = height.length - 1;
let res = 0;
while (l < r) {
res = Math.max(res, (r - l) * Math.min(height[l], height[r]));
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return res;
}
删除排序数组中的重复项，不能使用额外空间，返回不重复的长度
function removeDuplicates(arr) {
let i = 0;
let len = arr.length;
for (let j = 1; j < len; j++) {
if (arr[j] !== arr[j - 1]) {
arr[++i] = arr[j];
}
}
return i + 1;
}
设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val) ：当元素 val 不存在时，向集合中插入该项。
remove(val) ：元素 val 存在时，从集合中移除该项。
getRandom ：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
// map方法
function RandomSet(){
this.map = new Map()
this.values = []
}
RandomSet.prototype.insert = function(val){
if(this.map.has(val)) return false
this.map.set(val,values.length)
// 插入后的索引（插入前的数组长度）
this.values.push(val)
return true
}
RandomSet.prototype.remove = function(val){
if(!this.map.has(val)) return false
let index = this.map.get(val)
// 判断在尾部
// 似乎也可以用头部
if(index === this.values.length - 1){
this.map.delete(value)
this.values.pop()
}else{
// 不在尾部
// values用尾部元素填充该位置
// map中修改索引
let last = this.values.pop()
// 赋值
this.values[index] = last
this.map.set(last,index)
this.map.delete(val)
}
return val
}
RandomSet.prototype.getRandom = function(){
let len = this.values.length
let index = Math.floor(Math.random()*len)
return this.values[index]
}
// set方法
// set是不重复的值的集合
function RandomSet(){
this.data = new Set()
}
RandomizedSet.prototype.insert = function(val){
if(this.data.has(val)) return false
this.set.add(val)
return true
}
RandomizedSet.prototype.remove = function(val){
if(!this.data.has(val)) return false
this.set.delete(val)
return val
}
RandomizedSet.prototype.getRandom = function(){
let len = this.values.length
let index = Math.floor(Math.random()*len)
return [...this.data][index]
}
合并两个有序数组
// arr1 = [1,2,5] m=3
// arr2 = [2,3,4] n=3
// 假设arr1能装下arr2
function mergeArr(arr1, m, arr2, n) {
let index1 = m - 1;
let index2 = n - 1;
let index = m + n - 1;
while (index >= 0) {
if (index2 < 0) {
// arr2耗尽
// 剩下保持arr1的值
arr1[index--] = arr2[index2--];
continue;
}
arr1[index--] = arr1[index1] >= arr2[index2] ? arr1[index1--] : arr2[index2--];
}
}
计算两个数组的交集
function intersection(arr1, arr2) {
return [...new Set(arr1.filter((item) => arr2.includes(item)))];
}
计算多个数组的交集
function intersection(...arrs) {
if (arrs.length === 0) return [];
if (arrs.length === 1) return arrs[0];
return [
...new Set(
arrs.reduce((pre, next) => {
// reduce累加器，每一次的return作为下一次累加的pre，你咋这也能忘
// 后还能添加参数手动制定第一次累加的pre值
return pre.filter((item) => next.includes(item));
})
),
];
}
大数相乘(可以输出字符串)
function bigMulti(x, y) {
if (x === "0" || y === "0") return "0";
if (x === "1") return y;
if (y === "1") return x;
const len1 = x.length;
const len2 = y.length;
const pos = new Array(len1 + len2).fill(0);
let num1, num2, mulit, cur;
for (let i = len1 - 1; i >= 0; i--) {
num1 = x[i];
for (let j = len2 - 1; j >= 0; j--) {
num2 = y[j];
mulit = num1 * num2;
cur = mulit + pos[i + j + 1];
pos[i + j + 1] = cur % 10;
pos[i + j] += (cur / 10) | 0; // 取10位以上部分
}
}
let res = pos.join("");
console.log(res);
while (res[0] === "0") {
res = res.substring(1);
}
return res;
}
保留精度加法
const fixAdd = (x, y) => {
const len1 = x.split(".")[1].length;
const len2 = y.split(".")[1].length;
const maxLen = len1 >= len2 ? len1 : len2;
const times = maxLen * 10;
return (x * times + y * times) / times;
};
满 9 加 1
function add1(num) {
for (let dig = num.length - 1; dig >= 0; dig--) {
if (num[dig] === 9) {
num[dig] = 0;
} else {
num[dig]++;
return num;
}
}
num.unshift(1);
return num;
}
将数组中的 0 全部移动到最后且非 0 部分保持原顺序
function move0(num) {
let i = 0;
let j = 0;
while (i < num.length) {
if (num[i] !== 0) {
[mim[i], num[j]] = [num[j], num[i]];
i++;
j++;
} else {
i++;
}
}
}
数的次方（不使用内置库 pow
// 如果指数n是偶数，x^n = x^(n/2) * x^(n/2)
// 如果指数n是奇数，x^n = x * x^(n/2) * x^(n/2)
function myPow(x, n) {
function _pow(base, ex) {
if (ex === 0) return 1;
if (ex === 1) return base;
const splitPow = _pow(base, Math.floor(ex / 2));
return ex % 2 ? base * splitPow * splitPow : splitPow * splitPow;
}
const res = _pow(x, Math.abs(n));
return n < 0 ? 1 / res : res;
}数字的开方 （不使用内置库 pow 和 X ** X
// 返回值只保留整数部分 ，8 => 2
function mySqrt(num) {
let l = 0;
let r = num;
// 左右指针重合后跳出
while (l <= r) {
// 计算一次当前的中间值
const mid = Math.floor((r - l) / 2) + l;
// const mid = (r-l) >> 1 + l
const curPow = mid * mid;
if (mid <= num) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return r;
}输出 1 到最大的 n 位数
/**
/ @params n=1 一位数，最大9，输出123456789
/ @params n=2 两位数呀 最大99
*/
function printNumbers1(n) {
//组合字符串
let str = "";
while (n > 0) {
str += "9";
n--;
}
str = Number(str);
const res = [];
for (let i = 1; i <= str; i++) {
res.push(i);
}
return res;
}
function printNumbers1(n) {
//最大值就是 10^n-1......
const max = 10 ** n - 1;
const res = new Array(max).fill(1);
return res.map((v, i) => v + i);
}和为 s 的所有正数序列
/**
* 15
* [1,2,3,4,5] [4,5,6] [7,8]
*/
function findContinuousSequence(target) {
// 直接用滑动窗口套
let l = 1;
let r = 2;
let sum = 3;
const res = [];
while (l < r) {
if (sum === target) {
const ret = [];
for (let i = j; i <= r; i++) {
ret.push(i);
}
sum -= l;
l++;
} else if (sum > target) {
sum -= l;
l++;
} else {
r++;
sum += r;
}
}
return res;
}
// 滑动窗口的另外一种实现
function findContinuousSequence(target) {
const max = target % 2 === 0 ? target / 2 : Math.round(target / 2);
// max右边都不可能满足
// t = 9
// max = 1，2，3，4，5，6[x]，7[x]，8[x]
const window = [];
const res = [];
let sum = 0;
for (let i = 1; i <= max; i++) {
window.push(i);
sum += i;
while (sum > target) {
sum -= window.shift();
}
if (sum === target) {
window.length > 1 && res.push([...window]);
//FIXME:
// 注意！！
// push window的浅拷贝
}
}
return res;
}数组中出现次数超过数组长度一半的元素
// 一定会是排序后的数组中点
function majorityElement(nums) {
nums = nums.sort();
return nums[Math.floor(nums.length / 2)];
}
// 投票记数
function majorityElement(nums) {
let vote = 1;
// 前后元素相同投票加1，不同减1，票数抵消则计算后面的元素
let mid = nums[0];
for (let num of nums) {
if (vote === 1) {
mid = num;
}
vote += num === mid ? 1 : -1;
}
return mid;
}圆圈中最后剩下的数字
0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
// 朴朴素素超时方法
function lastRemaining(n, m) {
const arr = new Array(n).fill(0).map((v, i) => (v += i));
let pos = 0;
while (arr > 1) {
pos = (pos + m - 1) % arr.length;
arr.splice(pos, 1);
}
return arr[0];
}
// 找规律
// 约瑟夫环
function lastRemaining(n, m) {
// 0，1，2，3，4，5...n-1,n
// n = 1 时输出 0
// 反推得到公式
// n个数字,由于从0开始排列，则索引===数值
// 当前状态用f(n,m)表示，则上一轮为f(n-1,m)
// f(n,m) = (f(n-1,m)+m)%n
if (n === 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
// 也可以使用迭代实现
function lastRemaining(n, m) {
let pos = 0; // n为1时的 剩下0
for (let i = 2; i <= n; i++) {
// 每一轮都根据规律修改
pos = (pos + m) % i;
}
return pos;
}将数组中的奇数移动到前，偶数移动到后
function exchange(nums) {
// 对撞指针
// 分别寻找符合条件的数
let l = 0,
r = nums.length - 1;
while (l < r) {
while (l < r && nums[l] % 2 !== 0) l++;
while (l < r && nums[r] % 2 === 0) r--;
[nums[l], nums[r]] = [nums[r], nums[l]];
}
return nums;
}
function exchange(nums) {
// 快慢指针
let slow = 0,
fast = 0;
while (fast < nums.length) {
if (nums[fast] % 2 !== 0) {
[nums[slow], nums[fast]] = [num[fast], nums[slow]];
slow++;
}
fast++;
}
return nums;
}青蛙跳台阶/斐波那契数列
> 注意别搞混了，fibonacci 数列排列是固定的
> fib 数列 [0,1,1,2,3]
> 青蛙跳法 [1,1,2,3,5]
function numWays(n) {
if (n <= 2) return n;
let res = 0;
let i = 2;
let cur = 2;
let pre = 1;
while (i++ < n) {
// 从n=3时迭代推导
res = cur + pre;
pre = cur;
cur = res;
}
return res;
}
function numWays(n) {
// 斐波那契数列
const arr = [0, 1];
for (let i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[i];
}
// 长度为n的斐波那契数组生成器
function fibonacciArray(n) {
return new Array(n).fill(0).reduce((acc, cur, i) => {
return acc.concat(i > 1 ? acc[i - 1] + acc[i - 2] : o);
}, []);
}
function Fibonacci(n) {
if (n === 0) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
// 尾递归版本
function Fibonacci(n, b1 = 1, b2 = 1, c = 3) {
if (n < 3) {
return 1;
} else {
if (n === 3) {
return c;
} else {
return Fibonacci(n, b2, b1 + b2, c + 1);
}
}
}连续子数组的和的最大值
function maxSubArray(nums) {
// 用dp记录该位置作为子数组末尾的累加值
// [nums[0],nums[1]],dp[1] = num[0] + num[1]
// dp[2] = dp[1] + nums[2]
// 同时判断前一dp的值正负
// 前一个dp为正则 当前dp = 前dp + 当前nums
// 如果为负直接丢弃
if (nums.length < 2) return nums[0];
let max = nums[0];
let dpi = nums[0];
for (let i = 1; i < nums.length; i++) {
dpi = dpi > 0 ? dpi + nums[i] : nums[i];
max = Math.max(max, dpi);
}
return max;
}反转嵌套数组
// 已知数组 a=[1,[2,[3,[4,null]]]], 实现数组 b=[4,[3,[2,[1,null]]]] ，考虑n级嵌套的情况
const a = [1, [2, [3, [4, null]]]];
function reverseArray(arr) {
function reverse(arr, temp) {
// arr = [1,[2,[3,[4,null]]]]
// arr = [1,[2,[3,[4,null]]]][1] = [2,[3,[4,null]]]
// arr = [1,[2,[3,[4,null]]]][1][1] = [3,[4,null]]
// arr = [1,[2,[3,[4,null]]]][1][1][1] = [4,null]
if (arr[1] === null) {
return [arr[0], temp];
// return
}
temp = temp ? [arr[0], temp] : [arr[0], null];
// temp = [1,null]
// temp = [2,[1,null]]
// temp = [3,[2,[1,null]]]
return reverse(arr[1], temp); // 递归进嵌套
}
return reverse(arr, null);
}
console.log(reverseArray(a));约瑟夫环
0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
// 递归公式
// f(n,m) = (f(n-1,m)+m)%n 本轮索引=上轮索引+m%n
function lastRemaining(n, m) {
if (n === 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
function lastRemaining(n, m) {
let i = 0;
for (let j = 2; j <= m; j++) {
i = (i + m) % j;
}
return i;
}连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 状态转移
// 由连续元素来求和
// dp[i] 位置的累加值由dp[i-1]决定，dp[i-1]不为负则加上dp[i-1]
function maxSubArray(nums) {
if (nums.length < 2) return nums;
let max = nums[0];
const dp = [nums[0]];
for (let i = 1; i < nums.length; i++) {
dp[i] = dp[i - 1] > 0 ? nums[i] + dp[i - 1] : nums[i];
if (dp[i] > max) max = dp[i];
}
return max;
}
// 使用变量记忆dp[i-1]的值
function maxSubArray(nums) {
if (nums.length < 2) return nums;
let max = nums[0];
let preDp = 0; // init 0
let curDp;
for (let n of nums) {
curDp = n;
curDp += preDp > 0 ? preDp : 0;
if (curDp > max) max = curDp;
preDp = curDp;
}
return max;
}[0 ~ n-1]中缺省的值
// 正确的数组应该value===index
// [0,1,3] => 2
// [1,2] => 0
function missingNumber(nums) {
for (let i = 0; i < nums.length; i++) {
if (i !== nums[i]) return i;
}
}
function missingNumber(nums) {
let l = 0;
let r = nums.length - 1;
while (l >= r) {
let mid = Math.floor((r - l) / 2) + l;
if (mid === nums[mid]) {
// 中间位置数值正确，说明缺省数值在右边
l = mid + 1;
} else {
// 中间数值已经不正确，说明缺省数值在左边
r = mid - 1;
}
}
// 跳出while后r在l的左边
return l;
}输入一个矩形，顺时针打印矩形其中元素
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
];
function spiralOrder(matrix) {
const rowLen = matrix.length;
const columnLen = matrix[0].length;
let top = 0;
let bottom = rowLen - 1;
let left = 0;
let right = columnLen - 1;
const res = [];
while (left <= right && top <= bottom) {
for (let a = left; a <= right; a++) {
res.push(matrix[top][a]);
}
for (let b = top + 1; b <= bottom; b++) {
res.push(matrix[b][right]);
}
if (top >= bottom || left >= right) break;
for (let c = right - 1; c >= left; c--) {
res.push(matrix[bottom][c]);
}
for (let d = bottom; d >= top; d--) {
res.push(matrix[left][d]);
}
left++;
right--;
top++;
bottom--;
}
return res;
}电商 SKU 全排列/笛卡尔积
const attrs = {
names: ["iPhone X", "iPhone XS", "iPhone 11"],
colors: ["黑色", "白色", "红色"],
storage: ["64g", "128G", "256g"],
};
const descartes = function (chunks) {
let res = [];
const keysName = Object.keys(chunks);
// 由于是操作对象,多增加一个keys数组
const helper = function (chunkIndex, prev) {
let curKey = keysName[chunkIndex];
let curChunk = chunks[curKey];
let isLast = chunkIndex === keysName.length - 1;
for (let val of curChunk) {
const cur = prev.concat(`${curKey}:${val}`);
if (isLast) {
// 如果已经处理到数组的最后一项了 则把拼接的结果放入返回值中
res.push(cur);
} else {
helper(chunkIndex + 1, cur);
}
}
};
// 从属性数组下标为 0 开始处理
// 并且此时的 prev 是个空数组
helper(0, []);
return res;
};
1 到 n 的数字组成 k 长度的数组的所有组合
// 输入: n = 4, k = 2;
// 输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
function combine(n, k) {
const res = [];
function helper(start, prev) {
const len = prev.length;
if (len === k) {
res.push(prev);
return;
}
// 剪枝,还能剩下几个空位
const rest = k - len;
for (let i = start; i <= n; i++) {
if (n - i + 1 < rest) {
// 递增关系+1
// n是最大数字,减去当前数字+1
return; // 往后的i都不会符合,直接return
}
helper(i + 1, prev.concat(i));
}
}
helper(1, []);
return res;
}
请你判断一个 9 x 9 的数独是否有效。根据以下规则 ，验证已经填入的数字是否有效
1. 数字 1-9 在每一行只能出现一次。
1. 数字 1-9 在每一列只能出现一次。
1. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
1. 空白为'.'
board = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
];
//输出：true
function isValidSudoku(arr) {
// 用最直白的哈希表，由于要处理顺序递增数组，可以默认全部是0
// 记录index+1位置的数有没有出现过
const rows = new Array(9).fill(0).map(() => new Array(9).fill(0));
const columns = new Array(9).fill(0).map(() => new Array(9).fill(0));
// 9*9的小方块
const blocks = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => new Array(9).fill(0)));
// 开始循环
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const cur = board[i][j];
if (cur === ".") countine; //跳过
const index = +cur - 1;
rows[i][index]++;
columns[j][index]++;
blocks[~~(i / 3)][~~[j / 3]][index]++;
if (rows[i][index] > 1 || columns[j][index] > 1 || blocks[~~(i / 3)][~~[j / 3]][index] > 1) {
return false;
}
}
}
return true;
}
实现 LRU 缓存结构 （最近最少访问
function LRUCache(capacity){
this.capacity = capacity
this.cache = new Map()
}
LRUCache.prototype.get = function(key){
if(this.cache.has(key)){
const val = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key,val)
return val
}else{
return -1
}
}
LRUCache.prototype.put = function(key,value){
if(this.cache.has(key)){
this.cache.delete(key)
}
this.cache.set(key,value)
// 如果容量超标
if(this.cache.size > this.capacity){
// 删除map中的第一个
const latestKey = this.cache.keys().next().value
this.cache.delete(latestKey)
}
}
判断一个数是否是质数/素数
质数：大于 1 的自然数只能被 1 和自身整除的数
sqrt 平方根
function isPrime(num) {
if (num === 0) return false;
for (let i = 2; i < num - 1; i++) {
if (num % i === 0) return false;
}
return true;
}
// 一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)
function isPrime(num) {
if (num === 0) return false;
const sqrt = Math.sqrt(num);
for (let i = 2; i < sqrt; i++) {
if (num % i === 0) return false;
}
return true;
}计算 n 以内的质数数量
var countPrimes = function (n) {
// n之前的数组，先全部默认是质数
// primeArray[i] = true
const primeArray = new Array(n).fill(true);
let primeCount = 0;
for (let i = 2; i < n; i++) {
// 从2开始,由于2是质数,开始推导2派生出去的质数
// 即2的n次+2后都不会是质数了
if (primeArray[i]) {
primeCount++;
for (let j = i * i; j < n; j += i) {
primeArray[j] = false;
}
}
}
return primeCount;
};求出两个数组最长的公共子数组长度
// 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
// 输出：3
// 解释：长度最长的公共子数组是 [3,2,1]
// 动态规划
// 分别用i，j代表在两个数组中的索引
// 当arr1[i] === arr[j]时
// 该位置的公共长度 dp[i][j] = dp[i-1][j-1] + 1
// 建立二维数组dp
function commonLongest(A, B) {
const m = A.length;
const n = B.length;
let res = 0;
// 考虑0的情况，并且dp[x][0]或者dp[0][x]都为0
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// 从长度为0开始，则有一位重合 + 1
if (A[i - 1] === B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}计算岛屿的周长
二维数组，1 为陆地，0 为海水，铺成矩阵，陆地与陆地不会对角接壤（不会出现陆地环绕的海水），求出接壤陆地组成的岛屿的周长（一块陆地四条边）
// grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
function getPerimeter(grid) {
if (!grid || !grid.length || !grid[0].length) return 0;
const row = grid.length;
const col = grid.length;
// 查找第一块陆地
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (grid[i][j] === 1) {
return dfs(i, j);
}
}
}
// 从这个方块的四个方向开始搜索
function dfs(x, y) {
if (x < 0 || y < 0 || x >= row || y >= col) {
// 衍生的方块越过了边界，留下一条边
return 1;
}
if (grid[x][y] === 0) {
// 方块掉进了海里，留下一条边
return 1;
}
if (grid[x][y] === -1) {
// 之前访问过
return 0;
}
// 标记为访问过
grid[x][y] = -1;
// 向四周延伸
return dfs(x + 1, y) + dfs(x - 1, f) + dfs(x, y + 1) + dfs(x, y - 1);
}
return 0;
}
// 找规律 n个陆地，m条边是共享的，则周长 = n*4 - m*2
function getPerimeter(grid) {
if (!grid || !grid.length || !grid[0].length) return 0;
const row = grid.length;
const col = grid.length;
let land = 0;
let shareBorder = 0;
// 查找第一块陆地
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (grid[i][j] === 1) {
land++;
if (i + 1 < row && grid[i + 1][j] === 1) {
shareBorder++;
}
if (j + 1 < col && grid[i][j + 1] === 1) {
shareBorder++;
}
}
}
}
return land * 4 - shareBorder * 2;
}最大公约数（GCD）
使用递归。基本情况是当 y 等于 0 时。在这种情况下，返回 x。否则，返回 y 的 GCD 和 x / y 的其余部分。
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
// gcd (8, 36) -> 4bifurcate
按照布尔值对数组中元素分类
const bifurcate = (arr, filter) => arr.reduce((acc, val, i) => (acc[filter[i] ? 0 : 1].push(val), acc), [[], []]);
bifurcate(["beep", "boop", "foo", "bar"], [true, true, false, true]);
// [ ['beep', 'boop', 'bar'], ['foo'] ]合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
var merge = function(intervals) {
if(!intervals || !intervals.length || intervals.length<2) return intervals
intervals.sort((a,b)=>a[0]-b[0])
const res = []
const len = intervals.length
let pre = intervals[0]
for(let i = 1 ; i < len ; i++){
const cur = intervals[i]
// 如果有重合
if(pre[1]>=cur[0]){
//更新当前处理区间的判断结束位置
pre[1] = Math.max(pre[1],cur[1])
}else{
// 不存在重合了，进入下一个区间
res.push(pre)
pre = cur
}
}
res.push(pre)
return res
};算法题
http://yoursite.com/2022/02/24/算法题/