哈喽大家好，我是雨墨，小老弟又来了，这是小老弟的第二篇博客，记录小老弟我刷字符串类型的leetcode 题目的笔记。每日更新3道，直至完成目标~
话不多说，咱们开始正题~~
传送门：https://leetcode-cn.com/problems/reverse-string/
我的题解题目描述
编写一个函数，将字符串反转过来，要求必须原地修改字符串。
样例
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
算法
（双指针） O ( n ) O(n) O(n)
算法描述：使用两个指针，一个往后走，一个往前走，交换两个指针所指的元素，直到两个指针相遇，整个字符串就反转过来了。
class Solution {
public:
void reverseString(vector& s) {
int len = s.size();
for (int head = 0, tail = len - 1; head < tail; ++head, --tail)
swap(s[head], s[tail]);
}
};
leetcode 541 反转字符串Ⅱ（换一个玩法）
题目链接
传送门：https://leetcode-cn.com/problems/reverse-string-ii/
我的题解题目描述
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
样例
输入：s = "abcdefg", k = 2 输出："bacdfeg"
算法
（模拟） O ( n ) O(n) O(n)
题目要求要在每2k个字符中选择前k个字符反转，那每次i += 2 * k就可以了，再多考虑数组长度满不满足大于 k 的情况就可以了。
class Solution {
public:
string reverseStr(string s, int k) {
int len = s.size();
for (int i = 0; i < len; i += 2 * k) {
int l = i, r = min(l + k, len);
reverse(s.begin() + l, s.begin() + r);
}
return s;
}
};
剑指offer 05 替换空格
题目链接
传送门：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/submissions/
我的题解题目描述
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
样例
输入：s = "We are happy." 输出："We%20are%20happy."
算法1
（复制+替换） O ( n ) O(n) O(n)
将原字符串的内容拷贝到新的字符串内，如果遇到 ‘ ’， 就向新的字符串中添加%20。但是这种空间复杂度也是 O ( n ) O(n) O(n)。
class Solution {
public:
string replaceSpace(string s) {
int len = s.size();
string str;
for (int i = 0; i < len; ++i) {
if (s[i] != ' ')
str += s[i];
else str += "%20";
}
return str;
}
};
算法2
（双指针） O ( n ) O(n) O(n)
先计算将空格替换之后新的字符串会变成多大的长度，然后对原字符串resize这个新的长度，一个指针i从原数组的尾部向头走，一个指针j从新的字符串尾部向头走，如果没有遇到空格，则直接s[j--] = s[i]，否则将空格转换成%20。这样空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution {
public:
string replaceSpace(string s) {
int len = s.size(), new_len = 0;
for (const auto& str : s) {
if (str == ' ') new_len += 3;
else new_len ++;
}
s.resize(new_len);
for (int i = len - 1, j = new_len - 1; ~i; --i) {
if (s[i] != ' ') s[j--] = s[i];
else {
s[j--] = '0';
s[j--] = '2';
s[j--] = '%';
}
}
return s;
}
};
leetcode 151 翻转字符串里的单词（好题，字符串重点题）
题目链接
传送门：https://leetcode-cn.com/problems/reverse-words-in-a-string/
我的题解题目描述
给定一个字符串，逐个反转所有单词。
说明：
- 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
- 翻转后单词间应当仅用一个空格分隔。
- 翻转后的字符串中不应包含额外的空格。
样例
输入：s = " hello world " 输出："world hello"
算法
（拆分问题） O ( n ) O(n) O(n)
这道题乍一看确实很难想，没办法一步到位，那就只好把这道题拆解逐个击破，这也是一种很重要的思想。
算法描述：
- 可以先将这个字符串全部反转
- 然后再逐个反转每个单题且保证每个单题之后以空格间隔，删去不必要的空格
- 更多实现细节见代码
class Solution {
public:
string reverseWords(string s) {
int len = s.size();
reverse(s.begin(), s.end()); // 先将整个字符串翻转
int beg_of_word = 0; // 每个单词的开头
for (int slowIndex = 0; slowIndex < len; ++slowIndex) {
if (s[slowIndex] == ' ') continue; // 找到第一个不是 ' ' 的字符
int fastIndex = slowIndex, end_of_word = beg_of_word;
// 寻找每一个完整的单词并用其覆盖原字符串
while (s[fastIndex] != ' ' && fastIndex < len) s[end_of_word++] = s[fastIndex++];
// 翻转每个单词
reverse(s.begin() + beg_of_word, s.begin() + end_of_word);
s[end_of_word++] = ' '; // 在每个单词末尾添加 ' '
beg_of_word = end_of_word, slowIndex = fastIndex; // 更新
}
// 只要出现一个单词，那在其末尾一定会添加一个 ' '
if (beg_of_word) --beg_of_word;
// 将末尾多余的 ' ' 删去
s.erase(s.begin() + beg_of_word, s.end());
return s;
}
};
剑指offer 58 左旋转字符串
题目链接
传送门：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
我的题解题目描述
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
样例
输入: s = "abcdefg", k = 2 输出: "cdefgab"
算法
（思维题） O ( n ) O(n) O(n)
这道题我是把难度调大了的，也就是在 O ( 1 ) O(1) O(1)的空间复杂度下使得字符串左旋转。遇到问题一步不能到位，那就把它拆解，先reverse整个字符串一遍，将后 n 个字符串reverse一遍，再将前面的字符串reverse一遍，即可得到答案。
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.end());
reverse(s.end() - n, s.end());
reverse(s.begin(), s.begin() + s.size() - n);
return s;
}
};
leetcode 28 实现 strStr()
题目链接
传送门：https://leetcode-cn.com/problems/implement-strstr/
我的题解题目描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
样例
输入：haystack = "hello", needle = "ll" 输出：2
算法1
（暴力） O ( n m ) O(nm) O(nm)
暴力非常不可取，耗时非常高。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
if (haystack.empty()) return -1;
int len1 = haystack.size(), len2 = needle.size();
int k = 0;
int i = 0;
for (; i < len1; ++i) {
if (haystack[i] != needle[k]) continue;
int j = i;
while (j < len1 && haystack[j] == needle[k]) ++j, ++k;
if (k != len2) k = 0;
else break;
}
if (k != len2) return -1;
else return i;
}
};
算法2
（KMP) O ( n ) O(n) O(n)
快多了，这才是字符串匹配的正确打开方式 —– KMP，如果这次没有学会，那么就一定没有学会。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
int len1 = haystack.size(), len2 = needle.size();
haystack = ' ' + haystack, needle = ' ' + needle;
// 初始化 next[1] = 0
vector next(len2 + 1);
// 求 next 数组过程
// j 表示前缀末尾，也表示前后缀最大相等长度，i 表示后缀末尾
for (int i = 2, j = 0; i <= len2; ++i) {
// 前后缀不相同
while (j && needle[i] != needle[j + 1]) j = next[j];
// 前后缀相同
if (needle[i] == needle[j + 1]) ++j;
next[i] = j;
}
// 匹配过程
for (int i = 1, j = 0; i <= len1; ++i) {
while (j && haystack[i] != needle[j + 1]) j = next[j];
if (haystack[i] == needle[j + 1]) ++j;
if (j == len2) return i - len2;
}
return -1;
}
};
leetcode 459 重复的子字符串
题目链接
传送门：https://leetcode-cn.com/problems/repeated-substring-pattern/
我的题解题目描述
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
样例
输入: "abab" 输出: True
算法
这道题应该被设置为 hard ，因为它本身是非常麻烦的，推导真的很麻烦，但是如果知道以下两个 KMP 的性质，就变得 easy 了。
- n - next[n] 是字符串的最小周期
- 如果周期可以整除 n ，那么最小周期的长度一定是其他所有周期的约数
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int len = s.size();
s = ' ' + s;
vector next(len + 1);
for (int i = 2, j = 0; i <= len; ++i) {
while (j && s[i] != s[j + 1]) j = next[j];
if (s[i] == s[j + 1]) ++j;
next[i] = j;
}
int t = len - next[len];
return t < len && len % t == 0;
}
};
leetcode 13 罗马数字转整数
题目链接
传送门：https://leetcode-cn.com/problems/roman-to-integer/
我的题解题目描述
已知罗马数字包含如下七种字符，每一个字符对应的数值为
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
通常情况下，罗马数字小的数在大的数字的右边，但也有特例：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
样例
输入: "III" 输出: 3
输入: "IV" 输出: 4
输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3
算法
（模拟） O ( n ) O(n) O(n)
根据题意然后再模拟一遍，得到这样的结论：如果前一个数大于后一个数，那么结果就加上这个数，如果小于后一个数，那么结果就减去这个数。
class Solution {
public:
int romanToInt(string s) {
unordered_map hash;
hash['I'] = 1,
hash['V'] = 5,
hash['X'] = 10,
hash['L'] = 50,
hash['C'] = 100,
hash['D'] = 500,
hash['M'] = 1000;
int res = 0, len = s.size();
for (int i = 0; i < len; ++i) {
if (i + 1 < len && hash[s[i]] < hash[s[i + 1]])
res -= hash[s[i]];
else
res += hash[s[i]];
}
return res;
}
};
leetcode 67 二进制求和
题目链接
传送门：https://leetcode-cn.com/problems/add-binary/
我的题解题目描述
给定两个二进制数，算出他俩之和。
样例
输入: a = "11", b = "1" 输出: "100"
算法
（高精度加法） O ( n ) O(n) O(n)
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string res;
int lenA = a.size(), lenB = b.size();
for (int i = 0, t = 0; i < lenA || i < lenB || t; ++i) {
if (i < lenA) t += a[i] - '0';
if (i < lenB) t += b[i] - '0';
res += to_string(t % 2);
t /= 2;
}
reverse(res.begin(), res.end());
return res;
}
};
leetcode 434 字符串中的单词数
题目链接
传送门：https://leetcode-cn.com/problems/number-of-segments-in-a-string/
我的题解题目描述
统计字符串中的单词个数。
样例
输入: "Hello, my name is John" 输出: 5
算法1
（双指针） O ( n ) O(n) O(n)
遇到单词遍历一遍，然后给结果加上1.
class Solution {
public:
int countSegments(string s) {
int len = s.size();
int res = 0;
for (int i = 0; i < len; ++i) {
if (s[i] == ' ') continue;
int j = i + 1;
while (j < len && s[j] != ' ') ++j;
++res;
i = j - 1;
}
return res;
}
};
算法2
（规律） O ( n ) O(n) O(n)
这个办法很巧妙，它的意思是如果碰上空格，且它的前面的那个数不是空格，那么就是一个单词，因此需要在原字符串末尾加上一个空格。
class Solution {
public:
int countSegments(string s) {
int ans = 0;
s += ' ';
int len = s.size();
for (int i = 1; i <= len; ++i) {
if (s[i] == ' ' && s[i - 1] != ' ')
++ans;
}
return ans;
}
};
