字符串
转自：🔥【github】
⚡️字符串⚡️
滑动窗口思想(双指针进阶版）
有效的字母异位词
- 示例：
1
2输入: s = "anagram", t = "nagaram"
输出: true - 哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//构建哈希数组，用索引0~26代表a~z
bool isAnagram(string s, string t) {
if(s.length()!=t.length())return false;
//普通数组必须提前分配空间，或者用动态数组
int hashArr[26]={0};
for(int i=0;i<s.length();++i){
hashArr[s[i]-'a']++;
}
for(int i=0;i<t.length();++i){
hashArr[t[i]-'a']--;
}
//判断个数也可用i<26
for(int i=0;i<sizeof(hashArr)/sizeof(hashArr[0]);++i){
if(hashArr[i]!=0)return false;
}
return true;
}
};
最长回文串
Leetcode
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 //hash表统计字符出现频率
//偶数加入长度
//奇数-1加入长度
//最后回文长度小于字符集长度说明一定有未使用的字符，回文长度再加1
int longestPalindrome(string s) {
int longestLength=0;
int hash[127]={0};
for(int i=0;i<s.length();++i){
hash[s[i]]++;
}
for(int i=0;i<sizeof(hash)/sizeof(hash[0]);++i){
if(hash[i]%2==0){
longestLength+=hash[i];
}else{
longestLength+=hash[i]-1;
}
}
return longestLength<s.length()?++longestLength:longestLength;
}
};
同构字符串
- 示例：
1
2输入: s = "egg", t = "add"
输出: true1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//哈希交叉映射
//比如对于tit和pap，
//对于tit所有的t对应p，所有的i对应a
//对于pap所有的p对应t，所有的a对应i
//同时遍历两个字符串，就去map中寻找 该字母是否有对应值（映射），
//如果有就去查该映射的值是否与另一个字符串中对应位字母相同，如果不同就不是同构字符串
bool isIsomorphic(string s, string t) {
unordered_map<char,char> sHash;
unordered_map<char,char> tHash;
for(int i=0;s[i]!='\0';++i){
if(sHash.count(s[i]) && s[i]!=tHash[t[i]]){
return false;
}
else if(tHash.count(t[i]) && t[i]!=sHash[s[i]]){
return false;
}
else{
tHash[t[i]]=s[i];
sHash[s[i]]=t[i];
}
}
return true;
}
};
回文子串
- 中心扩展思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int cnt=0;
//回文字符串：奇数个数和偶数个数两种
//所以有两种中心扩展方式，以当前字符为中心、以当前字符和下一个字符为中心向两边拓展
int countSubstrings(string s) {
for(int i=0;s[i]!='\0';++i){
expandSubString(s,i,i);
expandSubString(s,i,i+1);
}
return cnt;
}
//中心扩散，回文字符串对称特点，两端相等
void expandSubString(string s,int start,int end){
while(start>=0 && end<s.length() && s[start]==s[end]){
start--;
end++;
cnt++;
}
}
};
回文数
- 用整数实现队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14//将整数分成左右两部分，右边那部分需要转置，然后判断这两部分是否相等。
bool isPalindrome(int x) {
if(x>=0 && x<10)return true;
if(x<0 || x%10==0)return false;
//我们将原始数字除以 10，然后给反转后的数字乘上 10
//当原始数字小于反转后的数字时，就意味着我们已经处理了一半位数的数字
int reverse=0;
while(reverse<x){
reverse=reverse*10+x%10;
x/=10;
}
return reverse==x || reverse/10==x?true:false;
}
};计数二进制子串
- 统计二进制字符串中
连续 1 和连续 0 数量相同的子字符串个数 - 对于长字符串会超出时间限制
示例：1
2
3输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。1
2
3输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
1 | |
最小覆盖子串
leetcode给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串
示例
1 | |
说明：字符串T可以有重复的字母，S必须全部包含T（意思是不光要包含字母的种类，相同字母的个数也得相等）。
解题思路
- 子串问题基本上都是滑动窗口思想
滑动窗口思想:在滑动窗口类型的问题中都会有两个指针。一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口
1 | |
