Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
考试周终于结束啦，又要回归到日常来。
今天先把考试周做过的简单题都更新一下,从明天开始每日一更!
题目顺序由易到难,方便自己找回做题的感觉,也方便阅读.
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; } else s1.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问题详解及代码实现】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
