js刷题，重点是思路。

分类汇总，收集知识点。👨‍🚀

学习链接

CP Wiki

CodeTop
题目会变动。。

visualgo
可视化数据结构！

基础算法

这里的题选的都很好啊！
来自CP Wiki

枚举

枚举就是指尝试所有可能的情况。
枚举的顺序可能影响程序的运行效率。
用二进制数表示状态的方法被称为状态压缩。

枚举子集

for (int i = 1; i < (1 << n); ++i) {
    for (int j = i; j; j = (j - 1) & i) {
        // ...
    }
}

折半搜索（Meet in the middle），是一种对暴力枚举的优化策略。

练习题

LC46 - 全排列(opens new window)

枚举不含重复元素数组的全排列。

const res = [], path = [];
backtracking([]);
return res;

function backtracking(used) { // 使用used进行标记。
    if(path.length === nums.length) {
        res.push(Array.from(path));
        return;
    }

    for(let i = 0; i < nums.length; i++) {
        if(used[i]) continue; //判断

        path.push(nums[i]);
        used[i] = true;

        backtracking(used);

        path.pop(); // 回溯
        used[i] = false;
    }
}

LC47 - 全排列 II(opens new window)

枚举含有重复元素数组的全排列。

含有重复的重点，就是要去重，去重先要排序！！

let res = [], path = [];
nums.sort((a, b) => a - b) // 排序
backtracking([]);
return res;
	
function backtracking(used) {
    if(path.length === nums.length) {
        res.push(Array.from(path));
        return;
    }
    for(let i = 0; i < nums.length; i++) {
		// 去重，used[i - 1] === false，在树层上去重
        if(i > 0 && nums[i] === nums[i - 1] && used[i - 1] === false) continue;
			
        if(!used[i]) {
            path.push(nums[i]);
            used[i] = true;
					
            backtracking(used);
					
            path.pop();
            used[i] = false;
        }
    }
}

LC1494 - 并行课程 II(opens new window)

枚举子集。

LC805 - 数组的均值分割(opens new window)

折半搜索。

排序

493. 翻转对

归并排序

1665. 完成所有任务的最少初始能量

按照剩余能量（要求减去实际消耗）降序排列，剩余能量多的先处理，剩余能量少的后处理。

还要再理解理解。。

tasks.sort((pre, next) => {
       return (next[1] - next[0]) - (pre[1] - pre[0])
   })
   let result = 0, restNums = 0
   for (let i = 0; i < tasks.length; i++) {
       result += ((tasks[i][1] - restNums > 0) ? (tasks[i][1] - restNums) : 0)
       tasks[i][1] - restNums > 0 && (restNums = tasks[i][1])
			
       restNums -= tasks[i][0]
   }
   return result

二分查找

重点：有序，找中点，缩小范围。
二分查找的复杂度是O(logN)。

1482. 制作 m 束花所需的最少天数

有点懂。

var minDays = function(bloomDay, m, k) {

    if(m > bloomDay.length / k) { // 同 m * k > bloomDay.length
        return -1;
    }
    let low = Math.min.apply(null, bloomDay), high = Math.max.apply(null, bloomDay);
    // console.log(low, high)
    while(low < high) {
        const days = Math.floor((high - low) / 2) + low;

        if(canMake(bloomDay, days, m, k)) {
            high = days;
        } else {
            low = days + 1; // 边界。
        }
        console.log(low, high,'000', days);
    }
    return low;
};

