分类刷算法题（三）数组操作 | 前端er
站长
· 阅读数 2
有人夜里相爱，有人夜里开车看海，有人因为测试用例没过睡不着觉
- 分类刷算法题
- 今天要刷的是 - 数组题目
- 很多基本操作在前面的链表，栈和队列都用过啦，就不赘述
- 开刷！
一、原地修改数组
- 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
};
做不够瘾的可以继续继续做以下题哩(反正我都做了哈哈哈)
三、滑动窗口
最基本思路；
- 使用双指针，初始化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收缩的条件，以及结果的计算；