【算法】分治思想、动态规划、回溯、贪心算法开发者社区

【算法】分治思想、动态规划、回溯、贪心算法

分解：将原问题分解成一系列子问题。
解决：递归求解各个子问题，若子问题足够小，则直接求解。
合并：将子问题的结果合并成原问题。

const mergeSort = function(arr) {
    const len = arr.length;
    if (len > 1) {
        // 对半分解
        const middle = Math.floor(len / 2);
        const left = arr.slice(0, middle);
        const right = arr.slice(middle, len);
        let i = 0; 
        let j = 0;
        let k = 0;
        // 分别对左右进行排序
        mergeSort(left);
        mergeSort(right);
        while(i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k] = left[i];
            } else {
                arr[k] = right[j];
        // 检查余项
        while(i < left.length) {
            arr[k] = left[i];
        while(j < right.length) {
            arr[k] = right[j];
    return arr;

时间复杂度：O(nlogn)
空间复杂度：O(n)

重叠子问题
最优子结构
状态转移方程

爬上 n-1 阶楼梯的方法数量
爬上 n-2 阶楼梯的方法数量

    dp[0] = 1
    dp[1] = 1
const climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];

时间复杂度：O(n)
空间复杂度：O(n)

const climbStairs = function(n) {
    let a1 = 1;
    let a2 = 1;
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2];
    return a2;

时间复杂度：O(n)
空间复杂度：O(1)

最近某音很火的贪心土味情话
喂，不是吧。今天喝了脉动啊，吃了果冻啊，但是，还是忍不住对你心动啊。

给一个孩子的饼干应当尽量小并且能满足孩子，大的留来满足胃口大的孩子
因为胃口小的孩子最容易得到满足，所以优先满足胃口小的孩子需求
按照从小到大的顺序使用饼干尝试是否可满足某个孩子
当饼干 j >= 胃口 i 时，饼干满足胃口，更新满足的孩子数并移动指针  i++ j++ res++
当饼干 j < 胃口 i 时，饼干不能满足胃口，需要换大的 j++

时间复杂度：O(nlogn)
空间复杂度：O(1)

const findContentChildren = function (g, s) {
    g = g.sort((a, b) => a - b);
    s = s.sort((a, b) => a - b);
    let gi = 0; // 胃口值
    let sj = 0; // 饼干尺寸
    let res = 0;
    while (gi < g.length && sj < s.length) {
        if (s[sj] >= g[gi]) {
            gi++;
            sj++;
            res++;
        } else {
            sj++;
    return res;

遍历下一个数字所对应的所有映射的字母
将当前的字母添加到组合最后，也就是 str + tmp[r]

时间复杂度：O(3^N * 4^M)
空间复杂度：O(3^N * 4^M)

const letterCombinations = function (digits) {
    if (!digits) {
        return [];
    const len = digits.length;
    const map = new Map();
    map.set('2', 'abc');
    map.set('3', 'def');
    map.set('4', 'ghi');
    map.set('5', 'jkl');
    map.set('6', 'mno');
    map.set('7', 'pqrs');
    map.set('8', 'tuv');
    map.set('9', 'wxyz');
    const result = [];
    function generate(i, str) {
        if (i == len) {
            result.push(str);
            return;
        const tmp = map.get(digits[i]);
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r]);

【算法】分治思想、动态规划、回溯、贪心算法

【算法】分治思想、动态规划、回溯、贪心算法

四种算法思想

分治算法 Divide and Conquer

动态规划 Dynamic Programming

贪心算法 Greedy

回溯算法 Backtracking