前端常用入门算法

时间：2024-04-28 11:15:26 来源：网络cs 作者：胡椒栏目：跨境学堂阅读：

标签：入门

阅读本书更多章节>>>>

一：双指针

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 < nums.length; fastIndex++) {        if (nums[fastIndex] !== 0) {            [nums[slowIndex], nums[fastIndex]] = [nums[fastIndex], nums[slowIndex]];            slowIndex++; // 如果遇到0，慢指针不再往前走        }    }};

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 < right){        if(newS[left] !== newS[right]){            return false;        }        left++;        right--;    }    return true;};

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 < nums1.length && second < nums2.length) {        if(nums1[first] === nums2[second]){            result.add(nums1[first]);            first++;            second++;        }else if(nums1[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 < tLength && sIndex < sLength){        if(s.charAt(sIndex) === t.charAt(tIndex)){            sIndex++;        }        tIndex++;    }    if(sIndex == sLength){        return true;    }else{        return false;    }};

二：快慢指针跟双指针的区别与相同点？

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 < pattern.length; i++) {        let p = p2s.has(pattern[i]) && p2s.get(pattern[i]) !== sArr[i];        let s = s2p.has(sArr[i]) && s2p.get(sArr[i]) !== pattern[i];        if(p || s){            return false;        }                p2s.set(pattern[i],sArr[i]); // 分别存放相反的映射关系        s2p.set(sArr[i],pattern[i]); // 分别存放相反的映射关系    }    return true;    };

四：回溯算法

例如，在一个集合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 < n; i++) {        const c = s[i];        if (c === 'A') {            absents++;            if (absents >= 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：实践

理论需要配合实践才能真正掌握，

哥们全栈写了一套个人博客，代码开源，欢迎大家来玩