- 字符串类总结
- 机器能否返回原点 (
easy) - 反转字符串 (
easy) - 反转字符串里的单词 (
medium反转) - 反转字符串中的单词III (
easy) - 罗马数字转整数 (
easy) - 报数 (
easy迭代) - 验证回文串 (
easy双指针) - 实现strStr() (
easy) - 字符串中的第一个唯一字符 (
easy哈希) - 最长公共前缀 (
easy字典树水平扫描) - 有效的字母异位词 (
easy哈希) - 字母异位词分组 (
medium哈希) - 字符串相乘 (
medium数学) - 字符串转整数(atoi) (
medium数学) - 滑动窗口
- 字符串的排列 (
medium哈希) - 最小覆盖子串 (
hard哈希) - 找到字符串中所有字母异位词 (
mediumhash) - 串联所有单词的子串 (
hardhash)
- 字符串的排列 (
- 机器能否返回原点 (
题解中的时间复杂度分析有误，应该是o(n) （n为字符串s的长度）
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (words.empty()) return res;
int w_len = words[0].size(), n = words.size(), len = s.size();
unordered_map<string, int> mp;
unordered_map<int, string> mp2;
for (const auto& word : words) {
++mp[word];
}
for (int i = 0; i <= len - w_len; ++i) {
mp2[i] = s.substr(i, w_len);
}
for (int i = 0; i < w_len && i <= len - w_len * n; ++i) {
unordered_map<string, int> mp1;
int l = i;
int r = i;
int valid = 0;
while (r <= len - w_len) {
auto tmp = mp2[r];
if (mp.find(tmp) == mp.end()) {
l = r + w_len;
r = l;
mp1.clear();
valid = 0;
continue;
} else {
++mp1[tmp];
if (mp1[tmp] == mp[tmp]) {
++valid;
}
if (mp1[tmp] > mp[tmp]) {
r += w_len;
while (l < r && mp1[tmp] > mp[tmp]) {
const auto& tmp1 = mp2[l];
if (tmp1 != tmp && mp[tmp1] == mp1[tmp1]) {
--valid;
}
--mp1[tmp1];
// if (tmp == tmp1 && mp[tmp1] == mp1[tmp1]) {
// ++valid;
// }
if (mp1[tmp1] == 0) {
mp1.erase(tmp1);
}
l += w_len;
}
continue;
}
}
r += w_len;
while (r - l == w_len * n) {
if (valid == mp.size()) {
res.push_back(l);
}
const auto& tmp1 = mp2[l];
if (mp.find(tmp1) != mp.end() && mp[tmp1] == mp1[tmp1]) {
--valid;
}
--mp1[tmp1];
if (mp1[tmp1] == 0) {
mp1.erase(tmp1);
}
l += w_len;
}
}
}
return res;
}
unordered_map<string, int> mp;
unordered_map<int, string> mp1;
};class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> window, need;
for (const char& ch : p) {
need[ch]++;
}
int l = 0, r = 0;
int valid = 0;
vector<int> res;
while (r < s.size()) {
char c = s[r];
if (need.find(c) != need.end()) {
window[c]++;
if (need[c] == window[c]) {
valid++;
}
}
while (r - l + 1 > p.size()) {
char a = s[l];
if (need.find(a) != need.end()) {
if (window[a] == need[a]) {
valid--;
}
window[a]--;
}
l++;
}
if (valid == need.size()) {
res.push_back(l);
}
++r;
}
return res;
}
};在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。
示例 1:
输入: "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:
输入: "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
正常逻辑处理
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public:
bool judgeCircle(string moves) {
int v = 0;
int h = 0;
for(auto begin : moves)
{
switch(begin)
{
case 'U':v++;break;
case 'D':v--;break;
case 'L':h--;break;
case 'R':h++;break;
}
}
if(0 == v && 0 == h)
return true;
return false;
}
};编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
双指针
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public:
string reverseString(string s) {
int len = s.size();
if(len == 0 || len == 1)
return s;
int l = 0;
int r = len - 1;
while(l < r)
{
swap(s[l++],s[r--]);
}
return s;
}
};给定一个字符串，逐个翻转字符串中的每个单词。
示例:
输入: "the sky is blue",
输出: "blue is sky the".
说明:
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。
首先清除字符串s头和尾的所有空格，然后反转整个字符串，最后反转字符串中的每个单词，这样得到的单词序列满足要求。但是由于字符串单词之间只能保留一个空格，因此反转之后需要把字符串s拷贝到另一个字符串s1，然后s清空，之后每反转一次单词，将反转的单词加到s1尾部，同时加上一个空格，直到最后一个反转的单词，就不需要加空格了。
注意：边界条件很多
- 单词间的空格要减到一个，因此需要另一块内存来存放消除掉空格的字符串
- s首尾都有可能有空格，所以刚开始需要过滤掉收尾的空格
- s可能全都是空格，这种情况输出空字符串
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public:
void reverseWords(string &s) {
if(s.empty()) return;
while(!s.empty() && s.back() == ' ')
s.pop_back();
if(s.empty()) return;
reverse(s.begin(),s.end());
while(!s.empty() && s.back() == ' ')
s.pop_back();
string s1(s);
s.clear();
int len = s1.size();
int l = 0,r = 0;
while(r < len)
{
if(s1[r] == ' ')
{
reverse(s1.begin() + l,s1.begin() + r);
copy(s1.begin() + l,s1.begin() + r + 1,back_inserter(s));
while(s1[r] == ' ' && r < len) r++;
l = r;
}
r++;
}
reverse(s1.begin() + l,s1.begin() + r);
copy(s1.begin() + l,s1.begin() + r,back_inserter(s));
}
};给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
定义两个指针l和r，r用来遍历字符串，每当r遇到空格就反转l~r之间的单词，然后r往后移动到下一个非空格的位置，同时令l = r。这样遍历完整个字符串，就能将字符串的单词反转。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public:
string reverseWords(string s) {
if(s.empty())
return s;
int l = 0,r = 0;
int len = s.size();
while(r < len)
{
if(s[r] == ' ')
{
reverse(s.begin()+l,s.begin()+r);
while(s[++r] == ' ');
l = r;
}
else
r++;
}
reverse(s.begin()+l,s.begin()+r);
return s;
}
};罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1：
输入: "IX"
输出: 9
示例 2:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 3:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
分类讨论，将情况考虑清楚即可。
注意：三种特殊情况的处理
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
for idx,ch in enumerate(s):
if ch == 'I':
res += 1
elif ch == 'V':
res += 5
if idx > 0 and s[idx-1] == 'I':
res -= 2
elif ch == 'X':
res += 10
if idx > 0 and s[idx-1] == 'I':
res -= 2
elif ch == 'L':
res += 50
if idx > 0 and s[idx-1] == 'X':
res -= 20
elif ch == 'C':
res += 100
if idx > 0 and s[idx-1] == 'X':
res -= 20
elif ch == 'D':
res += 500
if idx > 0 and s[idx-1] == 'C':
res -= 200
elif ch == 'M':
res += 1000
if idx > 0 and s[idx-1] == 'C':
res -= 200
return res报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
示例 2:
输入: 4
输出: "1211"
假设第n项和第n-1项的递推关系为 an = f(an-1),定义一个函数getStr来代替函数f，初始化数列首项"1"和"11"，根据函数getStr推导出第n项即可。
class Solution {
public:
string getStr(string str)
{
string res;
int num = 1;
int i = 0;
int len = str.size();
while(i < len)
{
if(i < len - 1)
{
if(str[i] != str[i + 1])
{
res += to_string(num) + str[i];
i++;
}
else
{
char s = str[i];
i++;
while(i < len && str[i] == s)
{
num++;
i++;
}
res += to_string(num) + s;
num = 1;
}
}
else if(i == len - 1)
{
res += to_string(num) + str[i];
i++;
}
}
return res;
}
string countAndSay(int n) {
if(n == 1) return string("1");
if(n == 2) return string("11");
string res = "11";
for(int i=2;i<n;i++)
{
res = getStr(res);
}
return res;
}
};给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
将字符串s中不是字母和数字的字符（包括空格）清除掉，然后定义两个指针l和r分别位于字符串的头和尾，同时向中间移动，移动的同时比较s[l]和s[r]，一旦发现它们不是相同字符并且不是同一字母的大小写，则判断s不是回文串。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public:
bool isPalindrome(string s) {
int len=s.size();
if(len == 0)
return true;
int index = 0;
for(int i=0;i<len;i++)
{
if((s[i] >= 'a' && s[i] <= 'z')
|| (s[i] >= 'A' && s[i] <= 'Z')
||(s[i] >= '0' & s[i] <= '9'))
s[index++] = s[i];
}
while(s.size() > index)
s.pop_back();
int l = 0;
int r = s.size() - 1;
while(l < r)
{
if(s[l] != s[r])
{
if(s[l] >= 'A' && s[r] >= 'A')
{
if(abs(s[l] - s[r]) != 32)
return false;
}
else
return false;
}
l++;
r--;
}
return true;
}
};实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
设needle的首字母为start,遍历haystack字符串，一旦找到和start相同的字符haystack[i]，就从haystack的该位置开始和needle一一比较，判断是否相等。
- 时间复杂度：O(mn)
- 空间复杂度：O(1)
class Solution {
public:
bool is_ok(int idx1,int idx2,const string& str1,const string& str2)
{
while(idx1 < str1.size() && idx2 < str2.size())
{
if(str1[idx1++] != str2[idx2++])
return false;
}
if(idx1 != str1.size())
return false;
return true;
}
int strStr(string haystack, string needle) {
int len1 = haystack.size();
int len2 = needle.size();
if(len2 == 0)
return 0;
if(len1 == 0)
return -1;
int start = needle.front();
for(int i = 0;i < len1;i++)
{
if(i+len2 > len1)
return -1;
if(haystack[i] == start)
{
if(is_ok(0,i,needle,haystack))
return i;
}
}
return -1;
}
};给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例 1:
s = "leetcode"
返回 0.
示例 2:
s = "loveleetcode",
返回 2.
注意：您可以假定该字符串只包含小写字母。
建立一个hash表，统计字符串中每个字符的次数，然后遍历一次字符串，找到第一个出现一次的字符即可。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
mp = dict()
for ch in s:
mp[ch] = 0
for ch in s:
mp[ch] += 1
for idx,ch in enumerate(s):
if mp[ch] == 1:
return idx
return -1
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
将字符串数组想象成元素不等长的二维矩阵，按照逐列的顺序遍历这个矩阵，同时比较同一列中每一行的字符是否相同：
- 如果都相同，将这个字符加入结果；
- 否则，直接返回结果。
最坏情况下，字符串数组所有的字符串都相同，假设是n个长度是m的字符串，此时
- 时间复杂度：O(mn)
- 空间复杂度：O(1)
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
string res("");
for(int i=0;i<strs[0].size();i++)
{
char ch = strs[0][i];
for(int j=1;j<strs.size();j++)
{
if(i >= strs[j].size() || ch != strs[j][i])
return res;
}
res += ch;
}
return res;
}
};建立一个字典树，将字符串数组的所有字符串加入字典书中，然后从字典树的根部出发，找到最长公共前缀。
最坏情况下，字符串数组所有的字符串都相同，假设是n个长度是m的字符串，此时
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
struct node
{
int path;
int tail;
node* next[26];
node()
{
path = 0;
tail = 0;
for(int i=0;i<26;i++)
next[i] = nullptr;
}
};
class Trie
{
public:
Trie()
{
root = new node();
}
void insert(string word)
{
node* p = root;
for(int i=0;i<word.size();i++)
{
p->path++;
int s = word[i] - 'a';
if(!p->next[s])
p->next[s] = new node();
p=p->next[s];
}
p->path++;
p->tail++;
}
string getPrefix(int n)
{
string res;
node* p = root;
bool flag = false;
while(p && p->path == n)
{
int i;
for(i=0;i<26;i++)
{
if(p->next[i] && p->next[i]->path == n)
{
res.push_back('a' + i);
flag = true;
break;
}
}
if(flag)
p = p->next[i];
else
break;
flag = false;
}
return res;
}
private:
node* root;
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int len = strs.size();
Trie tr;
for(auto s : strs)
tr.insert(s);
return tr.getPrefix(len);
}
};给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
首先判断s和t的长度是否一样，如果不一样，那么就不是字母异位词。如果长度一样，利用unordered_map作为哈希表，统计字符串s中字符的个数，然后遍历字符串t的每个元素ch，如果mp[ch] >= 0，则--mp[ch]，否则的话，mp[ch] < 0，那么就不是字母异位词。
设s长度为m，t长度为n
- 时间复杂度：O(m + n)
- 空间复杂度：O(max(m,n))
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) return false;
unordered_map<char,int> mp;
for(auto ch : s) ++mp[ch];
for(auto ch : t)
{
if(mp[ch] <= 0) return false;
else --mp[ch];
}
return true;
}
};给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
利用hash表，具体思路：
- 新建哈希表
mp，它的key为multiset<char>，value为vector<string>; - 遍历字符串数组里的每个字符串，把每个字符串的字符插入结构为
multiset的st中，在其中字母会自动排序（时间复杂度 log n）。因此，排序后的st作为key,对应的字符串value，添加到mp中。 - 最后将
mp的所有value按照key分组添加到结果中。
设strs中字符串元素的平均长度k，strs的长度n，那么
- 时间复杂度：O(n klog k)
- 空间复杂度：O(nk)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
int len = strs.size();
if(len == 0) return vector<vector<string>>();
vector<vector<string>> res;
map<multiset<char>,vector<string>> mp;
for(int i=0;i<len;i++)
{
multiset<char> st;
for(int j=0;j<strs[i].size();j++)
st.insert(strs[i][j]);
mp[st].push_back(strs[i]);
}
for(auto s : mp)
res.push_back(s.second);
return res;
}
};因为字母都是小写字母，可以利用计数来排序
时间复杂度：O(nk)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string s : strs) {
mp[strSort(s)].push_back(s);
}
vector<vector<string>> anagrams;
for (auto p : mp) {
anagrams.push_back(p.second);
}
return anagrams;
}
private:
string strSort(string s) {
int counter[26] = {0};
for (char c : s) {
counter[c - 'a']++;
}
string t;
for (int c = 0; c < 26; c++) {
t += string(counter[c], c + 'a');
}
return t;
}
};给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1和num2的长度小于110。num1和num2只包含数字 0-9。num1和num2均不以零开头，除非是数字 0 本身。- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
对于大数相乘需要用字符串来模拟，两个数字相乘的结果是错位相加得到的，将错位相加的结果放入一维数组mul中，然后按照进位，将mul的每一个元素变成一位，就得到了最终结果。详见博客
设相乘的两个数字位数分别是m和n，那么
- 时间复杂度：O(mn)
- 空间复杂度：O(m + n)
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
if(len1 == 0 || len2 == 0)
return string();
if(num1 == "0" || num2 == "0")
return "0";
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
string res;
vector<int> mul(len1+len2-1,0);
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
mul[i+j] += (num1[i] - '0')*(num2[j] - '0');
}
}
int over = 0;
int len3 = mul.size();
for(int i=0;i<len3;i++)
{
int tmp = mul[i] + over;
int val = tmp%10;
over = tmp/10;
res.push_back(val + '0');
}
if(over > 0)
res.push_back(over + '0');
reverse(res.begin(),res.end());
return res;
}
};请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN 。
考察字符串转换成数字问题，对于字符串中对应的每一位数字按照迭代相加得到结果。
注意边界：数字大于INT_MAX或者小于INIT_MIN溢出的情况。处理方法：提前预判，在就计算下一轮数字之前，将当前sum和INT_MIN/10以及INT_MAX/10比较。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public:
int myAtoi(string str) {
if(str.empty())
return 0;
int sum = 0;
int symbol = 1;
int i = 0;
while(str[i] == ' ')
i++;
if(str[i] == '-' || str[i] == '+')
{
symbol = (str[i] == '+') ? 1 : -1;
i++;
}
while(i < str.size() && str[i] >= '0' && str[i] <= '9')
{
if(sum > INT_MAX / 10 || (sum == INT_MAX / 10 && str[i] > '6'))
return INT_MAX;
if(sum < INT_MIN / 10 || (sum == INT_MIN / 10 && str[i] > '7'))
return INT_MIN;
sum = sum * 10 + (str[i] - '0') * symbol;
i++;
}
return sum;
}
};给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
思路：滑动窗口 + hash表
首先使用一个map统计字符串t中每个字符出现的次数，要解决这个问题，就是要找到s的子串中，包含所有map中的字符，并且字符出现次数大于等于该字符在map中计数的子串。满足要求的最短子串就是答案。
使用一个变量cnt记录字符串t的长度，这个长度将用于判断滑动窗口中是否包含所有t中的字符。使用一个变量min表示满足要求的子串的最小长度，一个变量start表示该子串的起始下标。我们按如下假设遍历s进行处理：
- 当遇到一个
t中的字符时，将其map中的计数减1（可能小于0，因为s中可能包含多个这样的字符），同时判断：- 如果减1之前计数大于0，说明这个字符应该含入滑动窗口中，此时
cnt减1； - 如果减1之前计数小于等于0，说明这个字符在s中出现了很多次，此时
cnt不变；
- 如果减1之前计数大于0，说明这个字符应该含入滑动窗口中，此时
- 当遇到一个不在t中出现的字符时，跳过。
显然，当cnt为0时，我们找到了一个满足要求的滑动窗口，这个滑动窗口中，包含了所有t中的字符。因此，我们比较这个滑动窗口的长度与min的值，如果小于min，说明找到了一个新的滑动窗口，因此更新min和start。
既然当cnt为0时，找到了一个满足要求的滑动窗口，那么下一步该怎么做？注意到我们找到的第一个滑动窗口是位于最左边，此时map中一些字符的计数可能小于0，因为t中的某些字符在该滑动窗口中出现了很多次。此时我们从左边开始释放字符，目的是希望在右边能找到一个新的相同字符，从而得到一个新的满足要求的滑动窗口。但是从左边开始，第一个在t中的字符可能是一个冗余的字符（即map中的计数小于0），因此释放了这个字符后，滑动窗口中还是拥有满足条件的字符，那么此时回收应该只增加其在map中的计数，但是不需要从右边开始滑动窗口（即不增加cnt）。因此，只有当遇到一个在t中，并且map中计数为0的字符，才需要将cnt加1。因为map计数为0说明滑动窗口中这个字符的数量“恰好”满足要求，因此可以开始从右边滑动窗口，也就是说，我们还应该从右边找到1个这样字符，使得map中其计数递减后，又变为0。
设字符串s的长度为m,字符串t的长度为n，那么：
- 时间复杂度：O(m)
- 空间复杂度：O(n)
class Solution {
public:
string minWindow(string s, string t) {
map<char,int> mp;
for(auto ch : t)
{
++mp[ch];
}
int m = s.size();
int n = t.size();
if(m < n) return "";
int cnt = n;
int start = 0,idx = 0,Min = INT_MAX,len = 0;
bool flag = false;
for(int i=0;i<m;i++)
{
char ch = s[i];
if(mp.find(ch) != mp.end())
{
if(!flag)
{
idx = i;
flag = true;
}
if(mp[ch] > 0)
{
--cnt;
}
--mp[ch];
}
while(cnt == 0)
{
len = i-idx+1;
if(Min > len)
{
start = idx;
Min = len;
}
char ch1 = s[idx];
if(mp.find(ch1) != mp.end())
{
if(mp[ch1] >= 0)
{
cnt++;
}
mp[ch1]++;
}
idx++;
}
}
return Min == INT_MAX ? "" : s.substr(start,Min);
}
};给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
暴力求解，求出s1的每一个排列，然后看是不是s2的子串。
- 时间复杂度：O(n!)
- 空间复杂度：O(1)
跳出全排列的思维定势，只需要遍历s2，然后每当遇到在s1中的字母时，以这个字母位置开始从s2截取与s1同等长度的字符串，和s1比较是否为同一个全排列组。而比较两个字符串是否为同一个排列，可以用哈希表，记录下两个字符串中字母的出现次数然后逐个字母进行比较。同时利用滑动窗口的思想，在遍历s2的过程中，动态地改变从s2截取的字符串对应的哈希表hash1，每遍历一个新的字母，就在hash中将它的次数加一，由于窗口大小限制为s1的长度，那么此时窗口左侧的字母在hash中的次数就需要减一，然后和s1对应的哈希表hash比较，如果相等，则返回true；否则，继续遍历下一个字母。如果遍历结束都没有发现相同的哈希表，那么返回false。
设s1的长度为m，s2的长度为n
- 时间复杂度O(mn)
- 空间复杂度O(n)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int len1 = s1.size();
int len2 = s2.size();
if(len1 > len2) return false;
if(len1 == 0) return false;
vector<int> hash(26,0),hash1(26,0);
for(int i=0;i<len1;i++)
{
hash[s1[i] - 'a']++;
hash1[s2[i] - 'a']++;
}
if(hash == hash1) return true;
for(int i=len1;i<len2;i++)
{
hash1[s2[i] - 'a']++;
hash1[s2[i-len1] - 'a']--;
if(hash[s2[i] - 'a'] > 0)
{
if(hash == hash1)
{
return true;
}
}
}
return false;
}
};