【双指针问题】LeetCode344、345、 844、283问题详解及代码实现

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

 

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接         

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

考试周终于结束啦，又要回归到日常来。

今天先把考试周做过的简单题都更新一下,从明天开始每日一更!

题目顺序由易到难,方便自己找回做题的感觉,也方便阅读.

目录

344. 反转字符串:

白话讲解:

题解:

代码实现:

LeetCode 345. 反转字符串中的元音字母:

白话讲解:

题解:

注:

代码实现:

LeetCode 844. 比较含退格的字符串:

白话讲解:

题解:

代码实现:

 优化

优化后的版本:

LeetCode 283. 移动零:

白话讲解:

这题的两种解法非常妙!都是我无法想到的  

题解1:

代码实现:

题解2:

代码实现:

---

344. 反转字符串:

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

白话讲解:

倒序输出整个数组

题解:

这题非常的简单,就是利用双指针的思想,从头尾开始遍历,并交换两个指针所指向的字符.虽然很简单,但也可以帮我们复习一下双指针的本质,毕竟算法题万变不离其宗.

可以直接使用swap,但Leecode上的速度评测好像没有这样手动交换的快.

代码实现:

class Solution {
public:void reverseString(vector<char>& s) {int left=0,right=s.size()-1;while(left<right){char tmp=s[left];s[left++]=s[right];s[right--]=tmp;}}
};

 

LeetCode 345. 反转字符串中的元音字母:

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

输入：s = "hello"
输出："holle"

输入：s = "leetcode"
输出："leotcede"

白话讲解:

大意就是将题目中所有出现的元音字母(包含大小写)反转.

题解:

利用hash的思想(为什么我又不直接用hash呢?因为还没学www,下次一定)将所有需要用到的结果保存起来,也就是"AEIOUaeiou",这里我们把他放到string类中,因为它支持find函数,比较方便.

之后利用上一题的基础模板(双指针头尾遍历)

先遍历起始位置left,利用find比对当前位置是否是元音字母,不是就左移,是的话就停下,等待交换

下一步从尾开始向前遍历right,重复上面的步骤.

当指针停下时就说明left,right指向的字母都为元音,此时将他们交换即可.

注:

find函数没找到返回的是-1 

因为前两步都为自增操作,所以交换要判定一下是否越界

代码实现:

class Solution {
public:string reverseVowels(string s) {int right=s.size()-1,left=0;string tag="aeiouAEIOU";while(left<=right){while(left<=right&&tag.find(s[left])==-1)left++;while(left<=right&&tag.find(s[right])==-1)right--;if(left<=right)swap(s[left],s[right]);  left++;right--;}return s;}};  

 

LeetCode 844. 比较含退格的字符串:

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

注意：如果对空文本输入退格字符，文本继续为空。

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

白话讲解:

给两段字符串,#代表backspace,判断处理完后两段字符串是否相等

题解:

分析题目可知,仍然是一个双指针的问题.但我们可以用容器里的push,与pop简化这一操作.

遍历数组,若不为#则将字符存入,若为#且容器不为空则将上一个字符删除,继续遍历下一个.

最后利用string的特性直接比较并返回就可以了.

代码实现:

class Solution {
public:bool backspaceCompare(string s, string t) {string s1,t1;for(int i=0;i<s.size();i++){if(s[i]=='#'){if(!s1.empty())s1.pop_back();else continue;}elses1.push_back(s[i]);}for(int j=0;j<t.size();j++){   if(t[j]=='#'){if(!t1.empty())t1.pop_back();else continue;}else t1.push_back(t[j]);}return t1==s1;}
};

 

 优化

这段代码有一点小小的问题,逻辑处理有点冗杂.

可以将中间判断的逻辑优化一下.

这里是先判定他是否为#,若为#则在进入新的一层判断是否为空,若不为空才删除,若为空则继续.

那我们可以抽出里面的核心逻辑

我只要知道这段是不是#,如果不是#我直接push,没有push的话说明是#,则判断他是否为空,有点像 

if(true)return ;
a++; 

当你true了底下就不会运行,当你false时,也不需要再去判定

优化后的版本:

class Solution {
public:bool backspaceCompare(string s, string t) {string s1,t1;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]!='#')t1.push_back(t[j]);else if(!t1.empty())t1.pop_back();}return t1==s1;}
};

 

 

LeetCode 283. 移动零:

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

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

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

白话讲解:

将非0元素整体往前移(不改变顺序),然后0放末尾

这题的两种解法非常妙!都是我无法想到的  

题解1:

我们要做的是将0的位置与非0 的对调,参考第一题,若采用前后指针的做法,就会破坏元素本来的顺序.所以不可行.

那我们想想临位指针的做法,参照快速排序的思想,将非0的都放到左边,其余放到右边.

所以依次遍历,先遍历右指针,当找到非0(交换因子)就停下

这时候左指针去在(0-right的范围里去找0),找到停下后交换

 

代码实现:

class Solution {
public:void moveZeroes(vector<int>& nums) {int i=0,j=1;while(j<nums.size()){while(j<nums.size()&&nums[j]==0)j++;while(i<j-1&&nums[i]!=0)i++;if(!nums[i]&&j<nums.size())swap(nums[i],nums[j]);j++;i++;}}
};

 

 

题解2:

还是两个临位指针,这个类似归并排序的思想,right指针向右进行遍历,遇到非0数就停下,将该值赋给left指针指向的位置,之后left++,right继续重复上面的步骤.

当right指针遍历到末尾时,此时说明left前的数据即为这个数组中出现的所有非0元素,此时将[left,num.size())的区间全部填充为0即可.

 

代码实现:

class Solution {
public:void moveZeroes(vector<int>& nums) {int i=0,j=0;while(j<nums.size()){while(j<nums.size()&&nums[j]==0)j++;if(nums.size()<=j)break;nums[i++]=nums[j++];}for(;i<nums.size();i++)nums[i]=0;}
};

 

 

 

完结撒花：

🌈本篇博客的内容【LeetCode344、345、 844、283问题详解及代码实现】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！