字符串系列总结
// 用到s[i + 1]做判断最好做一下边界检查
class Solution {
public:
// 程序中如何使用枚举型变量，unordered_map
unordered_map<char, int> stable = {
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D',500},
{'M',1000},
};
int romanToInt(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
if ((s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X'))
|| (s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C'))
|| (s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))) {
res += stable[s[i + 1]] - stable[s[i]];
// cout << " debug " << stable[s[i + 1]] << " " << stable[s[i]] << endl;
i++;
} else {
res += stable[s[i]];
// cout << " debug " << res << endl;
}
}
return res;
}
};
class Solution {
public:
// 。。。不会，10min
// 将第一个字符串存起来，作为基准,后续根据判断进行substr截取
// string的substr用法一定要掌握，很重要，匹配判断，重合度等等都用到
// s.substr(pos, size),起始位置+子串长度，如果pos+size超过string大小，只拷贝到字符串末尾
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
string pubString = strs[0];
for (int i = 1; i < strs.size(); i++) {
for (int j = 0; j < strs[i].size(); j++) {
if (strs[i][j] != pubString[j]) {
break;
}
}
pubString = strs[i].substr(0,j);
}
return pubString;
}
};
class Solution {
public:
// 判断括号匹配，左右匹配类型题，自己想法考虑用栈进行匹配
// 怎么匹配呢???
// hashmap???
// 对于st.empty()的判断很关键
// 基本逻辑就是碰到左括号就push进去，遇到右括号就和top对比，存在匹配的就pop出来，最后判断栈是否为空，如果完全匹配的话，栈就是空的
unordered_map<char,char> valid = {
{')','('},
{']','['},
{'}','{'},
};
stack<char> st;
bool isValid(string s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else {
if (!st.empty() && st.top() == valid[s[i]]) {
st.pop();
}
else {
st.push(s[i]);
}
}
}
return st.empty();
}
};
// class Solution {
// public:
// bool isValid(string s) {
// unordered_map<char,int> m{{'(',1},{'[',2},{'{',3},
// {')',4},{']',5},{'}',6}};
// stack<char> st;
// bool istrue=true;
// for(char c:s){
// int flag=m[c];
// if(flag>=1&&flag<=3) st.push(c);
// else if(!st.empty()&&m[st.top()]==flag-3) st.pop();
// else {istrue=false;break;}
// }
// if(!st.empty()) istrue=false;
// return istrue;
// }
// };
class Solution {
public:
// 感觉是个滑动窗口或者双指针类型的题目
// 字符串的匹配问题
// 滑动窗口怎么滑动???要弄清楚
// substr(pos, length)
// 穷举遍历法，KMP其他方法待学习
int strStr(string haystack, string needle) {
int res = -1;
// 极端case
if (needle == "") {
return 0;
}
// if (haystack == "") {
// return -1;
// }
for (int i = 0; i < haystack.size(); i++) {
// cout << i << " " <<haystack.substr(i, needle.size()) << endl;
if (needle == haystack.substr(i, needle.size())) {
res = i;
break;
}
if (i + needle.size() >= haystack.size()) {
break;
}
}
return res;
}
};
// 有点像基础的滑动窗口法
// class Solution {
// public:
// int strStr(string s, string p) {
// int n = s.size(), m = p.size();
// for(int i = 0; i <= n - m; i++){
// int j = i, k = 0;
// while(k < m and s[j] == p[k]){
// j++;
// k++;
// }
// if(k == m) return i;
// }
// return -1;
// }
// };
class Solution {
public:
// 首先想到的是从IP地址输入时学到的istringstream技巧,但是空格不止一个似乎不适用
// sstream库太好用了+++
// int lengthOfLastWord(string s) {
// istringstream is(s) ;
// string temp;
// vector<string> vec;
// while (getline(is,temp,' ')) {
// vec.emplace_back(temp);
// }
// }
// return vec[vec.size() - 1].size();
// 笨办法，字符串越界的情况不太好处理！！！
// 两个 >= 0的判断缺一不可，越界的安全保护很关键
// int lengthOfLastWord(string s) {
// // 预处理环节，先将末尾的空格都删掉
// int end = s.size() - 1;
// while (end >= 0 && s[end] == ' ') {
// end--;
// }
// if (end < 0) {
// return 0;
// }
// int start = end;
// // while (start >= 0 && s[start] != ' ') {
// while (start >= 0 && s[start] != ' ') {
// start--;
// }
// return end - start;
// }
// sstream也太优雅了吧！！！
// 对于带空格的输入，处理方法记住了
int lengthOfLastWord(string s)
{
istringstream is(s);
string res;
while(is>>res);
return res.size();
}
};
class Solution {
public:
// 对字符串进行加减乘除等运算操作的题目不少，借助carry进位逐个计算，注意位数要对其
// 位运算？？？
// 用字符串实现数字运算法则？？？
// 先用笨办法，考虑进位运算的题目都需要将进位carry单独考虑
// 然后根据每一位的相加结果进行分情况讨论
string addBinary(string a, string b) {
int LA = a.size();
int LB = b.size();
while (LA < LB) {
a = '0' + a;
LA++;
}
while (LB < LA) {
b = '0' + b;
LB++;
}
int carry = 0;
string res = a;
for (int i = a.size() - 1; i >= 0; i--) {
int num = a[i] - '0' + b[i] - '0' + carry;
if (num == 2) {
carry = 1;
res[i] = '0';
}
if (num == 3) {
carry = 1;
res[i] = '1';
}
if (num == 1) {
carry = 0;
res[i] = '1';
}
if (num == 0) {
carry = 0;
res[i] = '0';
}
}
if (carry == 1) {
res = '1' + res;
}
return res;
}
};
// 涉及到无关字符的清空问题，主要isdigit等库函数的使用
class Solution {
public:
bool isPalindrome(string s) {
string res = "";
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i])) {
res += s[i];
}
if (isalpha(s[i])) {
res += tolower(s[i]);
}
}
for (int i = 0, j = res.size() - 1; i < res.size() / 2 && j > (res.size() - 1) / 2; i++, j--) {
if (res[i] != res[j]) {
return false;
}
}
return true;
}
};
// 回文字符用一个while循环还是要优雅一些
// while (i < j) {
// if (tmp[i] != tmp[j]) return false;
// i++;
// j--;
// }
- 8-9 Excel表格，A-1，B-2，相当于string进制转换
// 正反别混淆了
class Solution {
public:
// 计算的中间字符和string类型进行+=组合操作，用static_cast<char>进行转换
// 1. string+string可---2.string+char可---3.string +char数组可
// char数组末尾\0自动添加
string convertToTitle(int columnNumber) {
string res = "";
while (columnNumber) {
// 从1开始，而不是从0开始，每一位都要从0开始算'A'
--columnNumber;
res = static_cast<char>(columnNumber % 26 + 'A') + res;
columnNumber = columnNumber / 26;
}
return res;
}
};
class Solution {
public:
// Forward solution
// 进制转换的题目肯定是forward计算模式，然后整体要乘以进制系数
int titleToNumber(string columnTitle) {
int res = 0;
for (int i = 0; i <= columnTitle.size() - 1; i++) {
int current = columnTitle[i] - 'A' + 1;
res = res * 26 + current;
}
return res;
}
};
// 字符串匹配类型的题目，首选hashmap映射方法，即unordered_map
// 有点逐个匹配的感觉，不包含匹配对就先insert
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char,char> m1;
unordered_map<char,char> m2;
if(s.size() != t.size()) {
return false;
}
for (int i = 0; i < s.size(); i++) {
char c1 = s[i];
char c2 = t[i];
if (m1.count(c1) > 0) {
if (m1[c1] != c2) {
return false;
}
} else if (m2.count(c2) > 0) {
if (m2[c2] != c1) {
return false;
}
}
else {
// m1[c1] = c2;
// m2[c2] = c1;
m1.insert({c1,c2});
m2.insert({c2,c1});
}
}
return true;
}
};
- 11 有效的字母异位词，明显的统计字符串每个字符的个数问题，同样用到hashmap,先统计完两串字符串的各个字符个数，再逐个对比
class Solution {
public:
unordered_map<char, int> mapS;
unordered_map<char, int> mapT;
bool isAnagram(string s, string t) {
if (s.size() != t.size()) {
return false;
}
for (int i = 0; i < s.size(); i++) {
mapS[s[i]]++;
mapT[t[i]]++;
}
for (char c : s) {
if (mapS[c] != mapT[c]) {
return false;
}
}
return true;
}
};
- 12 单词规律：和同构字符串异曲同工，穿了个马甲，基于空格的信息提取，用sstream高效处理
class Solution {
public:
// 对于匹配类型的题目，正反都要考虑，因此至少要两层for循环才可以
unordered_map<string, char> mapSc;
unordered_map<char, string> mapCs;
bool wordPattern(string pattern, string s) {
vector<string> vec;
// 如何将带空格的单词字符串，逐个存放到vector中，需要好好考虑一下
istringstream is(s);
string temp;
while(is >> temp){
vec.emplace_back(temp);
}
if (pattern.size() != vec.size()) {
return false;
}
for (int i = 0; i < pattern.size(); i++) {
mapCs[pattern[i]] = vec[i];
mapSc[vec[i]] = pattern[i];
}
for (int i = 0; i < pattern.size(); i++) {
if (mapCs[pattern[i]] != vec[i] || mapSc[vec[i]] != pattern[i]) {
return false;
}
}
return true;
}
};
- 13 反转字符串，堪称经典，双指针yyds,递归思想
// class Solution {
// public:
// void reverseString(vector<char>& s) { //字符串的定义
// // int left = 0, right = s.length()-1;
// int left = 0, right = s.size()-1;
// while(left < right){ //意思就是left >= right的时候停止循环
// char temp = s[left];
// s[left++] = s[right];
// s[right--] = temp;
// }
// }
// };
//直接双指针即可，可能用不到递归，用了也可以
// class Solution{
// public:
// void reverseString(vector<char> &s){
// helper(0,s.size()-1,s);
// }
// void helper(int start, int end, vector<char> &s){
// if(start >= end){
// return;
// }
// char temp = s[start];
// s[start] = s[end];
// s[end] = temp;
// helper(start+1,end-1,s);//用递归来实现这个指针移动的问题
// }
// };
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while(left < right){
swap(s[left],s[right]);
left++;
right--;
}
}
};
- 13 反转字符串中的元音字母，反转字符串的变种题目，左右同时考虑，循环层数多一点
class Solution {
public:
bool isYuanYin(char c) {
if (c == 'a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U') {
return true;
}
return false;
}
string reverseVowels(string s) {
int left = 0;
int right = s.size() - 1;
// 左右的移动应该怎么处理
while (left < right) {
if (isYuanYin(s[left])) {
if (isYuanYin(s[right])) {
if (isYuanYin(s[left]) && isYuanYin(s[right])) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
} else {
right--;
}
} else {
left++;
}
}
return s;
}
};
- 14 赎金信，判断第一个字符串是否是第二个字符串的子串问题，涉及到字符串匹配问题，考虑hashmap方法，其实可以直接将26个字母的数组直接考虑，空间换时间的概念
- 字典树！！！：简单实现，直接一层数组统计数量
class Solution {
public:
// 利用字典树，空间换时间，消耗更多的空间
bool canConstruct(string ransomNote, string magazine) {
int res[26] = {0};
for (auto& m : magazine) {
res[m - 'a']++;
}
for (auto& r : ransomNote) {
res[r - 'a']--;
if (res[r - 'a'] < 0) {
return false;
}
}
return true;
}
};
- 15 字符串的第一个唯一字符，字典树的变种应用，妙！
class Solution {
public:
// 合理利用字典序
int firstUniqChar(string s) {
int res[26] = {0};
for (auto& a : s) {
res[a - 'a']++;
}
for (int i = 0; i < s.size(); i++) {
if (res[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
};
- 16 找不同，两个字符串不同的那个元素，由于初始化数组的时候，全部都是0，因此一旦有不同的，肯定就--到负数，很好判断
class Solution {
public:
// 字典序也忒好用了吧
char findTheDifference(string s, string t) {
// char res = '';
int res[26] = {0};
for (auto& a : s) {
res[a - 'a']++;
}
for (auto& b : t) {
res[b - 'a']--;
if (res[b - 'a'] < 0) {
return b;
}
}
return NULL;
}
};
- 17 判断子序列，一看就是字典树，但是其实不是，因为匹配的情况要把子串的顺序对应上，因此需要双指针逐个匹配
class Solution {
public:
// 又是一道字典序！
// 还不太对，要把顺序对应上，有点东西
// bool isSubsequence(string s, string t) {
// int res[26] = {0};
// for (auto& c1 : t) {
// res[c1 - 'a']++;
// }
// for (auto& c2 : s) {
// res[c2 - 'a']--;
// if (res[c2 - 'a'] < 0) {
// return false;
// }
// }
// return true;
// }
// 双指针处理字符串逐个匹配的问题
// 如果是left < s.size() - 1就会有“” + “ahbgdc”判断不出来，为什么？
// 字符串类型题，空字符串的Corner case要考虑到
bool isSubsequence(string s, string t) {
int left = 0;
int right = 0;
while (left < s.size() && right < t.size()) {
if (s[left] == t[right]) {
left++;
}
right++;
}
return left == s.size();
}
};
- 18 最长回文串，双指针不可行？一定一定要注意审题，利用这些字母可以构造的最长回文串，因此，可以根据每个字母的奇偶次数来判断构造的长度
class Solution {
public:
//贪心算法需要再看看
int longestPalindrome(string s)
{
unordered_map<char, int> res;
int ans = 0;
for (auto& i : s) {
res[i]++;
}
unordered_map<char, int>::iterator it;
for (it = res.begin(); it != res.end(); it++) {
int len = it->second;
ans += len / 2 * 2;
// 确保加上中间的字母并且只加一次
if (len % 2 == 1 && ans % 2 == 0) {
ans++;
}
}
return ans;
}
};
- 19 3、5倍数问题，字符串，to_string用法
class Solution {
public:
vector<string> fizzBuzz(int n) {
vector<string> res;
for (int i = 1; i <= n; i++) {
if (i == 1 || i == 2 || i == 4) {
res.emplace_back(to_string(i));
} else if (i % 3 == 0 && i % 5 == 0) {
res.emplace_back("FizzBuzz");
} else if (i % 3 == 0) {
res.emplace_back("Fizz");
} else if (i % 5 == 0) {
res.emplace_back("Buzz");
} else {
string s = to_string(i);
res.emplace_back(s);
}
}
return res;
}
};
- 20 字符串相加问题，carry进位，先对其，while循环
class Solution {
public:
string addStrings(string num1, string num2) {
string res = "";
int n1 = num1.size() - 1;
int n2 = num2.size() - 1;
int carry = 0;
while(n1 >= 0 || n2 >= 0) {
int x = n1 >= 0 ? num1[n1] - '0' : 0;
int y = n2 >= 0 ? num2[n2] - '0' : 0;
int temp = x + y + carry;
carry = temp / 10;
res += to_string(temp % 10);
n1--;
n2--;
}
if (carry == 1) {
res += "1";
}
reverse(res.begin(), res.end());
return res;
}
};
- 21 统计字符串中的字符数，有一个小陷阱，','也算在字符中，sstream yyds
class Solution {
public:
// toupper tolower 库函数还是好用呀
// isalpha isdigit isalnum islower isupper
// 需要处理头尾问题的字符串，逆序处理看看
string licenseKeyFormatting(string s, int k) {
string res;
int count = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == '-') {
continue;
}
if (count % k == 0 && count != 0) {
res += '-';
}
res += toupper(s[i]);
count++;
}
reverse(res.begin(), res.end());
return res;
}
};
