Appearance
排序算法
动态规划
什么是动态规划？
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它将问题拆分成小问题，并从解决小问题作为起点，从而最终解决问题。
爬梯子问题：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ （注意：给定 n 是一个正整数）
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
a、1 阶 + 1 阶
b、2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
a、1 阶 + 1 阶 + 1 阶
b、1 阶 + 2 阶
c、2 阶 + 1 阶
解析：
走 1 阶台阶只有一种走法，但是走 2 阶台阶有两种走法（如示例1），如果 n 是双数，我们可以凑成 m 个 2 级台阶，每个 m 都有两种走法，如果 n 是单数，那么我们可以凑成 m 个 2 级台阶加上一个 1 级台阶，这样就似乎于一个排列组合题目了，但是开销貌似比较大。
如何将整个问题拆分成一个一个的小问题呢？
这个时候使用动态规划就很有用，简单地我们可以采用首位或者中间态进行一次分析，比如我们从最终态进行分析：走 N 阶台阶，最后一步必定是 1 步或者 2 步到达。
那么 N 阶台阶的走法不就相当于最后走一步和最后走两步的走法的总和吗！换一种方式来说，我们取一个中间态：如果总共有 3 级台阶，3 级台阶的走法只会存在两种大的可能：走了1阶台阶+走两步、走了两级台阶+走一步，即 3 级台阶的所有走法就是走了 1 阶台阶的走法加上走了 2 阶台阶的走法，而 1 阶台阶的走法只有一种，2 阶台阶的走法有 2 种，所有 3 阶台阶的走法有 3 种,我们使用一种更通用的方式进行表达的话就是所谓的状态转换方程：
ways[n] = ways[n-1] + ways[n-2];有了这个公式，我们就可以使用迭代来完成整个过程，寻求到最终的 ways[n] 的值了，迭代的开始即我们已知的确定条件：一阶台阶只有一种走法：ways[1]=1、两阶台阶有两种走法：ways[2]=2，代码如下：
javascript
function climbStairs(n) {
if (n === 1 || n === 2) {
return n;
}
var ways = [];
ways[0] = 1;
ways[1] = 2;
for (var i = 2; i < n; i++) {
ways[i] = ways[i-1] + ways[i-2];
}
return ways[n-1];
}梳理一下基本流程：
从一个现实方案中找到状态转换的特有规律
从特有规律中提取出状态转换方程
找到状态转换方程的迭代初始值（确定值）
解决问题
最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入：
[
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]输出：7
解释: 因为路径 1->3->1->1->1 的总和最小。
解析：
这道题涉及一个最优解问题，现在每一个点都有一个类似权重的值，我们要使这个值最小，假设走到 (m, n) 点时值最小，而走到 (m, n) 点只能从 (m-1, n) 和 (m, n-1) 两个点走过去，那么要保证 (m, n) 点的权重最小，则我们只需要选择走到 (m-1, n) 和 (m, n-1) 权重较小的那一边即可， 那么我们就可以得到新的状态转移方程：
sum[m][n] = MIN(sum[m-1][n], sum[m][n-1]) + table[m][n]即走到当前点的权重=走到前一步权重的较小值+当前点的权重，并且该问题需针对边上元素做特殊处理。
javascript
function minPathSum(grid) {
if (grid && grid.length) {
// 权重存储数组
var sum = new Array(grid.length);
for (var i = 0; i < grid[0].length; i++) {
sum[i] = new Array(grid[0].length);
}
// 起点初始权重确定值
sum[0][0] = grid[0][0];
for (var i = 0; i < grid.length; i++) {
for (var j = 0; j < grid[0].length; j++) {
if (i === 0 && j === 0) {
continue;
}
//边上的权重处理
if (i-1 < 0) {
sum[i][j] = sum[i][j-1] + grid[i][j];
} else if (j-1 < 0) {
sum[i][j] = sum[i-1][j] + grid[i][j];
} else {
sum[i][j] = Math.min(sum[i-1][j], sum[i][j-1]) + grid[i][j];
}
}
}
return sum[grid.length-1][grid[0].length-1];
} else {
throw new Error('Fuck!');
return ;
}
}所有字母组合问题
假设我们给定字母一批字母，在允许任意字母顺序的情况下，我们可以得到多少种长度与输入字母长度相等的字母组合呢？
示例 1:
输入："a"
输出："a"
示例 2:
输入："ab"
输出："ab", "ba"
示例 3:
输入："abc"
输出："abc", "acb", "bac", "bca", "cab", "cba"
实现代码：
javascript
function anagrams (str) {
if (str.length <= 2) {
return str.length === 2 ? [str, str[1] + str[0]] : [str];
}
return str.split('').reduce(
(acc, letter, i) => {
return acc.concat(anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val));
}
, []
);
};计算连续子向量的最大和
给一个数组，返回它的最大连续子序列的和，例如:[6, -3, -2, 7, -15, 1, 2, 2]，连续子向量的最大和为 8（从下标 0 个开始，到小标 3 为止）。
js
function maxSumList(arr) {
let maxv = arr[0];
let result = arr[0];
for (let i = 1; i < arr.length; i++) {
maxv = Math.max(maxv + arr[i], arr[i]);
result = Math.max(maxv, result);
}
return result;
}参考资料：
- 从实例中了解动态规划的基本思想
- js 动态规划实例讲解
- 详解动态规划01背包问题--JavaScript实现
- 详解动态规划最少硬币找零问题--JavaScript实现
- 详解动态规划最长公共子序列--JavaScript实现
二叉树
树拥有很多种结构，二叉树是树中最常用的结构，同时也是一个天然的递归结构。
二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当一颗树的叶数量数量为满时，该树可以称之为满二叉树。
js
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}二分搜索树：
二分搜索树也是二叉树，拥有二叉树的特性。但是区别在于二分搜索树每个节点的值都比他的左子树的值大，比右子树的值小。这种存储方式很适合于数据搜索。
js
class BST {
constructor() {
this.root = null;
this.size = 0;
}
addNode(node, val) {
this.root = _addChild(node, val);
}
// 添加节点时，需要比较添加的节点值和当前
// 节点值的大小
_addChild(node, val) {
if (!node) {
this.size++;
return new Node(val);
}
if (node.value > val) {
node.left = _addChild(node, val);
} else if (node.value < val) {
node.right = _addChild(node, val);
}
return node;
}
}加油站问题(贪心算法)
二分法
二叉树遍历
- 前序遍历：根左右js
preTraversal() { this._pre(this.root); } _pre(node) { if (!node) return; console.log(node.value); this._pre(node.left); this._pre(node.right); } - 中序遍历：左根右js
midTraversal() { this._mid(this.root); } _mid(node) { if (!node) return; _mid(node.left); console.log(node.value); _mid(node.right); } - 后序遍历：左右根js
backTraversal() { this._back(this.root); } _back(node) { if (!node) return; _back(node.left); _back(node.right); console.log(node.value); } - 层序遍历js
levelTraversal() { const root = this.root; const nodes = [root]; while (nodes.length) { const node = nodes.shift(); if (!node) return; console.log(node.value); nodes.push(node.left, node.right); } }
前/中/后序遍历皆为深度遍历，层序遍历为广度遍历，也就是一层层地遍历树。
二叉树反转：
js
reverseTree() {
this._reverse(this.root);
}
_reverse(node) {
if (!node) return;
this._reverse(node.left);
this._reverse(node.right);
const temp = node.left;
node.left = node.right;
node.right = temp;
}二叉树重建：
js
/**
* 根据前序&中序遍历的结果重建二叉树
*/
function rebuildBTree(pre, mid) {
let result = [];
if (pre.length === 1) {
result = {
val: pre[0],
left: null,
right: null
}
} else {
const root = pre.shift();
const rootIdx = mid.findIndex(item => item.val === root.val);
const midLeft = mid.slice(0, rootIdx);
const midRight = mid.slice(midLeft.length, mid.length);
result = {
val: root.val,
left: rebuildBTree(pre.slice(0, midLeft.length), midLeft),
right: rebuildBTree(pre.slice(midRight.length, pre.length))
}
}
return result;
}中序遍历配合另外任何一个遍历，能重建二叉树，即中序+前序、中序+后序、中序+层序可重建二叉树，其他的任意两个序列的组合都不能唯一的确定重建的二叉树。
常见链表操作
单链表反转：
思路：设置 2 个变量，分别记录其前驱 pre 和后继 next，然后不断 cur.next = pre 就可以了
js
function reverseList(head) {
if (!head || !head.next) return head;
let cur = head;
let pre = null;
while (cur) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}链表中环的检测：
思路一：变量标记法，遍历链表且每个遍历项都加上一个唯一标志，若有重复的则链表有环
js
function hasCycle(head) {
let cur = head;
while (cur) {
if (cur.val === 'cycleFlag') {
return true;
}
cur.val = 'cycleFlag';
cur = cur.next;
}
return false;
};思路二：快慢指针法，定义快慢 2 个指针，快的每次走 2 步，慢的每次走 1 步，当快慢指针相遇时，则有环
js
function hasCycle(head) {
if(!head || !head.next ) return false;
let slow = head;
let fast = head.next;
while (fast !== slow) {
if(!fast || !fast.next) return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
};思路三：奇技淫巧法，利用 JSON.stringify() 不能字符串化含有循环引用的结构
js
function hasCycle(head) {
try {
JSON.stringify(head);
return false;
} catch (err) {
return true;
}
}两个有序链表的合并：
思路一：遍历
js
function mergeTwoLists(l1, l2) {
if(l1 === null) return l2;
if(l2 === null) return l1;
let head = new ListNode(-1);
let node = head;
while (l1 && l2) {
if (l1.val <= l2.val) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
node.next = l1 ? l1 : l2;
return head.next;
};思路二：递归
js
function mergeTwoLists(l1, l2) {
if(l1 === null) return l2;
if(l2 === null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}删除链表的第 n 个节点：
思路：定义 2 个指针 a, b，新建一个空队头，b 先走 n 步，然后 a, b 再一起走，此时 a, b 的间隔是 n，当 b 到达队尾时，a 刚好在n的前一个节点(因为开始时多建了一个节点)，然后让 a.next 等于 a.next.next 即可。
js
function removeNthFromEnd(head, n) {
if(n === 0) return head;
let p = new ListNode(-1);
p.next = head;
let a = p;
let b = p;
while (n > 0) {
b = b.next;
n--;
}
while (b.next !== null) {
a = a.next;
b = b.next;
}
a.next = a.next.next;
return p.next;
};求链表的中间节点：
思路：2 个指针，一个每次走一步，一个每次走 2 步即可，当走 2 步的指针到达链表尾部时，走一步的指针刚好到链表中间
js
function middleNode(head) {
let a = head;
let b = head;
while (b != null && b.next != null) {
a = a.next;
b = b.next.next;
}
return a;
};取 1000 个数字里面的质数
质数/素数：是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数
正则表达式：
js
function getPrime(num) {
if (num <= 1) {
return false;
}
for (let i = 1; i < num; i++) {
let temp = new Array(i).fill(1).join('');
if (!/^1?$|^(11+?)\1+$/.test(temp)) {
console.log(i);
}
}
}找出已排序数组中和为给定值的两个元素，如：[1, 2, 3, 4, 5] 中找出和为 6 的两个元素。
双指针法：
js
function twoSum(arr, sum) {
let i = 0;
let j = arr.length - 1;
let result = [];
while (i < j) {
if (arr[i] + arr[j] > sum) {
j--;
} else if (arr[i] + arr[j] < sum) {
i++;
} else {
result.push([arr[i], arr[j]]);
i++;
j--;
}
}
return result;
}
// test
twoSum([1,2,3,4,5,6,7,8,9,10], 8);时间复杂度 O(n)。
线性顺序存储结构和链式存储结构有什么区别？以及优缺点
大数相加
Js 和任何一门语言一样，对其数值的范围有限制。
js
Number.MAX_VALUE; // 1.7976931348623157e+308
Number.MAX_SAFE_INTEGER; // 9007199254740991
Number.MIN_VALUE; // 5e-324
Number.MIN_SAFE_INTEGER; // -9007199254740991如果我们想要对一个超大的整数（> Number.MAX_SAFE_INTEGER）进行加法运算，但是又想输出一般形式，那么使用 + 是无法达到的，一旦数字超过 Number.MAX_SAFE_INTEGER 数字会被立即转换为科学计数法，并且数字精度相比以前将会有误差。在此时就需要自己实现一套加法算法。
js
function sumBigNumber(a, b) {
let res = '';
let temp = 0;
a = a.split('');
b = b.split('');
while (a.length || b.length || temp) {
temp += ~~a.pop() + ~~b.pop();
res = (temp % 10) + res;
temp = temp > 9;
}
return res.replace(/^0+/, '');
}
// 100000000000113333
sumBigNumber('100000000000002222', '111111');
// 23784678091374191619192327186252683753
sumBigNumber('3782647863278468012934670', '23784678091370408971329048718239749083');说明：
- 首先我们用字符串的形式来保存大数，就保证了其在数学表示上不会发生变化
- 初始化
res,temp变量来保存中间计算的结果，在将两个字符串split为数组，以便我们进行每一位的运算 - 循环的第一次就是进行「个位」的运算，将二者最末尾的两个数相加，由于每一位数字是
0 - 9，所以需要进行进位，在进过取余数操作后，将结果保留在个位 - 判断
temp是否大于10，若是则将temp赋值为true，等等，为什么要赋值成布尔值，不要着急，魔法即将发生 - 在两个大数中的一个还有数字没有参与运算，或者前一次运算发生进位后，进行下一次循环
- 接着除了对新的两个数字相加还要加上
temp，若上次发生了进位，则此时temp为true，JS 因为存在隐式转换，所以true转换为1，我们借用 JS 的类型转换，完成了逻辑上的逢10进1操作 - 接下来就是重复上述的操作，直到计算结束
js中 ~~ 和 | 的妙用：
~~ 它代表双非按位取反运算符，如果你想使用比 Math.floor() 更快的方法，那就是它了。需要注意，对于正数，它向下取整；对于负数，向上取整；非数字取值为0，它具体的表现形式为：
js
~~null; // => 0
~~undefined; // => 0
~~Infinity; // => 0
~~NaN; // => 0
~~0; // => 0
~~{}; // => 0
~~[]; // => 0
~~(1/0); // => 0
~~false; // => 0
~~true; // => 1
~~1.9; // => 1
~~-1.9; // => -1| 的用法，通常用来取整：
js
1.2|0 // 1
1.8|0 // 1
-1.2|0 // -1求 1+2+3+...+n
要求不能使用乘除法, for, while, if, else, switch, case 等关键字及条件判断语句（A ? B : C）。
**解法一：**递归
js
function sumAdd(n) {
if (n <= 1) return n;
return sumAdd(n - 1) + n;
}解法二：reduce
js
function sumAdd(n) {
let arr = new Array(n).fill(0);
let result = arr.reduce((acc, val, idx) => acc + idx, n);
return result;
}求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）
js
function count(num) {
let result = 0;
let reg = /1/g;
for (let i = 0; i <= num; i++) {
let temp = `${i}`.match(reg) || [];
result += temp.length;
}
return result;
}接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
js
// 暴力解法
function trap(height = []) {
if (height.length === 0) return 0;
const nums = height.length;
let result = 0;
for (let i = 1; i < nums - 1; i++) {
let l_max = 0;
let r_max = 0;
// 找右边最高的柱子
for (let j = i; j < nums; j++) {
r_max = Math.max(r_max, height[j]);
}
// 找左边最高的柱子
for (let j = i; j >= 0; j--) {
l_max = Math.max(l_max, height[j]);
}
result += Math.min(l_max, r_max) - height[i];
}
return result;
}
// 暴力解优化，时间复杂度 O(n)
function trap(height = []) {
if (height.length === 0) return 0;
const nums = height.length;
let result = 0;
let l_max = new Array(nums);
let r_max = new Array(nums);
l_max[0] = height[0];
r_max[nums-1] = height[nums-1];
for (let i = 1; i < nums; i++) {
l_max[i] = Math.max(height[i], l_max[i - 1]);
}
for (let i = nums - 2; i >= 0; i--) {
r_max[i] = Math.max(height[i], r_max[i + 1]);
}
for (let i = 1; i < nums - 1; i++) {
result += Math.min(l_max[i], r_max[i]) - height[i];
}
return result;
}
// 进一步优化，双指针法
function trap(height = []) {
if (height.length === 0) return 0;
const nums = height.length;
let result = 0;
let left = 0;
let right = nums - 1;
let l_max = height[0];
let r_max = height[nums - 1];
while (left <= right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
if (l_max <= r_max) {
result += l_max - height[left];
left++;
} else {
result += r_max - height[right];
right--;
}
}
return result;
}