443 String Compression
注意:这里是按照顺序压缩,不忽略顺序就不能用字母表计数再还原了。
如果char num == 1 只需要压入char本身
num > 1 时还需要压入char的个数 按字符压入
class Solution {
public:vector<char> Push(vector<char>& prev , int num , char letter){prev.push_back(letter);if(num == 1){return prev;}else{for(char ch : to_string(num)){prev.push_back(ch);}}return prev;}int compress(vector<char>& chars) {//按顺序压缩字符串//主体:遍历charsint n = chars.size();int count = 0;vector<char> prev;int res = 0 , start = 0;for(int i = 0 ; i < n ; i++){if(i == n-1 || chars[i+1] != chars[i]){//触发压缩计数count = i - start + 1;prev = Push(prev , count , chars[i]);start = i+1;}}res = prev.size();chars.clear();//chars.size() == 0for(int i = 0 ; i < res ; i++){chars.push_back(prev[i]);}return res;}
};
优化:使用双指针,原地压缩,不用管多余出来的部分,因为会直接被cut掉:最后输出的字符组长度是按照return来的。
class Solution {
public:int compress(vector<char>& chars) {//双指针 write readint n = chars.size();int write = 0 , start = 0;for(int read = 0 ; read < n ; read++){if(read == n-1 || chars[read+1] != chars[read]){//触发压缩,使用writeint count = read - start + 1;//字符输入chars[write] = chars[read];write++;//个数字符串的输入if(count > 1){for(char ch : to_string(count)){chars[write++] = ch;}}start = read+1;}}return write;}
};
467 Unique Substrings in Wraparound String【全文背诵】
constraint : 限制,束缚,行为约束---->restrain
原思路:计算单个字符,找到len >1 的子字符 ,计算其除了长度为1以外的子字符串个数
但是如果重复出现abc这个子字符,代码会全部计算进去,但这是错的,只需要计算以a开头的最长的那个字符串的数就可以了,也就是题目中的unique的要求
class Solution {
public:int findSubstringInWraproundString(string s) {vector<int> count(26,0);//记录s中字母个数int res = 0;int len = 0;for(int i = 0 ; i < s.size() ; i++){//单个字符if(count[s[i] - 'a'] == 0){res ++;}count[s[i] - 'a']++;//多个字符if(i >0 &&( s[i] == s[i-1] +1 || (s[i-1] == 'z'&&s[i] == 'a'))){len++;}else{if(len > 1){res = res + len*(len+1)/2 - len;//长度>1的子字符串个数}len = 1;}}if(len > 1){res = res + len*(len+1)/2 - len;//长度>1的子字符串个数}return res;}
};
这个思路中很巧妙的是整先将s整个遍历,使用dp是用来计数以’a’+i结尾的最长字符串的最大长度
介是动态规划?!是我有眼无珠了
优点1:通过加法还原了计算长度为n的字符串的子字符串个数 1 + 2 +3…+ n = n*(n+1)/2
优点2:只取最大的长度,就完成了唯一字符串的要求,不会像原思路中将重复字符串也计算进入res中
class Solution {
public:int findSubstringInWraproundString(string s) {// dp数组,用于记录以每个字符结尾的最长子字符串的长度vector<int> dp(26, 0);int maxLen = 0; // 当前连续子字符串的长度for (int i = 0; i < s.size(); i++) {// 检查当前字符和前一个字符是否连续if (i > 0 && (s[i] == s[i - 1] + 1 || (s[i - 1] == 'z' && s[i] == 'a'))) {maxLen++;} else {maxLen = 1;}int index = s[i] - 'a';dp[index] = max(dp[index], maxLen);}// 计算结果,即所有以每个字符结尾的最长子字符串长度之和int res = 0;for (int len : dp) {res += len;}return res;}
};