第七天|
题目1 344.反转字符串
344.反转字符串 | 代码随想录
字符串基础操作！ | LeetCode：344.反转字符串_哔哩哔哩_bilibili
笔记
为什么是O(1)的额外空间? 我的代码中使用了4个int变量，即额外空间是固定的，是常数，所以是O(1)
异或实现的swap：
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
原理：首先知道异或的一些性质：a ^ a = 0（任何数与自己异或得到0） a ^ 0 = a（任何数与0异或得到自身） a ^ b = b ^ a
假设s[i] = a，s[j] = b
第一步：s[i] = a ^ b，s[j] = b
第二步：s[i] = a ^ b，s[j] = b ^ a ^ b = b ^ b ^ a = 0 ^ a = a
第三步：s[i] = a ^ b ^ a = a ^ a ^ b = b，s[j] = a交换完成
注意：这种方法有一个潜在风险：如果i == j（交换的是同一个位置） 会导致数值消失，全部变为0；
实操出现问题
无
代码/比较
class Solution {
public:void reverseString(vector<char>& s) {int len=s.size();for(int i=0,j=len-1;i<len/2;i++,j--){int tmp=s[i];s[i]=s[j];s[j]=tmp;}}
};
541. 反转字符串II
笔记：
步长为2k进行遍历。
实操出现问题：
reverse函数用于反转字符串： reverse(s.begin()+i,s.begin()+i+k);
reverse函数是左闭右开
代码/比较：
class Solution {
public:string reverseStr(string s, int k) {for(int i=0;i<s.size();i+=2*k){if(i+k<=s.size()){reverse(s.begin()+i,s.begin()+i+k);continue;}else{reverse(s.begin() + i, s.end());}}return s;}
};
替换数字
笔记：
很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
- 不用申请新数组。
- 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
实操出现的问题：
在赋值中left和right的移动：什么时候移动？情况一：left指针没有碰到数字：每一次赋值后无论是left还是right都要往后移动
情况二：left指针碰到了数字：此时left不需要移动，right每赋值一次向后移动；left在right完成一个“right”的赋值后再移动。
代码/比较：
#include <iostream>
using namespace std;
int main()
{string s;//输入的字符串cin>>s;int count=0;//用于计算多少个数字for(int i=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9')count++;}int len_before=s.size();//之前的长度s.resize(s.size()-count+count*6);//right指向新str，left指向旧strint left=len_before-1;int right=s.size()-1;//循环遍历整个数组，如果left碰上了数字，则right从右往左依次赋值rebmun；如果没有碰到数字，则将旧str的元素复制到新str中while(left!=right){if(s[left]>='0'&&s[left]<='9')//碰到数字{s[right--]='r';s[right--]='e';s[right--]='b';s[right--]='m';s[right--]='u';s[right--]='n';left--;}elses[right--]=s[left--];}cout<<s<<endl;}