leetcode每天5题-Day23

1.移除元素

27. 移除元素-简单
重点：数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
b站视频讲解

①暴力

var removeElement = function(nums, val) {
    // 暴力 ： 双层for循环
    // 第一层for循环 遍历数组
    for(let i=0;i<nums.length;i++){
        if(nums[i]==val){
            // 第二层for循环 更新数组
            for(let j=i+1;j<nums.length;j++){
                nums[j-1]=nums[j];
            }
            i--;// 下标i以后的数值都向前移动了一位，所以i也向前移动一位 防止连续两位都是val
            nums.length--;
        }
    }
    return nums.length;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n^2)
空间复杂度：O(1)

②双指针
快指针：寻找val
慢指针：更新数组

var removeElement = function(nums, val) {
    let slow=0;
    for(let fast=0;fast<nums.length;fast++){
        // 更新数组的操作
        if(nums[fast]!=val){
            nums[slow++]=nums[fast];
        }
    }
    return slow;
};
1
2
3
4
5
6
7
8
9
10

时间复杂度：O(n)
空间复杂度：O(1)

2.删除排序数组中的重复项

26. 删除有序数组中的重复项-简单
这道题自己没做出来，看了题解才做出来...
①双指针

var removeDuplicates = function(nums) {
    // 因为nums.length>=1  所以数组中至少有一个元素 slow和fast从1开始
    let slow=1,fast=1;
    while(fast<nums.length){
        if(nums[fast]!==nums[fast-1]){
            nums[slow]=nums[fast];
            ++slow;
        }
        fast++;  
    }
    console.log(slow);
    return slow;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)，其中n是数组的长度。快指针和慢指针最多各移动n次。
空间复杂度：O(1)。只需要使用常数的额外空间。
②同样双指针

var removeDuplicates = function(nums) {
    let j=nums.length;
    if(j>1){
        // 慢指针j
        j=1;
        // 快指针i
        for(let i=1;i<nums.length;i++){
            if(nums[i]==nums[i-1]){
                continue;
            }else{
                nums[j]=nums[i];
                j++;
            }
        }
    }
    return j;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.移动零

283. 移动零-简单
①双指针
这道题也是自己没做出来，看了题解才做出来的...要注意不要重复fast++
错误示范👇

正解👇

var moveZeroes = function(nums) {
    if(nums.length==1) return nums;
    let slow=0,fast=0;
    while(fast<nums.length&&slow<nums.length){
        if(nums[fast]!==0){
	        let temp=nums[slow];
	        nums[slow]=nums[fast];
	        nums[fast]=temp;
	        
	        slow++;
        }
        fast++;
    }
    return slow;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

②同样双指针解法

var moveZeroes = function(nums) {
    let len=nums.length;
    for(let i=0,j=0;i<len&&j<len;){
        if(nums[j]!=0){
            nums[i]=nums[j];
            if(i!==j) nums[j]=0;
            i++;
        }
        j++;
    }
    // return i;
};
1
2
3
4
5
6
7
8
9
10
11
12

4.比较含退格的字符串

844. 比较含退格的字符串-简单
①双指针
两个指针，分别遍历s、t两个字符串，若当前字符串不为#，就把字符压入数组中，否则从数组中弹出一个字符，最后比较两个数组的结果是否相等。

var backspaceCompare = function(s, t) {
    const len1=s.length,len2=t.length;
    let i=0,j=0;
    const ans1=[],ans2=[];
    while(i<len1){
        if(s.charAt(i)!=='#'){
            ans1.push(s.charAt(i));
            i++;
        }else{
            ans1.pop();
            i++;
        }
        
    }
    while(j<len2){
        if(t.charAt(j)!=='#'){
            ans2.push(t.charAt(j));
            j++;
        }else{
            ans2.pop();
            j++;
        }
    }
    return ans1.toString()===ans2.toString();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

②同样双指针
逆序遍历两个字符串
根据官方题解的java版本写的，其实没看懂...

var backspaceCompare = function(s, t) {
    const len1=s.length,len2=t.length;
    let ans1=Array.from(s),ans2=Array.from(t);
    console.log(ans1,ans2);
    let skip_s=0,skip_t=0;
    for(let i=len1-1,j=len2-1;i>=0||j>=0;i--,j--){
        // 先找到 s 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
        while(i>=0){
            if(ans1[i]=='#'){
                skip_s++;
                i--;
            }else if(skip_s>0){
                skip_s--;
                i--;
            }else{
                // 与t进行比较
                break;
            }
        }
        // 再找到 t 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
        while(j>=0){
            if(ans2[j]=='#'){
                skip_t++;
                j--;
            }else if(skip_t>0){
                skip_t--;
                j--;
            }else{
                break;
            }
        }
        if(i>=0&&j>=0){
            if(ans1[i]!==ans2[j]){
                console.log(ans1[i],ans2[j]);
                return false;
            }
        }else if(i>=0||j>=0){
            return false;
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

时间复杂度：O(N+M)，其中 N和 M分别为字符串 S和 T的长度。我们需要遍历两字符串各一次。
空间复杂度：O(1)。对于每个字符串，我们只需要定义一个指针和一个计数器即可。

5.有序数组的平方

977. 有序数组的平方
b站视频讲解-代码随想录
①平方后直接排序
坑： for of不改变原数组

var sortedSquares = function(nums) {
    for(let i=0;i<nums.length;i++){
        nums[i]*=nums[i];
    }
    nums.sort((a,b)=>a-b);
    return nums;
};
1
2
3
4
5
6
7

时间复杂度：O(nlogn)，其中 n是数组nums 的长度。
空间复杂度：O(logn)。除了存储答案的数组以外，我们需要O(logn) 的栈空间进行排序。
②双指针
利用有序数组这个特性，数组平方后的最大值不是在最左边就是在最右边。
双指针：i指向起始位置，j指向终止位置，比较两个指针指向的元素，两个指针逐渐向中间靠拢。
定义一个大小和nums一样的新数组，让k指向新数组的终止位置。

var sortedSquares = function(nums) {
    // 双指针
    let i=0,j=nums.length-1,k=nums.length-1;
    const ans=new Array(nums.length).fill(0);
    while(i<=j){
        if(nums[i]*nums[i]>=nums[j]*nums[j]){
            ans[k]=nums[i]*nums[i];
            i++;
        }else{
            ans[k]=nums[j]*nums[j];
            j--;
        }
        k--;
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

做了不少题，都用到了逆序这个思想