替换空格
原地算法
class Solution {
public:
string replaceSpaces(string &str) {
int len = 0;
for (auto c: str) {
if (c == ' ') len += 3;
else len ++;
}
int l = str.size() - 1;
str.resize(len);
for (int i = l, j = len - 1; i >= 0; i --) {
if (str[i] == ' ') {
str[j --] = '0';
str[j --] = '2';
str[j --] = '%';
}
else str[j --] = str[i];
}
return str;
}
};
最长不含重复字符的子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> heap;
int res = 0;
for (int i = 0, j = 0; i < s.size(); i ++) {
heap[s[i]] ++;
while (heap[s[i]] > 1) heap[s[j ++]] --;
res = max(res, i - j + 1);
}
return res;
}
};
翻转单词顺序
翻转整个字符串后, 再反转每个单词即可.
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i ++) {
int j = i + 1;
while (j < s.size() && s[j] != ' ') j ++;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
return s;
}
};
左旋转字符串
先翻转整个字符串, 然后分别翻转左旋部分和非左旋部分即可.
class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.begin() + str.size() - n);
reverse(str.begin() + str.size() - n, str.end());
return str;
}
};
串连所有单词的子串
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
暴力做法
首先用一个哈希表hash预处理每个单词出现的次数.
之后枚举给定字符串s的每一个起点, 对于每一个起点, 从后看每一个单词, 然后用另一个哈希表cur_hash处理遍历过程中每一个单词出现的次数, 假设现在遍历到的单词是cur:
- 如果
cur_hash[cur] <= hash[cur], 正常, 继续遍历 - 如果
cur_hash[cur] > hash[cur]或者cur在hash中根本没有出现: 那么不符合题意, 当前枚举的s起点是无效的.
之后, 如果遍历单词的个数达到了所有单词的数量, 那么就成功了.
时间复杂度是$O(nm)$, 其中$n$是字符串s的长度, $m$是单词的个数.
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> hash;
vector<int> ans;
int n = s.size(), m = words.size(), len = words[0].size();
/* 统计每个单词出现的次数 */
for (auto word: words) hash[word] ++;
for (int i = 0; i <= n - m * len; i ++) {
unordered_map<string, int> cur_hash;
int cnt = 0;
for (int j = i; j <= n - len; j += len) {
string cur = s.substr(j, len);
/* 如果cur没有在words中出现过, 直接失败 */
if (!hash.count(cur)) break;
cur_hash[cur] ++;
if (cur_hash[cur] > hash[cur]) break;
else if (cur_hash[cur] <= hash[cur]) cnt ++;
if (cnt == words.size()) {
ans.push_back(i);
break;
}
}
}
return ans;
}
};
双指针算法
首先, 还是用哈希表预处理每一个单词出现的次数.
假设每一个单词的长度是len.
之后, 对于给定的字符串s, 将它切分成一段一段, 每一段长度是len, 这些段可以组成一个原串的单词序列, 不同的序列一共有len中, 它们的起点分别是0, 1, 2, ..., len - 1, 其中以len为起点的序列和以0为起点的序列是等价的, 因为是子串关系.
之后, 遍历每一个从s中得到的序列, 用双指针算法得到由words中单词组成的连续的最长的序列, 看这个序列中的单词个数是否是m, 如果是m, 那就成功, 这个双指针算法可以参考LeetCode 3
一共有len个序列, 枚举每个序列需要$O(n)$的时间复杂度, 那么总的时间复杂度就是$O(nlen)$
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> hash;
vector<int> ans;
int n = s.size(), m = words.size(), len = words[0].size();
/* 统计每个单词出现的次数 */
for (auto word: words) hash[word] ++;
for (int i = 0; i < len; i ++) {
vector<string> ws;
int j = i;
while (j + len - 1 < s.size()) {
ws.push_back(s.substr(j, len));
j += len;
}
unordered_map<string, int> cur_hash;
for (int p = 0, q = 0; p < ws.size(); p ++) {
cur_hash[ws[p]] ++;
while (cur_hash[ws[p]] > hash[ws[p]]) cur_hash[ws[q ++]] --;
if (p - q + 1 == m) ans.push_back(i + q * len);
}
}
return ans;
}
};
字符串最长公共前缀
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if (strs.empty()) return res;
for (int i = 0; ; i ++) {
if (i >= strs[0].size()) return res;
char c = strs[0][i];
for (auto &str: strs) {
if (i >= str.size() || str[i] != c) return res;
}
res += c;
}
return res;
}
};
字符串转换整数
class Solution {
public:
int myAtoi(string s) {
int k = 0;
while (k < s.size() && s[k] == ' ') k ++;
if (k == s.size()) return 0;
bool neg = false;
if (s[k] == '-') neg = true;
if (s[k] == '-' || s[k] == '+') k ++;
int res = 0;
while (k < s.size() && s[k] >= '0' && s[k] <= '9') {
int x = s[k] - '0';
/* 10 * res + x有可能溢出, 所以要写成这种形式 */
/* 这里为什么不写>=, 考虑2147483646, 最后一位没遍历到的时候, res是214748364, (INT_MAX - x) / 10也是这个结果, 如果写大于等于, 那么直接就返回了INT_MAX, 结果不对, 下面同理 */
if (!neg && res > (INT_MAX - x) / 10) return INT_MAX;
if (neg && -res < (INT_MIN + x) / 10) return INT_MIN;
/* 为什么要特判? 首先-res * 10 - x 如果溢出, 上面直接就返回了INT_MIN, 因此这里是不会溢出的, 其次, 如果结果是-2147483648(INT_MIN), 那么上面是不会返回INT_MIN的, 需要特判, res不能存储2147483648, 因为正数最多到2147483647, 所以需要在这里特判 */
if (neg && -res * 10 - x == INT_MIN) return INT_MIN;
res = res * 10 + x;
k ++;
}
return (neg) ? -res : res;
}
};
字符串前缀哈希
按照字符的ASCII码, 可以将字符串映射到一个$P$进制的数, 可以实现在$O(1)$的时间内判断字符串的两个子串是否相等.
#include <iostream>
using namespace std;
const int N = 100010, P = 131;
typedef unsigned long long ULL;
ULL h[N], p[N];
char str[N];
int n, m;
ULL get(int l, int r) {
return h[r] - h[l - 1] * (r - l + 1);
}
int main() {
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++) {
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m --) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
外观数列
典型的双指针算法.
class Solution {
public:
string countAndSay(int n) {
if (n == 1) return "1";
string prev = countAndSay(n - 1);
vector<pair<int, int>> group;
string res = "";
for (int i = 0; i < prev.size(); i ++) {
int j = i + 1;
while (j < prev.size() && prev[j] == prev[i]) j ++;
int cnt = j - i;
res += cnt + '0';
res += prev[i];
i = j - 1;
}
return res;
}
};
字母异位词分组
如果两个单词在同一个组, 那么它们排序后的字符串相同.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hashs;
for (auto &str: strs) {
string nstr = str;
sort(nstr.begin(), nstr.end());
hashs[nstr].push_back(str);
}
vector<vector<string>> ans;
/* 遍历哈希表的方式 */
for (auto &item: hashs) ans.push_back(item.second);
return ans;
}
};