文章目录
- 一、反转字符串中的每一个单词（leetcode 151、557）
- 二、多个字符串的最长公共前缀（leetcode 14）
- 三、字符串转整数（leetcode 8）
- 四、N位数字串删除K个数字，使剩下的数字串最小（leetcode 402）
- 五、回文子串的个数（Leetcode 647）
- 六、最长无重复字符的子串（leetcode 3）
- 七、最长回文子串（leetcode 5）
- 八、查找子串的位置（leetcode 28）
一、反转字符串中的每一个单词（leetcode 151、557）
思路：利用string流输入将原字符串按空格分割，然后去除尾部空格，整体翻转字符串，最后遍历字符串进行部分翻转。
class Solution {
public:
string reverseWords(string s) {
stringstream ss(s);
string token, str;
// 利用string流输入将原字符串按空格分割
while (ss >> token) {
str = str + token + " ";
}
// 去除尾部空格
int sz = str.size() - 1;
while (str[sz] == ' ') {
str.pop_back();
sz--;
}
// 先整体翻转
reverse(str.begin(), str.end());
for (int i = 0, j = 0; i <= str.size(); ++i){
// 部分翻转
if (i == str.size() || str[i] == ' '){
reverse(str.begin()+j, str.begin()+i);
j = i + 1;
}
}
return str;
}
};二、多个字符串的最长公共前缀（leetcode 14）
思路：假设第一个字符串为最长前缀，比较当前最长前缀和下一个字符串的公共部分，不断更新公共前缀。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res = "";
if (!strs.empty()){
// 假设第一个为最长前缀，以后再不断更新公共前缀
res = strs[0];
for (int i = 1; i < strs.size(); ++i){
// 比较当前最长前缀和下一个字符串的公共部分
int len = 0;
for (int j = 0; j < res.size() && j < strs[i].size(); ++j){
if (strs[i][j] == res[j])
len++;
else
break;
}
// 更新最长公共前缀
res = res.substr(0, len);
}
}
return res;
}
};三、字符串转整数（leetcode 8）
思路：先过滤前面的空格，然后判断正负号以及首字符是不是数字，最后判断越界。
class Solution {
public:
int myAtoi(string str) {
int i = 0, flag = 1;
// 过滤前面的空格
while (str[i] == ' ')
i++;
// 判断正负号以及首字符是不是数字
if (str[i] == '-'){
i++;
flag = -1;
}
else if (str[i] == '+'){
i++;
}
else if (!isdigit(str[i]))
return 0;
long long int res = 0;
for (; i < str.size(); ++i){
if (isdigit(str[i])){
res = res * 10 + (str[i] - '0');
// 判断整数越界
if (res > INT_MAX && flag == 1)
return INT_MAX;
if (res > INT_MAX && flag == -1)
return INT_MIN;
}
else
break;
}
return res * flag;
}
};四、N位数字串删除K个数字，使剩下的数字串最小（leetcode 402）
class Solution {
public:
string removeKdigits(string num, int k) {
// 构建一个非递减栈stkstk：从左往右遍历数字numnum，依次进栈；每个数字xx进栈前检查
// 是否比栈顶，是的话弹掉栈顶；全部数字一共有k次机会弹栈顶（相当于，最多在这一步删掉k个数字）。
stack<char> stk;
for (auto x : num) {
while (!stk.empty() && stk.top() > x && k) {
stk.pop();
k--;
}
stk.push(x);
}
// 如果k次(删数字的)机会没有用完，则弹出栈顶直到stkstk中剩余stk.size()−k个数字
while (k--)
stk.pop();
string res;
// 将stkstk倒出来再reverse，统计前导0的个数，并以此返回对应的值
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
int i = 0;
while (i < res.size() && res[i] == '0')
i++;
if (i == res.size())
return "0";
else
return string(res.begin()+i, res.end());
}
};五、回文子串的个数（Leetcode 647）
思路：以字符串中的每一个字符都当作回文串中间的位置，然后向两边扩散，每当成功匹配两个左右两个字符，结果res自增1，然后再比较下一对。注意回文字符串有奇数和偶数两种形式，如果是奇数长度，那么i位置就是中间那个字符的位置，所以我们左右两遍都从i开始遍历；如果是偶数长度的，那么i是最中间两个字符的左边那个，右边那个就是i+1，这样就能覆盖所有的情况。
class Solution {
public:
int countSubstrings(string s) {
if (s.empty()) return 0;
int res = 0;
// 分别考虑长度为奇数和偶数的情况
for (int i = 0; i < s.size(); ++i) {
countSubstringsCore(s, i, i, res);
countSubstringsCore(s, i, i+1, res);
}
return res;
}
// 以字符串中的每一个字符都当作回文串中间的位置，然后向两边扩散，每当成功匹配两个左右两个字符，
// 结果res自增1，然后再比较下一对
void countSubstringsCore(string s, int i, int j, int &res) {
while (i >= 0 && j < s.size() && s[i] == s[j]) {
--i;
++j;
++res;
}
}
};六、最长无重复字符的子串（leetcode 3）
思路：滑动窗口加哈希，即每遍历一个元素就记录下它出现的次数，如果当前元素计数大于1，则向前找到与当前字符相同的字符，i记录的是这个相同字符的下一个字符，它们之间的区间长度就是无重复子串的长度，然后不断更新最大值。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> ump;
int maxlen = 0;
for (int i = 0, j = 0; j < s.size(); ++j){
// 每遍历一个元素就记录下它出现的次数
ump[s[j]]++;
// 向前找到与当前字符相同的字符，i记录的是这个相同字符的下一个字符
while (ump[s[j]] > 1)
ump[s[i++]]--;
maxlen = max(maxlen, j - i + 1);
}
return maxlen;
}
};七、最长回文子串（leetcode 5）
思路：以某一个字符为中心向两边扩散寻找回文子串，用maxLen记录长度，如果子串是奇数，则以当前位置为中心，如果子串是偶数，则以当前位置和下一个位置共同作为中心。
class Solution {
public:
string longestPalindrome(string s) {
int start = 0, maxLen = 0;
// 以某一个字符为中心向两边扩散寻找回文子串
for (int i = 0; i < s.size(); ++i){
// 如果子串是奇数，则以当前位置为中心
longestPalindromeCore(s, i, i, start, maxLen);
// 如果子串是偶数，则以当前位置和下一个位置共同作为中心
longestPalindromeCore(s, i, i+1, start, maxLen);
}
return s.substr(start, maxLen);
}
void longestPalindromeCore(string s, int left, int right,
int &start, int &maxLen){
while (left >= 0 && right < s.size() && s[left] == s[right]){
--left;
right++;
}
// start记录回文子串开始的地方，maxLen记录长度
if (maxLen < right - left - 1){
start = left + 1;
maxLen = right - left - 1;
}
}
};八、查找子串的位置（leetcode 28）
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle == "")
return 0;
// i用于遍历haystack，j用于遍历needle，cnt用于计算相同字符的数量
int j = 0, cnt = 0;
for (int i = 0; i < haystack.size(); ++i){
if (haystack[i] == needle[j]){
cnt++;
// 如果j遍历到头了则说明needle是haystack的子串
if (j == needle.size() - 1)
return i-cnt+1;
j++;
}
// 重置i，j，cnt
else {
i -= cnt;
j = 0;
cnt = 0;
}
}
return -1;
}
};