廊坊酒店网站建设,建设工程安全监督备案网站,自学建设网站,家装公司招聘装修工人文章目录 一、旋转字符串思路1思路2 二、亲密字符串思路 总结 一、旋转字符串
点我直达终点~ 思路1
前提#xff1a;如果s串和goal串长度不等#xff0c;则goal串不可能是s串旋转得来#xff0c;直接返回false#xff1b;
通过观察#xff0c;可以发现每旋转一次#… 文章目录 一、旋转字符串思路1思路2 二、亲密字符串思路 总结 一、旋转字符串
点我直达终点~ 思路1
前提如果s串和goal串长度不等则goal串不可能是s串旋转得来直接返回false
通过观察可以发现每旋转一次第一个字符就会出现在最后一个字符的位置处其余字符均往前挪动一个位置。 所以我们首先将第一个字符保存然后挪动其他字符再将保存的字符放到最后。 其次判断s和goal是否相等如果不等则继续按照上述方式旋转 注意:如果旋转s的长度次后与goal仍然不想等返回false 代码:
class Solution {
public:bool rotateString(string s, string goal) {if(s.size()!goal.size())return false;for(int j 0 ; j s.size();j){char ch s[0];//旋转一遍for(int i 1;i s.size();i){s[i-1] s[i];}s[s.size()-1] ch;if(s goal){return true;}}//如果旋转完s.size()遍还不是true那就falsereturn false;}
};时间复杂度O(N^2) 空间复杂度O(1)(原地旋转)
思路2
前提如果s串和goal串长度不等则goal串不可能是s串旋转得来直接返回false
一个巧妙的解法运用如果goal串由s串旋转得来那么goal串一定是ss串的子串。 只需要判断goal字符串是否为ss串的子串即可。
class Solution
{
public:bool rotateString(string s, string goal){string ss ss;if(s.size() goal.size() ss.find(goal) ! string::npos)return true;return false;}
};时间复杂度O(N) 空间复杂度O(N)
二、亲密字符串
点我直达终点~
思路
前提如果s串和goal串长度不等则goal串不可能是s串旋转得来直接返回false
对于这道题首先遍历一遍s串一边遍历一边与goal字符串进行对比如果对应下标的goal串的字符和s串的对应下标的字符不相等则记录不等的字符和下标。s串和goal串一定只有两个不相等的字符 找到后如果pos1下标和pos2下标相同说明s串和goal串一定相等。 然而这里存在两种情况如题目描述 情况1ab和ab 情况2aa和aa 此时我们不需要分情况讨论只需要找到s字符串的任意一个字符如果出现两次及以上则说明交换s字符串的任意两个相同的字符一定与goal字符串相等。 比如: aabab 和aababs字符串中的a出现了三次b出现了两次 那么无论怎么交换其中的a或者bs字符串始终和goal字符串相等。 如果字符串pos1下标和pos2下标不同则交换对应的pos1和pos2的字符再判断是否与goal串相等即可。 详细请看代码
class Solution {
public:bool buddyStrings(string s, string goal) { //1.长度不等必然不是亲密字符串if(s.size()!goal.size())return false;char arr[2];//找第一个不相同的字符,并记录下标int i 0;int pos1 0,pos2 0;for(; is.size();i){if(s[i]!goal[i]){arr[0] s[i];pos1 i;break;}}//找第二个不相同的字符for(i1; is.size();i){if(s[i]!goal[i]){arr[1] s[i];pos2 i;break;}}// 如果pos1 pos2,说明s和goal是完全相等的两个串//此时有两种情况如果s中有两个位置交换后还是原来的s此时s和goal相等。//但不管是哪种情况我们都只需要找出任意一个字符出现2次及以上就可以知道是亲密字符串if(pos1 pos2){vectorint count(26);for(int i 0;is.size();i){count[s[i] - a];if(count[s[i] - a]2)return true;}return false;}//此种情况不是s串和goal串相等那么正常交换两个字符的位置然后判断是否与goal相等即可。else{swap(s[pos1],s[pos2]);if(s goal)return true;return false;}}
};时间复杂度O(N) 空间复杂度O(1) 只消耗常量个空间即26 总结
通过这两道题学习到了旋转字符串的一般规律是转化为找子串的问题 而亲密字符串的本质就是分情况讨论 情况1如果s!goal 情况2如果sgoal 的分别处理方式。
