分类刷算法题（三）数组操作 | 前端er

有人夜里相爱，有人夜里开车看海，有人由于测试用例没过睡不着觉

• 分类刷算法题
• 今日要刷的是 – 数组题目
• 许多根本操作在前面的链表，栈和行列都用过啦，就不赘述
• 开刷！

一、原地修正数组

• 26. 删除有序数组中的重复项 – 力扣（LeetCode）
• 难度：简略
• 嘿嘿看到这道题，就知道双指针法中的快慢指针又要重出江湖啦
• 这道题只需求快指针走在前面，只需快慢指针指向的数组值不相同，那么就将快指针指向的值赋值给慢指针指向的值即可！
• 最终回来的数组长度，即慢指针+1

var removeDuplicates = function(nums) {
    if(nums.length == 0) return 0;
    let fast = 0;
    let slow = 0;
    while(fast<nums.length) {
        if(nums[slow] != nums[fast]) {
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    return slow+1
};

• 27. 移除元素 – 力扣（LeetCode）
• 难度：简略
• 再来一道类似的题，思路跟上面的根本是相同的，动手试试叭
• 思路：仍旧是快指针走在前面，只需指向的值不等于val，则将其指向的值赋值给慢指针指向的值即可，最终回来慢指针表明数组长度

var removeElement = function(nums, val) {
    let slow = 0;
    let fast = 0;
    while(fast < nums.length) {
        if(nums[fast] != val) {  
            nums[slow] = nums[fast];
             slow++;
        }
        fast++;
    }
    return slow
}

• 283. 移动零 – 力扣（LeetCode）
• 难度：简略
• 有没有发现这道题跟上一道根本相同，不相同的便是后边需求赋值为0，那么咱们就让慢指针顺次跑到快指针的位置，途中顺次赋值为0即可

var moveZeroes = function(nums) {
  let slow = 0;
    let fast = 0;
    while(fast < nums.length) {
        if(nums[fast] != 0) {  
            nums[slow] = nums[fast];
             slow++;
        }
        fast++;
    }
    while(slow < fast) {
        nums[slow] = 0;
        slow++
    }
};

二、前缀和

前缀和首要适用的场景是原始数组不会被修正的情况下，频繁查询某个区间的累加和。

• 303. 区域和检索 – 数组不可变 – 力扣（LeetCode）
• 难度：简略
• 这道题当然一开端能够想到的便是运用双指针法，然后调用sumRange时去遍历相加，其时这种做法很不高雅，在屡次调用sumRange的情况下会重复很多的操作；咱们的意图当然是希望能将sumRange的时间复杂度降为O(1)，换句话说便是不要遍历，那么就需求空间来换时间了
• 所以考虑运用咱们的前缀和办法： 初始化一个数组，第n个寄存nums前n个值之后
• 那么假如我想求索引区间[1, 4]内的一切元素之和，就能够经过preSum[5] - preSum[1]得出

var NumArray = function(nums) {
    //初始化一个比nums长度还大1的数组--由于咱们preSum[0]需求赋值为0,方便累加
    this.preSum = new Array(nums.length+1).fill(0);
    for(let i = 0;i<nums.length;i++) {
        this.preSum[i+1] = this.preSum[i] + nums[i];
    }
};
NumArray.prototype.sumRange = function(left, right) {
    return this.preSum[right+1] - this.preSum[left]
};

• 643. 子数组最大平均数 I – 力扣（LeetCode）
• 难度：简略
• 这道题能够用之前咱们提过的滑动窗口办法来做，也能够用前缀和来做
• 先算出前缀和数组，然后再进行遍历一次，求以k为单位的最大值，最终return出该值除以k即可

var findMaxAverage = function(nums, k) {
    //初始化前缀和数组
    let preSum = new Array(nums.length+1).fill(0);
    //算出前缀和数组
    for(let i =0 ;i<nums.length;i++) {
        preSum[i+1] = nums[i] + preSum[i];
    }
    let max = -Infinity;
    //以k为单位求最大值
    for(let i = k-1; i< nums.length; i++ ) {
        max = Math.max(preSum[i+1] - preSum[i+1-k] , max)
    }
    //回来平均值
    return max/k
};

• 238. 除本身以外数组的乘积 – 力扣（LeetCode）
• 难度：中等
• 这道题仍旧能够用前缀和思路，可是是两次类似前缀和
• 思路：
  • 先算出左面顺次相乘数组
  • 再算出从右边开端顺次相乘数组
  • 最终算出除本身以外数组

var productExceptSelf = function(nums) {
    let preSumLeft = new Array(nums.length+1).fill(1);
    let preSumRight = new Array(nums.length+1).fill(1);
    let res = [];
    //算出从左面开端相乘的前缀积
    for(let i = 0 ;i<nums.length;i++) {
        preSumLeft[i+1] = preSumLeft[i] * nums[i];
    }
    //算出从右边开端的，而且算出成果
    for(let i = nums.length-1;i>=0;i--) {
         preSumRight[i] = preSumRight[i+1] * nums[i]; 
         res[i] = preSumRight[i+1] * preSumLeft[i];
    }
    return res
};

做不够瘾的能够持续持续做以下题哩(反正我都做了哈哈哈)

1480. 一维数组的动态和 – 力扣（LeetCode）

304. 二维区域和检索 – 矩阵不可变 – 力扣（LeetCode）

523. 接连的子数组和 – 力扣（LeetCode）

三、滑动窗口

最根本思路；

• 运用双指针，初始化left=0，right=0， 把[left,right]称为一个区间，也是咱们所说的窗口
• 不断添加right扩展窗口，直到窗口中的元素符合要求
• 中止添加right，转而不断添加left然后缩小窗口，直到不再符合要求

• 76. 最小覆盖子串 – 力扣（LeetCode）
• 难度；困难
• 不要被这个难度吓到哦，理解清楚滑动窗口是怎么样的解题思路就很清晰啦(耐心看下去！！！）
• 思路:
  • 运用双指针，初始化left=0，right=0
  • 初始化map结构，用来核算存储t中需求的字符串以及分别需求的个数
  • 初始化needLength为map长度，这个是用来判别窗口内的数据是否符合要求
  • 进入while循环，由于这儿是为了寻找最小覆盖子串，因而right应该走到最终
  • 不断添加right扩展窗口，直到窗口中的元素符合要求
  • 中止添加right，转而不断添加left然后缩小窗口，直到不再符合要求
  • （以上两步具体看代码注释）
  • 记载下每次比较添加left更新所得的最小覆盖子串

var minWindow = function(s, t) {
    //初始化left=0，right=0
    let left = 0;
    let right = 0;
    let res = '';
     //初始化map结构，用来核算存储t中需求的字符串以及分别需求的个数
    const need = new Map();
    for(let item of t) {
        //假如现已记载该字符，则数据加1 ，不然记载并赋值为1
        need.set(item, need.has(item)? need.get(item) + 1 : 1 );
    }
    let needLength = need.size;
    while(right < s.length) {
      //这儿执行的意图其实便是上述滑动窗口的第五步：不断添加right扩展窗口，直到窗口中的元素符合要求
     //用c1记载当前right指向的值
     const c1 = s[right];
     //判别map结构是否有该字符(其实便是判别t是否需求该字符)
     if(need.has(c1)) {
         //该字符进入窗口，由于map结构该字符所需次数-1
         need.set(c1, need.get(c1)-1);
          //当该字符所需求的次数为0时，t所需求的字符类型个数-1
         if(need.get(c1) == 0) needLength -= 1
    }
        //这儿t所需的字符现已悉数在窗口里面了，现在要做的是去缩短窗口
        while(needLength == 0) {
             //记载下每次更新得到的子串，由于subString是不包括endIndex位置的字符，所以这儿right要+1
            const newRes = s.substring(left,right+1);
            //假如该子串比现已存储的子串长度还小或许成果子串为空，即更新成果子串
            if(!res || newRes.length <= res.length) res = newRes;
            //这儿开端缩短窗口-让left向右走
            const c2 = s[left];
            //假如map结构有该字符
            if(need.has(c2)) {
                //则将map结构该字符所需次数+1(应该咱们把该字符移出窗口了嘛)
                need.set(c2,need.get(c2)+1);
                //假如该字符只剩下一次，那么就阐明left向右一步就不符合要求了，所以这儿要将needLength+1,使其退出循环
                if(need.get(c2) === 1) needLength +=1;
            }
            left +=1;
        }   
     right+=1;
    }
    return res;
};

• 567. 字符串的排列 – 力扣（LeetCode）
• 难度： 中等
• 做完上面那道题再看这道是不是就觉得简略一点啦
• 根本都是上面的代码，那么有差异的便是，这道题要求的是接连的字符，也便是定长的，也便是说窗口的长度应该是固定的，那么咱们打断right添加的条件就变成了判别窗口长度是否大于所需长度
• 同时这道题要求的不是找到最小，而是找得到就回来true，不然回来false，那么咱们再遍历过程中，只需needLength===0时就应该即时回来true，防止做无用的遍历

var checkInclusion = function(s1, s2) {
    let left = 0 ,right = 0 ;
    const need = new Map();
    //先寄存每个字符所需求的次数
    for(let item of s1) {
        need.set(item , need.has(item)? need.get(item)+1: 1);
    }
    //需求的字符串个数
    let needLength = need.size;
    while(right < s2.length) {
        const c1 = s2[right];
        if(need.has(c1)) {
            need.set(c1, need.get(c1)-1);
            //进入窗口就所需个数-1
            if(need.get(c1) == 0)  needLength--;
        }
        //由于这儿需求的字符时接连的，所以窗口应该是定长的
        if(right -left >= s1.length) {
             const c2 = s2[left];
             if(need.has(c2)) {
                 need.set(c2, need.get(c2)+1);
                 if(need.get(c2) == 1) needLength +=1;
             }
             left++;
        }
        right++;
        if(needLength == 0) return true;
    }
    return false
};

• 3. 无重复字符的最长子串 – 力扣（LeetCode）
• 难度：中等
• 我记住如同今年字节前端青训营的笔试最终一道便是这个题，所以仍是很值得一做的
• 打开一看，我现已做过这道题了，尽管做过了，可是现在回看仍是觉得不够高雅，凭借辅助栈仍旧用了三次遍历

var lengthOfLongestSubstring = function(s) {
    let ss = new Array();
    let maxArr = [];
    //采用滑动窗口
    for(let i=0;i<s.length;i++){
        let result = is(ss,s[i]);
        //这是不存在
        if(result == -1){
            ss.push(s[i]);
        }else{
            //这是存在
            ss.splice(0,Number(result)+1); 
            ss.push(s[i]);
        }
    maxArr.push(ss.length);
    }
    let max = 0;
   for(let i of maxArr){
       if(i>=max){
           max = i
       }
   }
   return max
};
var is = function(arr,o){
    let result = -1;
    for(let i in arr){
        if(arr[i] == o){
            result = i;
        } 
    }
    return result
}

• 仍是依照咱们上面双指针+滑动窗口的套路来啦
• 那这道题呢，不需求咱们去找到满足他给定的字符串，而是让咱们找出不重复的就好
• 所以咱们这儿能够用map结构也能够直接用数组也挺方便
• 只需当map结构寄存的字符串次数大于1时，就改动left缩短窗口，直到该字符串的次数能够小于等于1才让right持续右移，当然在这个过程也需求不断地去比对得出res

var lengthOfLongestSubstring = function(s) {
    let left = 0 , right = 0;
    let res = 0;
    let need = new Map();
    while(right < s.length) {
        const c1 = s[right];
        need.set(c1,need.get(c1)? need.get(c1)+1: 1);
        //寄存的字符串次数大于1时，就改动left缩短窗口
        while(need.get(c1) >1) {
            const c2 = s[left];
            need.set(c2, need.get(c2)-1);
            left++;
        }
        right ++;
        //比对得出res
        res = right - left > res ? right-left: res
    }
    return res
}

总结：尽管滑动窗口的题目都是中等或许困难等级的，可是只需找到了根本思路套路，再辨析清楚每一道题left缩短的条件，以及成果的核算；

关于其他算法题也能够看看我发过的

• 分类刷算法题（一）链表 | 前端er – ()
• 分类刷算法题（二）栈和行列 | 前端er – ()
• 分类刷算法题（四） 二分查找 | 前端er – ()
• 分类刷算法题 （五） 二叉树 | 前端er – ()