##代码随想录 | 刷题记录 | Day02 |C++ | 数组 移除元素&&删除有序数组中的重复项&&移动零&&比较含退格的字符串

27.移除元素

27. 移除元素 - 力扣（LeetCode）

解题思路一：暴力解法

碰到val就一个一个挨着移动到val将val覆盖

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
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int res=0;//记录val数量
        for(int i=0;i<nums.size()-res;i++)
        {
            if(nums[i]==val)//发现一样的
            {
                for(int j=i+1;j<nums.size();j++)//向前移动 
                    nums[j-1]=nums[j];
                res++;
                i--;//循环中的i++会让循环跳过一个数，要进行i--
            }
        }
        return nums.size()-res;
    }
};

/*class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { 
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; 
                size--; 
            }
        }
        return size;

    }
};*/

需要注意的点：

1.每次覆盖完以后循环的i++会让循环跳过一个数字，所以需要i–（一刷错误所在）

2.每次覆盖完以后每次有用的数组长度其实只有nums.size()-res，故循环条件为此；（没有这个条件会超时）

解题思路二：双指针法

首先要搞清楚快慢指针的定义：

快指针是原数组的下标

慢指针是新数组的下标

思路：用快指针遍历原数组，只不要碰到val，说明原数组和新数组下标一致，两者的数也是一样的，碰到val后，快指针移动慢指针暂停，用快指针的值代替慢指针，然后继续移动

27.移除元素-双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int s=0;//慢指针
        for(int f=0;f<nums.size();f++)//快指针
        {
            if(nums[f]!=val)
            {
                nums[s]=nums[f];//得到新数组的过程
                s++;//没有碰到val时s才会++
			}
		}
        return s;//s表示的是新数组下标需要++才是数量
    }
};

注意点：

1.只有没碰到val慢指针才会往前走

2.巧妙地覆盖过程得到了新数组

相关题目

26.删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

解法：双指针

快慢指针定义：

快：原数组下标

慢：新数组下标

初始化：快慢指针都从1开始，因为重复项需要和前一项进行比较而不是固定值val

思路：

快指针遍历原数组，只有当快指针和其前一项所指向的数不同时慢指针才会进行覆盖和++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
       	int s=1;
        for(int f=1;f<nums.size();f++)
        {
            if(nums[f]!=nums[f-1])//说明这一项不是重复项
            {
                nums[s]=nums[f];//放入新数组
                s++;//新数组下标++
			}
		}
        return s;
    }
};

关键点：考虑if中的条件和快慢指针的初始化

283.移动零

283. 移动零 - 力扣（LeetCode）

解法：双指针

快慢指针定义：

依旧是原数组和新数组下标

思路：

其实就把元素0移除（和27一样的操作），然后把新数组之后的都赋值成0即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int s=0;
        for(int f=0;f<nums.size();f++)//移除元素0的过程
        {
            if(nums[f]!=0)
            {
                nums[s]=nums[f];
                s++;
            }
        }
        for(int i=s;i<nums.size();i++)//赋值成0的过程，注意是从s开始，s就是新数组的下一个数
            nums[i]=0;
    }
};

844.比较含退格的字符串

844. 比较含退格的字符串 - 力扣（LeetCode）

解法一：栈思想

思路：遇到#就pop栈顶元素并且直接到下一个，不是#就入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }
    string build(string s)
    {
        string str;
        for(auto c:s)
        {
            if(c!='#')
                str.push_back(c);
            else if(!str.empty())
                str.pop_back();
        }
        return str;
    }
};

解法二：双指针（本题不太会看了题解的，复习时多加注意）

快慢指针定义：
快：原数组下标

慢：新数组下标

思路：也是和移除元素差不多，遇到#就回退，表现为新数组下标s–，即新数组的内容少了一个，当然前提是s要大于0，如果没有遇到就赋值给新数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }
    string build(string str)//处理字符串
    {
        int s=0;
        for(int f=0;f<str.size();f++)
        {
            if(str[f]!='#')//没有碰到就赋值给新的数组
            {
                str[s]=str[f];
                s++;
            }
            else if(s>0)//碰到了且s大于0
                s--;
        }
        return string(str.begin(),str.begin()+s);//返回新数组部分
    }
};