做网站编码,网络协议分析课程设计报告,安卓商城网站开发,苏州互联网招聘文章目录 一、压缩字符串思路 二、仅执行一次字符串交换能否使两个字符串相等思路1#xff1a;计数法思路2#xff1a;模拟法 总结 一、压缩字符串
点我直达~ 思路
使用双指针法
大致过程如下#xff1a;
使用双指针#xff0c;分别读#xff08;read#xff09;计数法思路2模拟法 总结 一、压缩字符串
点我直达~ 思路
使用双指针法
大致过程如下
使用双指针分别读read写write指针读指针不断向后走当read指针走到最后位置处时或read和read的下一个位置与当前位置不相等时说明该read指针走到了某一串相同子串的最后位置处。此时write指针开始记录具体的字符给定一个left指针记录当前位置此时每一个子串的长度都是 read - left 1使用短除法将子串的长度记录下来再进行逆置即可。
具体操作如下
1.给定两个指针write 和 leftleft指针记录每一个子串的开始位置分别指向第一个元素的位置。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(vectorchar chars) {int write 0,left 0;for(int read 0;readchars.size();read){if(read chars.size()-1 ||chars[read]!chars[read1]){ chars[write] chars[read];//存储字符int begin write; // 逆置的左下标int n read - left 1 ; if(n1){while(n){chars[write] (n%10) 0;n/10;}//逆置的右下标是writereverse(chars[begin],chars[write]);}left read1;}}return write;}
};时间复杂度On空间复杂度O1
二、仅执行一次字符串交换能否使两个字符串相等
点我直达~ 思路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,如果发现有两个以上字母不同不管怎么交换都不等 vectorint v1; // 两个下标int count 0;//计算s1和s2有几个不等的字母for(int i 0;is1.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;in;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];}
};总结
通过写今天的两道题重新认识了双指针法的厉害的地方哪哪都可以考虑双指针法。 比如排序字符串逆置字符串压缩等等有关字符串的题都可以考虑一下双指针法 还有只要涉及到两个字符串中的两个字符的问题都可以进行下标的模拟或者计数法来实现。
