242 有效的异位数组
标签：哈希表 计数器 数组
最近做到好多这种题目，都是用哈希表来解决的。不过鉴于本题只有26个小写字母，用数组来实现一个计数器就可以了,统计s的时候++，统计t的时候--，什么时候小于0了，就返回false。
代码：
time:80.03%, memory:5.66%
class Solution {
public:
bool isAnagram(string s, string t) {
int cnt_s[26] = {0};
for(int i = 0; i < s.size(); i++)
cnt_s[s[i]-'a']++;
for(int i = 0; i < t.size(); i++){
cnt_s[t[i]-'a']--;
if(cnt_s[t[i]-'a'] < 0) return false;
}
for(int i = 0; i < 26; i++){
if(cnt_s[i] > 0) return false;
}
return true;
}
};
8 字符串转换整数（atoi）
标签：字符串，溢出
这个题目很烦，一方面需要留心有没有溢出的情况，另一方面输入的字符串格式有各种各样，题目交代的也不是很清楚，提交了几次报错，最后才纠正把题目要求搞清楚。
这里采用的是提前判断溢出的方式，正数的情况下，n * 10 + int(str[i] - '0') > 2147483647时，下一步就会溢出；负数时，n * 10 - int(str[i] - '0') < -2147483648，下一步也会溢出。
代码：
time: 56.71%, memory: 10.68%
class Solution {
public:
int myAtoi(string str) {
int n = 0;
bool is_neg;
int i = 0, valid = 0, m;
while(i < str.size() && str[i] == ' ')
i++;
if(i == str.size()) return 0; // empty string
if(str[i] == '-') {
is_neg = true;
i++;
if(!isdigit(str[i])) return 0;
}
else if(str[i] == '+'){
is_neg = false;
i++;
if(!isdigit(str[i])) return 0;
}
else if(isdigit(str[i])) is_neg = false;
else return 0; // not valid
for(; i < str.size(); i++){
if(!isdigit(str[i])) break; // partial invalid
if(is_neg){
if(n < (-2147483648 + int(str[i] - '0')) / 10.0)
return -2147483648;
n = n * 10 - int(str[i] - '0');
}
else{
if(n > (2147483647 - int(str[i] - '0')) / 10.0)
return 2147483647;
n = n * 10 + int(str[i] - '0');
}
}
return n;
}
};
28 实现strStr()
暴力解法，时间复杂度是O(mn), 空间复杂度O(1).
time: 10.62%, memory: 64.59%
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.size() == 0) return 0;
if(haystack.size() < needle.size()) return -1;
for(int i = 0; i < haystack.size(); i++){
int p = i, q = 0;
while(p < haystack.size() && q < needle.size() && haystack[p] == needle[q]){
p++;
q++;
}
if(q == needle.size()) return i;
}
return -1;
}
};
不过，这种做法还是太慢了，从题解中学到一种Sunday算法，好理解而且速度还很快。题解地址：https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/
首先遍历一遍模式串（短的那个），把所有出现的字符的最小位置偏移记录下来：len-idx。
比如：目标串 a b a a b, 模式串 a a b，则a的最小位置偏移是2，b是1.
第一次匹配
a b a a b
a a b
匹配失败。取模式串右边第一个字符，也就是目标串中的第三个字符，a，其最小偏移位置是2，则下一次，模式串右移2.
第二次匹配
a b a a b
-----a a b
这一次，匹配成功。如果模式串右边的第一个字符没有在模式串中出现，则模式串右移模式串的长度。
虽然，最坏情况下，这种做法的时间复杂度也是O(mn)，但是实际上能节省的操作要多得多。
代码：
time: 93.79%, memory: 15.78%
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.size() == 0) return 0;
if(haystack.size() < needle.size()) return -1;
// calculate index_map
map<char, int> index_map;
for(int i = 0; i < needle.size(); i++){
index_map[needle[i]] = needle.size() - i;
}
// match
int idx = 0;
while(idx + needle.size() <= haystack.size()){
int p = idx, q = 0;
while(p < haystack.size() && q < needle.size() && haystack[p] == needle[q]){
p++;
q++;
}
if(q == needle.size()) return idx;
if(idx + needle.size() >= haystack.size()) return -1;
if(index_map.count(haystack[idx + needle.size()])){
idx += index_map[haystack[idx + needle.size()]];
}
else{
idx = idx + needle.size() + 1;
}
}
return -1;
}
};
KMP算法：
该算法参考邓俊辉老师的数据结构课程。
KMP构造了一个next数组，用于存放当前模式串的字符与文本串失配后，模式串下一个与当前文本串字符做匹配的位置。next的获取方式为：对于模式串P[0, j), n[j]为P[0,j)的最长的相等的前缀与后缀长度。比如abcmabc, 前缀abc与后缀abc可以自匹配，则n[7]=3.如果abcmabcx的x与当前文本串字符失配，则变为abcm的m与当前文本串字符做匹配。
这里，在-1设置了一个通配符作为哨兵（假想的），next数组在0处为-1，即如果P[0]与当前文本串失配，下一次将-1处的通配符移到当前位置，也就相当于模式串整体右移一步。
还需注意的问题是，对于：
当模式串在第四个位置与1失配后，模式串不应该右移1，因为左边都是0，都会与1失配。所以，在构造next数组时，也应该特别注意一下。
time: 93.85%, memory: 6.43%
class Solution {
public:
vector<int> get_next(string P){
vector<int> next;
next.push_back(-1);
int p = 0, q = -1, p_len = P.size();
while(p < p_len - 1){
if(q < 0 || P[p] == P[q]){
p++;
q++;
if(P[p] == P[q]) next.push_back(next[q]); // 如果两个字符相同
else next.push_back(q);
}
else{
q = next[q];
}
}
return next;
}
int strStr(string haystack, string needle) {
if (haystack.size() < needle.size()) return -1;
// if (needle.size() == 0) return 0;
vector<int> next = get_next(needle);
int h_len = haystack.size(), n_len = needle.size();
int p = 0, q = 0;
while(q < n_len && p < h_len){
if(q < 0 || haystack[p] == needle[q]){
p++;
q++;
}
else
q = next[q];
}
if(q == needle.size()) return (p - q);
return -1;
}
};
