首页 > 其他分享 >代码随想录day01|26.删除重复项;27.移除元素;704.二分;844.含退格字符串

代码随想录day01|26.删除重复项;27.移除元素;704.二分;844.含退格字符串

时间:2023-01-11 20:36:06浏览次数:69  
标签:二分 nums int 元素 随想录 数组 移除 退格 指针

26
27;
704;
844

关键内容:数组;二分;快慢指针

首先,在面对数组时,我们必须清楚,数组中的元素在内存中是连续分布的,单独删除一个元素是不可实现的,所以当出现类似删除原数组元素之类的要求时(也可理解为在原数组上进行元素个数变化的操作),操作应为覆盖元素,这是十分基础的知识。

下面以题目来具体分析快慢指针与二分,以及笔者在刷题时遇到的一些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)
对特殊情况的处理讨论(首先确定其是否真的特殊)。

标签:二分,nums,int,元素,随想录,数组,移除,退格,指针
From: https://www.cnblogs.com/wryyyyyyy/p/17044815.html

相关文章