27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
方法一 暴力解法
思路:两层for循环,外层循环来遍历每一个元素,判断是否和val相等.内层循环,在找到和val相等的元素后进行整体前移.
参考代码1
//暴力法 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]; } size--; i--;//下次直接从当前位置进行判断. } } return size; }
时间复杂度：O ( n 2 )
空间复杂度：O ( 1 )
方法二 双指针
快的指针来遍历每一个元素,慢的指针来控制下一次有效元素存放的位置.
参考代码2
//双指针法:解决数组,链表,字符串元素的变化时经常用到 int removeElement(vector<int>& nums, int val) { int slowIndex = 0; for(int fastIndex = 0;fastIndex < nums.size();fastIndex++){ if(nums[fastIndex]!=val){//如果相等,则fastIndex向后移动,showIndex保持不变. 如果不等,则移动元素到前面. nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; }
时间复杂度：O ( n )
空间复杂度：O ( 1 )
26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
方法一:暴力法(超时)
参考代码1
int removeDuplicates(vector<int>& nums) { int size = nums.size(); if(size==1){ return 1; } for(int i = 1;i<size;i++){ if(nums[i]==nums[i-1]){//如果当前元素和上一个元素相等,则将该元素以及其后的元素同时后移 for(int j = i+1;j<size;j++){ nums[j-1] = nums[j]; } size--; i--;//下次直接从当前位置进行判断. } } return size; }
方法二:双指针
参考代码2
// 双指针法 int removeDuplicates(vector<int>& nums) { if(nums.size()==1){ return 1; } if(nums.size()==0){ return 0; } int slowIndex = 1;//showIndex当前要放的元素的位置. for(int fastIndex = 1; fastIndex<nums.size();fastIndex++){//遍历所有的元素 if(nums[slowIndex-1]!=nums[fastIndex]){//如果当前的元素和之前的元素一样,则fastIndex继续后移 跳过该元素 nums[slowIndex++] = nums[fastIndex]; //否则fastIndex放在指定的位置.. } } return slowIndex; }
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
方法一:暴力法
void moveZeroes(vector<int>& nums) { int size = nums.size(); for(int i = 0;i<size;i++){ if(!nums[i]){ for(int j = i+1;j<size;j++){ nums[j-1] = nums[j]; } size--;//不过多解释... i--; } } for(int i = size;i<nums.size();i++){ nums[i] = 0; } }
方法二:双指针
//双指针 void moveZeroes(vector<int>& nums) { int slowIndex = 0; for(int fastIndex = 0;fastIndex<nums.size();fastIndex++){ if(nums[fastIndex]){//不为0 nums[slowIndex++] = nums[fastIndex]; } } for(int j = slowIndex;j<nums.size();j++){ nums[j] = 0; } }
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = "ab##", t = "c#d#" 输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = "a##c", t = "#a#c" 输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b" 输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
方法一:栈模拟(自己的代码)
bool backspaceCompare(string s, string t) { stack<char> S; string s1="",s2=""; //这里可以优化一下,封装成函数... for(int i = 0;i < s.size();i++){ if(s[i]=='#'&&S.size()>0){//如果等于#但Q为空,则不进行操作 S.pop(); }else if(s[i]!='#'){ S.push(s[i]); } } while(!S.empty()){ s1+=S.top(); S.pop(); } for(int i = 0;i < t.size();i++){ if(t[i]=='#'&&S.size()>0){//如果等于#但Q为空,则不进行操作 S.pop(); }else if(t[i]!='#'){ S.push(t[i]); } } while(!S.empty()){ s2+=S.top(); S.pop(); } if(s1==s2){ return true; } return false; }
方法二:栈模拟(卡尔大佬的代码,未经过优化)
//栈==>直接使用字符串的push_back和pop_back()来解决. bool backspaceCompare(string s, string t) { string s1,s2; for(int i = 0; i < s.size(); i++) { if(s[i]!='#') { s1.push_back(s[i]); } else if(!s1.empty()) { s1.pop_back(); } } for(int j = 0; j < t.size(); j++) { if(t[j]!='#') { s2.push_back(t[j]); } else if(!s2.empty()) { s2.pop_back(); } } if(s1==s2) { return true; } return false; }
栈模拟最终的代码
//进行程序的优化 bool backspaceCompare(string s, string t) { return backspaceCompare(s)==backspaceCompare(t); } string backspaceCompare(string s) { string s1; for(int i = 0; i < s.size(); i++) { if(s[i]!='#') { s1.push_back(s[i]); } else if(!s1.empty()) { s1.pop_back(); } } return s1; }
双指针(待补充)
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
方法一:暴力法
直接for循环+sort排序
参考代码1
vector<int> sortedSquares(vector<int>& nums) { for(int i = 0; i < nums.size(); i++) { nums[i] = nums[i]*nums[i]; } sort(nums.begin(),nums.end()); return nums; }
方法二:双指针
数字本身是有序的,只是负数平方之后也可能成为最大数.
但是最大的那个数只可能在数组的最左边或者在最右边,不可能在中间的.中间的数的平方都小于两边数的平方.所以我们考虑使用双指针.
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]; 。
参考代码2
//方法二,双指针法 vector<int> sortedSquares(vector<int>& nums) { vector<int> result(nums.size()); int i = 0,j = nums.size() - 1,k = result.size()-1; while(i<=j){ if(nums[i]*nums[i]<nums[j]*nums[j]){ result[k--] = nums[j]*nums[j]; j--; }else{ result[k--] = nums[i]*nums[i]; i++; } } return result; }
