常见算法[亲测有效]

「时光不负，创作不停，本文正在参加2021年终总结征文大赛」

    一星期后，我们来到了决赛，前期我们打得都比较稳，没发生些正面团战，经济稍稍领先于对面，42分钟的时候由于我在自家野区脸探草丛被对面蹲了一波，直接葬送了比赛。晚上学校贴吧又炸锅了，纷纷议论我那波猩猩操作，毫无意识的菜鸡……虽然我知道是自己的失误导致比赛输了，但被人喷的滋味真不好受….
    十点多的时候收到她的一条消息：虽然比赛输了，但你打的挺好的，人都有失误的时候……瞬间让我心里充满了暖意。我们已经好几个月没联系了，她说不想因为上次告白的事情让我们变成陌生人，希望我们能继续当朋友……我赶忙屁颠屁颠的答应了，这是我一直想说却不敢说的,自从上次表白被拒后我一直躲避着她，我想她，但我无法直面她，总感觉有稍许尴尬（你们表白失败后看到她会是咋样的心情？）。我们的关系一下回到了我告白前的那样，当时给了我一种错觉，或许我还有机会。那天晚上我们聊了很多，比赛的失败和被人各种喷变得一点也不重要了。
    落了灰的小摩托被我擦的ber亮，曾一度想卖了却又不舍得，毕竟它载满了回忆，虽然不怎么美好。我没有像以前那样每天帮她带早餐了，一星期可能会帮她带一，两次的那种。我想这样相处起来会更加轻松、自然些。
    时间悄悄流逝，转眼到了大二，大二开始报些选修课了，我本想和她报同一个，怎奈她选的是芭蕾舞….后来我选了旅游，我很想出去看看祖国的大山大河，条件不允许哎， 第一次选修课时，我早早的来到了教室，坐在中间的位置，同学们和老师也都陆陆续续的来了，老师正准备上课时，一位的衣着时尚的女生缓缓的走进教室，一下吸引了大家的目光，她身高1米6左右吧，长相属于那种甜美可爱型了。她目光扫了下教室，朝我这儿走来然后坐下了….

动态规划：感觉就是找一些规律

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

示例 1：

输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。

题解：

    var maxArr = function(nums) {
        let maxVal = nums[0];
        let sum = 0;
        for(let num of nums) {
            if(sum + num > num){
                sum = sum + num;
            } else {
                sum = num;
            }
            maxVal = Math.max(maxVal, sum);
        };
        return maxVal;
    };

以nums数组稍作分析：
第一次循环：sum初始为0 num=-2 sum=num=-2 maxVal=-2
第二次循环：sum初始为-2 num=1 sum=num=1 maxVal=1
第三次循环：sum初始为1 num=-3 sum=sum+num=-2 maxVal=1
第四次循环：sum初始为-2 num=4 sum=num=4 maxVal=4
前面的数做相加的时候得到的结果小于0，那么往下加的时候可以直接忽略他们的和，以当前数作为一个新的起点开始往下加，每次相加maxVal都会比较最大的sum值的和。

不得不说动态规划真的比较难，上面例子在力扣属于简单的…..

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择

盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

题解：

var maxArea = function(height) {
    let i = 0, j = height.length-1;
    let square, max = 0;
    while(j-i >= 1){
        if(height[i]>height[j]){
            square = height[j] * (j-i);
            j--;
        }else{
            square = height[i] * (j-i);
            i++;
        }
        max = Math.max(square,max);
    }
    return max;
};

使用贪心+双指针
分析：

1. 我们在数组中使用两个指针，一个放在开始，一个置于末尾。
2. 在每一步中，我们将指向较短线段的指针向较长的线段那端移动；
3. 同时，我们记录下所有步骤里最大的面积: maxSquare。
4. 以 m , n 表示前后指针，H[m] 表示位置 m 处的高度，n 是输入的数据长度。S(m,n) = min(H[m],H[n]) * (n-m) 是 (m,n) 对的面积。h[m,n] 表示当前位置的树高, h = n-m

分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。

归并排序为例

题解：

  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];
                    i++;
                } else {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }
            // 检查余项
            while(i < left.length) {
                arr[k] = left[i];
                i++;
                k++;
            }
            while(j < right.length) {
                arr[k] = right[j];
                j++;
                k++;
            }
        }
        return arr;
    }

回溯：当发现已不满足求解条件时，就“回溯”返回，尝试别的路径

[电话号码的字母组合]

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入： digits = "23"
输出： ["ad","ae","af","bd","be","bf","cd","ce","cf"]

题解：

   const letterCombinations = (digits) => {
        if (digits.length == 0) return [];
        const res = [];
        const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
        // dfs: 当前构建的字符串为curStr，现在“翻译”到第i个数字，基于此继续“翻译”
        const dfs = (curStr, i) => {   // curStr是当前字符串，i是扫描的指针
          if (i > digits.length - 1) { // 指针越界，递归的出口
            res.push(curStr);          // 将解推入res
            return;                    // 结束当前递归分支
          }
          const letters = map[digits[i]]; // 当前数字对应的字母
          for (const letter of letters) { // 一个字母是一个选择，对应一个递归分支
            dfs(curStr + letter, i + 1);  // 选择翻译成letter，生成新字符串，i指针右移继续翻译（递归）
          }
        };
        dfs('', 0); // 递归的入口，初始字符串为''，从下标0开始翻译
        return res;
      };

分析：
回溯本质是暴力搜索,用DFS（深度优先搜索）的方式。

思索

[3,5,1,9,2,0,8,4,7,6] 0-9 10个数进行排序，时间复杂度最低为多少？

算法听起来高大上，它也确实比较难，初级入门要求其实也还好。

最近工作有点忙，码字不易，麻烦点赞支持下！也非常感谢那些一直支持我的掘友们

故事传送门：juejin.cn/post/702429…