前端常用入门算法

一：双指针

1、同向快慢指针

适合原地调换一个数组的元素们的位置，使用for循环，声明两个下标，同向移动，一个移的快，一个移的慢。

快的指针用来往前走，慢的用来停在目标数据上。典型的案例：283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

var moveZeroes = function(nums) {    let slowIndex = 0;    for (let fastIndex = 0; fastIndex   
2、相反方向的指针
 
同一个数据，开发一个指针，结尾一个指针。一个往左一个往右，向中间靠拢。适合解决回文串类问题。实例：125. 验证回文串
 
var isPalindrome = function(s) {    let newS = s.toLowerCase();    newS = newS.replace(/[^a-z0-9]/g,"");    // 核心思想开始    let left = 0,right = newS.length-1;    while(left  
3、一个数据对应一个指针
 
双指针适用于获取两个数组中的相同元素，使用while语句。
 
首先需要把两个数组排序，比较两个指针的值。如果相同将值推进结果数据，并将两个指针都挪动一位；如果不同，将值小的指针挪动一位；
 
将值小的数组指针挪动一位，是因为两个数组都是从小到大的排序的。值小的数组往前走，才有可能和值大的数组的项趋近或相同。
 
一直到某个数组遍历结束即可，典型实例1：349. 两个数组的交集
 
题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]解释：[4,9] 也是可通过的var intersection = function(nums1, nums2) {   // 先滤重    nums1.sort((a, b) => a - b);    nums2.sort((a, b) => a - b);    const result = new Set();    let first = 0, second = 0;    while (first  nums2[second]){            second++;        }else{            first++;        }    }    return [...result];};
 
案例2: 392. 判断子序列 
 
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。示例 1：输入：s = "abc", t = "ahbgdc"输出：true示例 2：输入：s = "axc", t = "ahbgdc"输出：false// 整体思路是把父串整个匹配一遍。刚开始两个指针都从0开始，当两个字符相同时，指针都加一。如果不同父串加一，如果子串被全部包含，那么最终子串的下标要等于子串长度才行var isSubsequence = function(s, t) {    let sIndex = 0;    let tIndex = 0;    let sLength = s.length;    let tLength = t.length;    while(tIndex  
 
二：快慢指针跟双指针的区别与相同点？
 
1、区别
 

• 使用场景不同。快慢指针使用于一个数组，双指针适用于两个数组。
• 适用的遍历方法不同。快慢指针适合for循环，双指针适合while循环。

  2、相同点

  • 都属于对数组的操作算法
  • 都是操作两个下标 

    三：双向映射

    我们常用哈希表实现映射关系，有时双向映射技巧解决问题效率很高。

    双向映射常使用两个Map，分别存放两组数据相反的映射关系。然后便利数据，查看相反两个映射关系是否都符合。

    比如力扣：290. 单词规律

    给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。示例1:输入: pattern = "abba", s = "dog cat cat dog"输出: true示例 2:输入:pattern = "abba", s = "dog cat cat fish"输出: false示例 3:输入: pattern = "aaaa", s = "dog cat cat dog"输出: false

    var wordPattern = function(pattern, s) {     sArr = s.split(" ");    let p2s = new Map(); // pattern对s的映射    let s2p = new Map(); // s对pattern的映射    if(pattern.length !== sArr.length){        return false;    }    for (let i = 0; i  
    四：回溯算法
     
    例如，在一个集合S中，找到所有和为target的子集的问题，我们可以通过回溯算法来求解。我们可以定义一个空集合subset来存储每一个满足条件的子集，并从集合的第一个元素开始遍历。在遍历的过程中，我们递归地从当前位置开始寻找满足条件的子集，如果找到了一个满足条件的子集，就加入到subset集合中，并回溯到上一个状态，继续查找满足条件的解，如果遍历整个集合，仍然没有找到满足条件的子集，则不断回溯，直到找到满足的子集或者遍历整个集合。这样就可以找到所有满足的子集了。
     
    五：算法技巧
     
    1、判断数组中连续3个值满足条件？
     
    我想到的是用一个数组装满足条件的值的下标，当数组长度大于2时，判断当前值是不是等于上一个值加一，上上那个值加2。
     
    还是力扣官解厉害，他们用一个变量0计算。每次符合条件就加一，但是下一个循环不符合条件就赋0.当变量等于3时，就是有连续的3个值满足条件。实例如下
     
    551. 学生出勤记录 I
     
    var checkRecord = function(s) {    let absents = 0, lates = 0;    const n = s.length;    for (let i = 0; i = 2) {                return false;            }        }        // 奇迹从这里开始        if (c === 'L') {            lates++;            if (lates >= 3) {                return false;            }        } else {            lates = 0;        }    }    return true;};
     
    2、层级关系用栈
     
    当涉及多层时，需要层层深入，从最里层开始算。这时可以使用数组，一层一层的push，然后从数组最后一个执行，一个个pop。模拟往外一层一层处理。
     
    394. 字符串解码​​​​​​
     
    3、获取某个字母的下标？
     
    比如a是24个字母的第一个，下标0。b的下标是1，c的下标是2。如果动态获取呢？
     
    "c".charCodeAt() - "a".charCodeAt();
     
    即通过某个字母的编码减去a的编码，差值就是该字母在24位字母中的下标。 
     
    六：矩阵类题目
     
    1、生成指定矩阵
     
    生成指定n行、m列的矩阵。需要两层循环，第一层生成n个数组，第二层给生成的数组插入m个值即可。
     
    PS：实践
     
    理论需要配合实践才能真正掌握，
     
    哥们全栈写了一套个人博客 ，代码开源，欢迎大家来玩