leetcode344.反转字符串

链接

基本思路介绍

实际上就是一个reverse函数就可以完成的，但是这边推荐手写一下，辅助理解。实际上采用的也是类双指针的方式进行书写的。

AC-code

class Solution {
public:void reverseString(vector<char>& s) {for(int i = 0; i < s.size()/2; i++){//假设只有h   此时size = 1  1/2=0 所以不变化 成立//假设有he  此时size = 2  2/2=1 此时需要变化 也就是0和1变化swap(s[i],s[s.size()-i-1]);}}
};

leetcode541. 反转字符串II

链接

基本思路介绍

这道题目其实也是模拟，实现题目中规定的反转规则就可以了。

一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

AC-code

class Solution {
public:void reverse(string& s, int start, int end){//start指向开始的位置，end指向结束后的一个位置比如“h” start指向0 end指向1for(int i = 0; i < (end - start)/2; i++){//对于“h”来说 start=0 end=1  1/2=0  也就是不交换//对于“he”来说 start=0 end=2 2/2=1 此时交换的应该是0和1swap(s[start + i] , s[end - i - 1]);}}string reverseStr(string s, int k) {for(int i = 0; i < s.size(); i+=2*k){//先判断是否存在k个if(i+k > s.size()){reverse(s,i,s.size());}else{reverse(s,i,i+k);}}return s;}
};

剑指Offer 05.替换空格

链接

基本思路介绍

实际上看到这道题，正常人的想法肯定就是创建一个新的空间，再用原来的数组进行双指针法不断迭代替换。想法还是很简单的，但是这里采用在原本的字符串中进行迭代运算，节省一下空间。

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

AC-code

class Solution {
public:string replaceSpace(string s) {//先统计空格的数目int count = 0;int lens = s.size();for(auto i : s){if(i == ' ')count++;}//对于字符串重新定义大小s.resize(lens + 2 * count);//采用双指针法进行从后往前进行迭代。left代表的是原本字符串的最后一位，right代表的是现在这个字符串的最后一位。int left = lens - 1;int right = s.size() - 1;//开始检索left，发现left是空格，开始替换%20，如果不是空格本位替换。for(;left >= 0; left--){if(s[left] == ' '){s[right--] = '0';s[right--] = '2';s[right--] = '%';}else{s[right--] = s[left];}}return s;}
};

拓展

这里也给大家拓展一下字符串和数组有什么差别，

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。

在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。

在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。

那么vector< char > 和 string 又有什么区别呢？

其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。