一、压缩字符串
思路
使用双指针法
大致过程如下：
- 使用双指针，分别读（read），写（write）指针，读指针不断向后走，当read指针走到最后位置处时，或read和read的下一个位置与当前位置不相等时，说明该read指针走到了某一串相同子串的最后位置处。
- 此时write指针开始记录具体的字符，给定一个left指针记录当前位置，此时每一个子串的长度都是
read - left +1 - 使用短除法将子串的长度记录下来，再进行逆置即可。
具体操作如下：
- 1.给定两个指针write 和 left
（left指针记录每一个子串的开始位置），分别指向第一个元素的位置。 - 2.使用read指针，遍历字符串，当read遇到其后面一个字符与当前字符不等，或者read走到末尾时，此时将write指针记录当前子串的字符，以及长度，那就让write一边记录一边往后走。
- 3.当write指针开始记录子串的长度时，给一个下标
begin，这个begin就是记录子串的长度的起始位置，比如一个串的长度为：123，需要记录到chars数组的是[“1”,“2”,“3”]，begin记录着"1"下标的位置。 - 4.使用短除法将某一个串的长度的每一位记录下来，然后逆置，逆置的开始是begin，结尾是write。
- 5.因为write总是向后走，知道走到记录完所有的字符以及每一个相同的字符串的长度，则最终返回write的长度即可
具体代码如下：
class Solution { public: int compress(vector<char>& chars) { int write = 0,left = 0; for(int read = 0;read<chars.size();++read) { if(read == chars.size()-1 || chars[read]!=chars[read+1]) { chars[write++] = chars[read];//存储字符 int begin = write; // 逆置的左下标 int n = read - left + 1 ; if(n>1) { while(n) { chars[write++] = (n%10) + '0'; n/=10; } //逆置的右下标是write reverse(&chars[begin],&chars[write]); } left = read+1; } } return write; } };
时间复杂度：O（n），空间复杂度O（1）
二、仅执行一次字符串交换能否使两个字符串相等
思路1：计数法
- 情况1：如果两个字符串的长度不同，那么不管怎么交换一定不等，返回false
- 情况2：如果两个字符串的长度相同：
- 情况1：如果不相同的字符超过两个，或者不相同的字符只有一个，那么两个字符串不管怎么交换字符一定不等，返回false
- 情况2：如果不相同的字符恰好为两个，此时有两种方法解决：
- 1.交换这两个不相同的字符的位置，如果交换后s1 == s2，返回true，否则false。
- 2.判断 s1[i] == s2[j] ,s1[j] == s2[i]是否满足即可。
具体请看下面代码：
class Solution { public: bool areAlmostEqual(string s1, string s2) { //1.相等，true if(s1 == s2) return true; //2.长度不等，false if(s1.size() != s2.size()) return false; //3.遍历s1和s2,如果发现有两个以上字母不同，不管怎么交换都不等 vector<int> v1; // 两个下标 int count = 0;//计算s1和s2有几个不等的字母 for(int i = 0;i<s1.size();++i) { if(s1[i]!=s2[i]) { ++count; v1.push_back(i); } } //如果不是只有两个字母不同，不管怎么交换一定不等。 if(count !=2) return false; return s1[v1[0]] == s2[v1[1]] && s1[v1[1]] == s2[v1[0]] ; //下面的操作也可 //swap(s2[v1[0]],s2[v1[1]]); // if(s1 == s2) // return true; // return false; } };
思路2：模拟法
模拟法整体思路与计数法大致相同
给定两个初始值pos1 ，pos2均为 -1，记录两个字符串不同的字符的下标。
- 如果不同位置超过两个或者只有一个，返回false
- 如果不同位置为两个或者没有不同位置，返回true
具体请看下面代码：
class Solution { public: bool areAlmostEqual(string s1, string s2) { int n = s1.size(),pos1 = -1,pos2 = -1; for(int i = 0;i<n;++i) { if(s1[i] == s2[i]) continue; if(pos1 == -1) pos1 = i; else if(pos2 == -1) pos2 = i; //该情况是超过两个不同的字符 else return false; } //该情况是没有不同的字符 if(pos1 == -1) return true; //该情况是只有一个不同的字符 if(pos2 == -1) return false; //该情况是正常情况 return s1[pos1] == s2[pos2] && s1[pos2] == s2[pos1]; } };
总结
通过写今天的两道题，重新认识了双指针法的厉害的地方，哪哪都可以考虑双指针法。
比如：排序，字符串逆置，字符串压缩等等，有关字符串的题都可以考虑一下双指针法
还有只要涉及到两个字符串中的两个字符的问题，都可以进行下标的模拟，或者计数法来实现。
