【每日挠头算法题（2）】压缩字符串|仅执行一次字符串交换能否使两个字符串相等

---

一、压缩字符串

点我直达~

思路

使用双指针法

大致过程如下：

• 使用双指针，分别读（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;}//逆置的右下标是writereverse(&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.相等，trueif(s1 == s2)return true;//2.长度不等，falseif(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;//该情况是超过两个不同的字符elsereturn false;}//该情况是没有不同的字符if(pos1 == -1)return true;//该情况是只有一个不同的字符if(pos2 == -1)return false;//该情况是正常情况return s1[pos1] == s2[pos2] && s1[pos2] == s2[pos1];}
};

---

总结

通过写今天的两道题，重新认识了双指针法的厉害的地方，哪哪都可以考虑双指针法。

比如：排序，字符串逆置，字符串压缩等等，有关字符串的题都可以考虑一下双指针法
还有只要涉及到两个字符串中的两个字符的问题，都可以进行下标的模拟，或者计数法来实现。