leetcode 27. 移除元素

leetcode 27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

思路：
方法1：暴力求解：两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
方法2：双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 定义快慢指针
• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

#include <stdio.h>#if 1
//法1：暴力解法，两层循环
int removeElement(int* nums, int numsSize, int val) {//一层循环用于遍历数组元素for(int i=0;i<numsSize;i++){//找到要删除的元素，直接把后面的元素往前移一位，进行覆盖实现删除的目的if(nums[i]==val){//把后面的元素往前移一位for(int j=i+1;j<numsSize;j++){nums[j-1]=nums[j];}i--;//下一轮循环从新覆盖位置开始numsSize--;//删除元素数组长度减1}}return numsSize;
}
#endif
#if 0
//法2：使用快慢指针 快指针用于查找新数组元素，新数组就是不含有目标元素的数组
//慢指针 指向更新 新数组下标的位置
int removeElement(int* nums, int numsSize, int val) {int slow=0;//快指针循环遍历数组，找到新数组元素，即不等于要删除值的元素，用慢指针接受新数组下标for(int fast=0;fast<numsSize;fast++){//fast找到新数组元素会更新，找到要删除的会跳过该元素，继续寻找下一个if(nums[fast]!=val){nums[slow]=nums[fast];//找到新数组元素并进行更新slow++;//新数组长度增加}}return slow;
}
#endif
//双指针的优化，找到要删除的元素直接用最后一个元素覆盖此元素，避免了需要保留的元素的重复赋值操作
#if 0
int removeElement(int* nums, int numsSize, int val) {int left =0,right=numsSize-1;while(left<=right){//若left指向删除元素,用最后元素right覆盖，包括了赋值过来的元素恰好也等于 val情况，//会继续将right指向的元素复制过来，直到左指针指向的元素的值不等于 val 为止if(nums[left]  == val){nums[left] = nums[right];right--;}else left++;}return left;
}
#endifint main()
{int nums[] = {3,2,2,3,5,6,7};int retSize=removeElement(nums,sizeof(nums)/sizeof(nums[0]),3);printf("retSize:%d\n",retSize);
}

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

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

示例 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 。不需要考虑数组中超出新长度后面的元素。

思路：快慢指针法：快指针找下一个不同元素值的下标位置，将该位置值赋值给慢指针，简单来说就是拿后一个值与前一个值进行比较，不同就更新，相同就跳过继续往后遍历

#include <stdio.h>//快慢指针法：快指针找下一个不同元素值的下标位置，将该位置值赋值给慢指针
int removeDuplicates(int* nums, int numsSize) {//长度为0，不包含任何元素if(numsSize==0)return 0;int slow=0;//慢指针初始指向0下标//fast从下表为1开始遍历元素，找到下一个不同元素要填入的下标位置for(int fast=1;fast<numsSize;fast++){//快指针与新数组的慢指针进行比较if(nums[fast]!=nums[slow]){//找到后填入新数组的下一位位置，因为0号位置肯定是有效的nums[slow+1]=nums[fast];slow++;}}return slow+1;//返回长度为下标值加1
}int main()
{int nums[]={0,0,1,1,1,2,2,3,3,4};int ret=removeDuplicates(nums,sizeof(nums)/sizeof(*nums));if(ret!=0){for(int i=0;i<ret;i++)printf("%d ",nums[i]);}else return -1;return 0;
}

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

思路：

• 法1：双指针，slow记录不为0的元素下表，fast遍历数组，找到不为0的元素赋值给slow，遍历结束后，将末尾元素全置为0，用到复制
• 法2：双指针，slow 指针用于标记非零元素应该放置的位置，fast 指针用于遍历数组。当fast指针遇到非零元素时，将其与slow 指针指向的元素交换，并移动slow 指针

#include <stdio.h>#if 1
//法1：双指针，slow记录不为0的元素下表，fast遍历数组，找到不为0的元素赋值给slow，
//遍历结束后，将末尾元素全置为0
void moveZeroes(int* nums, int numsSize) {if(numsSize==0)return ;int slow=0;//slow记录不为0的元素下表，fast遍历数组，找到不为0的元素赋值给slowfor(int fast=0;fast<numsSize;fast++){if(nums[fast]!=0){nums[slow++]=nums[fast];}}//直接将末尾元素全置为0for(int i=slow;i<numsSize;i++)nums[i]=0;
}
#endif
/*官方：slow 指针用于标记非零元素应该放置的位置，fast 指针用于遍历数组。
当fast指针遇到非零元素时，将其与slow 指针指向的元素交换，并移动slow  指针。*/
#if 0
void swap(int *p1,int *p2)
{int temp=*p1;*p1=*p2;*p2=temp;
}
void moveZeroes(int* nums, int numsSize) {int slow=0,fast=0;while(fast<numsSize){//fast找到不为0的元素与slow进行交换if(nums[fast]!=0){swap(nums+slow,nums+fast);slow++;//slow指向下一个不为0的元素下标} // else  fast++;  fast是每遍历一个元素后加1，继续遍历下一个元素，加else 会导致只有==0的情况才会继续遍历fast++;}
}
#endif
int main()
{int nums[]={0,1,0,3,12};moveZeroes(nums,sizeof(nums)/sizeof(nums[0]));for(int i=0;i<sizeof(nums)/sizeof(nums[0]);i++)printf("%d ",nums[i]);return 0;
}

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。

示例 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 = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

思路：
双指针法：一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关
定义 skip 表示当前待删除的字符的数量，逆序遍历数组，
若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1，i–；
若该字符为普通字符：

• 若 skip 为 0，则说明当前字符不需要删去,退出循环与另一字符串进行比较是否相等；
• 若 skip 不为 0，则说明当前字符需要删去，让 skip 减 1，同时数组下标–，跳过此元素表示退格。

bool backspaceCompare(char* s, char* t) {int i=strlen(s)-1,j=strlen(t)-1;int skipS=0,skipT=0;//记录待删除字符的数量while(i>=0 || j>=0){//s数组中找while(i>=0){//找到退格符，skip+1，数组下标前移if(s[i]=='#'){skipS++;i--;}//当前字符不为退格且skip不为0，说明要进行退格操作else if(skipS>0){skipS--;i--;}else break;//字符不为退格且skip不为0，跳出循环与另一个字符数组比较}//t数组中找while(j>=0){//找到退格符，skip+1，数组下标前移if(t[j]=='#'){skipT++;j--;}//当前字符不为退格且skip不为0，说明要进行退格操作else if(skipT>0){skipT--;j--;}else break;//字符不为退格且skip不为0，跳出循环与另一个字符数组比较}if (i >= 0 && j >= 0) {//两个字符不相等if (s[i] != t[j]) {return false;}} //其中一个字符串处理完，另一个字符串未处理完的情况也不相等，因为长度不一致else {if (i >= 0 || j >= 0) {return false;}}i--;j--;}return true;
}