const canMake = (bloomDay, days, m, k) => {
    let bouquets = 0;
    let flowers = 0;
    const length = bloomDay.length;

    for(let i = 0; i < length && bouquets < m; i++) {
        if(bloomDay[i] <= days) {
            flowers++;
            if(flowers === k) {
                bouquets++; // 二分
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m; // 二分成立
}

三分查找

二分查找要求数组或范围满足一定意义上的有序性，三分查找则是针对数组或范围满足单峰或单谷的特性，即可能是先递增后递减，或先递减后递增。

针对高维空间，可以在固定前kk维的情况下对第k+1k+1维进行三分查找，这样一层层进行下去，也就是所谓的三分套三分。

1515. 服务中心的最佳位置

数据结构

栈

栈（Stack）是一种具有后进先出特性的线性数据结构。

单调栈（Monotonic Stack）在数据结构层面就是最普通的栈，但我们需要在新元素入栈时维护一个栈的单调性，使栈中的元素始终保持升序或降序。
在一类与区间有关的问题中，单调栈可以实现O(N)O(N)的复杂度，因为每个元素至多入栈和出栈一次。

42. 接雨水

动态规划解法

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，
下标 i 处能接的雨水量等于下标 i 处的水能到达的**最大高度减去 height[i]**。

单调栈解法

84. 柱状图中最大的矩形

队列

862. 和至少为 K 的最短子数组

子数组是数组中连续的一部分。

前缀和 + 单调队列

进阶数据结构

了解了解。。

平衡二叉搜索树

二叉搜索树是一类特殊的带权（点权）二叉树

它的特点是，每个节点的权值总是大于其左子树中任何节点的权值，同时小于其右子树中任何节点的权值。

在二叉搜索树中进行查找、插入、删除等操作的时间复杂度为O(h)，其中hh为树高。

如果它的所有节点都只有左孩子，此时二叉搜索树退化为一条链表，查找、插入、删除等操作的时间复杂度为O(n)

并查集

线段树

线段树（Segment Tree）是一种树型数据结构

树中的每个节点代表一段[L,R]的区间
一个节点的左孩子和右孩子的区间不相交且其并恰好等于该节点对应的区间。
树的叶子节点对应的区间为[L,L]，也即单点。

线段树常用于含修改的区间查询。

动态规划专题

靠数量取胜吧。。

动态规划中每一个状态一定是由上一个状态推导出来的

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

基础

509. 斐波那契数

if(n <= 1) return n;
let dp = [];
dp[0] = 0;
dp[1] = 1;

for(let i = 2; i <= n; i++) {
    let sum = dp[0] + dp[1];
    dp[0] = dp[1];
    dp[1] = sum;
}
return dp[1];

70. 爬楼梯

当前位置，由前两个位置得出。

if(n <= 1) return n;
let dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 1;
for(let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]

746. 使用最小花费爬楼梯

找前两个的累加的最小值

let n = cost.length;
let pre = 0, cur = 0;
for(let i = 2; i <= n; i++) {
    let next = Math.min(pre + cost[i - 2], cur + cost[i - 1]);
    pre = cur;
    cur = next;
}
return cur;

62.不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

二维dp，初始值，一行一列 1
从【1，1】开始，当前位置等于上一个，和前一个之和。

let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
for(let i = 0; i < m; i++) {
    dp[i][0] = 1;
}
for(let i = 0; i < n; i++) {
    dp[0][i] = 1;
}
for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
}
return dp[m - 1][n - 1];

63. 不同路径 II

网格中的障碍物和空位置分别用 1 和 0 来表示。

二维dp，同上，
需要处理的是1的部分。初始化的时候，有1，后面的路径就不设置了
累加部分，有1，当前位置就设置为 0 。

let dp = new Array(obstacleGrid.length).fill(0).map(() => new Array(obstacleGrid[0].length).fill(0));

 for(let i = 0; i < obstacleGrid.length; i++) {
     if(obstacleGrid[i][0] !== 1) {
         dp[i][0] = 1;
     } else {
         break;
     }
 }
 for(let i = 0; i < obstacleGrid[0].length; i++) {
     if(obstacleGrid[0][i] !== 1) {
         dp[0][i] = 1;
     } else {
         break;
     }
 }

 for(let i = 1; i < obstacleGrid.length; i++) {
     for(let j = 1; j < obstacleGrid[0].length; j++) {
         dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][ j - 1];
     }
 }

 return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。
返回你可以获得的最大乘积。

2 <= n <= 58

j * (i - j) 是单纯的把整数拆分为两个数相乘，
而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

let dp = new Array(n + 1).fill(0); // n + 1
dp[2] = 1;

for(let i = 2; i <= n; i++) { // <= n
    for(let j = 1; j < i; j++) {
        dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j);
    }
}
return dp[n];

96.不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

背包

打家劫舍

股票问题

子序列问题

状态压缩动态规划

状态压缩动态规划的一个明显标志是题目中某一参数的上限为一个很小的常数（通常不超过20）。
同时，题目中存在某种非此即彼的状态，比如工作是否完成，灯是否点亮，等式是否满足，数值的奇偶，等等。

Leetcode刷题