关键内容:数组;二分;快慢指针
首先,在面对数组时,我们必须清楚,数组中的元素在内存中是连续分布的,单独删除一个元素是不可实现的,所以当出现类似删除原数组元素之类的要求时(也可理解为在原数组上进行元素个数变化的操作),操作应为覆盖元素,这是十分基础的知识。
下面以题目来具体分析快慢指针与二分,以及笔者在刷题时遇到的一些idea
26.删除有序数组的重复项
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
//建立快慢指针,满指针用来具体改变数组中元素的值,而快指针则须不断探索数组的元素,当满足某种条件时
//使得慢指针指向的值改变。快指针的探索可由一层for循环推动。
int slow=0;
int fast=0;
for (fast=0;fast<nums.size()-1;fast++) //此处,笔者开始写了fast<nums.size(),发生了执行错误,内存方面有问题
//后来一看,循环内开始的if判断内容使得这个循环结束要提前一步发生。
{
if(nums[fast]==nums[fast+1])
{
continue;
}
nums[slow]=nums[fast];
slow+=1;
}
slow+=1; //此处由于原数组最后一项未经循环所考虑,笔者开始时对最后一项是否加入现在的数组进行了分类讨论,后来一想发现
int size=nums.size()-1; //若最后一项不同于上一项,则包含,若与前一或若干项一样,由于continue,也一定包含,因此直接写进去即可。
nums[slow-1]=nums[size]; //此外,slow的值也值得注意,不过并不难理解
return slow; //最后,热知识;常量与表达式不可使用自增自减式,nums.size()是表达式。
}
};
另外附上评论区看到的做法
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int j = 0;
for (int i = 1; i < nums.size(); i++)
if (nums[j] != nums[i]) nums[++j] = nums[i];
return ++j;
}
咋看一眼感觉很高大上,但其实就是快慢指针思想,只不过slow变成了j,fast变成了i,if的内容变成了原先else的,fast初始值从1开始,结束时把原数组最后一个也包含在内;这样省去了最后的赋值,稍微精简一些。这其实是良好运用了自增自减运算符,配合初值,结束条件等共同造成的。
leetcode27题也是用一样的思想即可解决,当然笔者最开始想到的并非快慢指针,但也并非carl写的暴力解法(双层for循环)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int cou=0;
for (int i=0;i<nums.size();i++)
{
if(nums[i]==val)
{
cou++;
}
}
int len=nums.size()-cou;
vector<int> exm(len);
int j=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=val)
{
exm[j]=nums[i];
j+=1;
}
}
for(int i=0;i<len;i++)
{
nums[i]=exm[i];
}
return len;
}
};
细看便可知,笔者开辟了一个常量数组的空间来方便改变。
844题,也是用快慢指针,那个退格符可对应为负责赋值的slow减一;值得注意的是,题目注意说对空文本输入#还应该是空文本,说明空文本时(代码即slow=0)若遇到#,slow不变(保持为0)
bool backspaceCompare(char * s, char * t){
int size1=strlen(s);
int size2=strlen(t);
int slow1=0;
int fast1=0;
for(fast1=0;fast1<size1;fast1++)
{
if(s[fast1]!='#')
{
s[slow1++]=s[fast1];
}
else
{
if(slow1!=0) //空文本处理
slow1-=1;
}
}
int slow2=0;
int fast2=0;
for(fast2=0;fast2<size2;fast2++)
{
if(t[fast2]!='#')
{
t[slow2++]=t[fast2];
}
else
{
if(slow2!=0) //空文本处理
slow2-=1;
}
}
if(slow1==slow2)
{
for(int i=0;i<slow1;i++)
{
if(s[i]!=t[i])
{
return false;
}
}
return true;
}
return false;
}
最后讲一下二分,首先要明白,二分的使用条件是有序数组,无重复元素
其次,二分涉及区间,大致可分为[left,right];[left,right)这两种区间,相对应的,while循环中的条件就有<=和<的区别,right,left后期赋值多少也是要
考虑到元素到底有没有涉及到。(注意,第二种区间right初值为数组大小)
闭区间的做法
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
int middle;
while(left<=right)
{
middle=left+(right-left)/2; //与(left+right)/2结果相同,这样做主要是防止溢出。也可以将/2用移位>>1来代替,不过要加(),
if(nums[middle]>target) //因为运算符的优先级问题
{
right=middle-1;
}
else if(nums[middle]<target)
{
left=middle+1;
}
else{
return middle;
}
}
return -1;
}
};
总结:用快慢指针对数组进行覆盖元素操作能避免多重循环,且仅在原数组上操作,占用空间少;
二分不难,关键要细致;
要注意到程序的细节,比如if判断语句是否可能出现触及不该触及的内存等,以及循环结束条件,循环不变量等等;
防溢出问题(此篇中用数学方法解决,之前遇到自建int变量溢出,改为了long)
对特殊情况的处理讨论(首先确定其是否真的特殊)。