242 有效的異位數(shù)組

標(biāo)簽：哈希表 計數(shù)器 數(shù)組
最近做到好多這種題目，都是用哈希表來解決的。不過鑒于本題只有26個小寫字母，用數(shù)組來實現(xiàn)一個計數(shù)器就可以了,統(tǒng)計s的時候++，統(tǒng)計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 字符串轉(zhuǎn)換整數(shù)（atoi）

標(biāo)簽：字符串，溢出
這個題目很煩，一方面需要留心有沒有溢出的情況，另一方面輸入的字符串格式有各種各樣，題目交代的也不是很清楚，提交了幾次報錯，最后才糾正把題目要求搞清楚。
這里采用的是提前判斷溢出的方式，正數(shù)的情況下，n * 10 + int(str[i] - '0') > 2147483647時，下一步就會溢出；負數(shù)時，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 實現(xiàn)strStr()

暴力解法，時間復(fù)雜度是O(mn), 空間復(fù)雜度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;
    }
};

不過，這種做法還是太慢了，從題解中學(xué)到一種Sunday算法，好理解而且速度還很快。題解地址：https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/
首先遍歷一遍模式串（短的那個），把所有出現(xiàn)的字符的最小位置偏移記錄下來：len-idx。
比如：目標(biāo)串 a b a a b, 模式串 a a b，則a的最小位置偏移是2，b是1.
第一次匹配
a b a a b
a a b
匹配失敗。取模式串右邊第一個字符，也就是目標(biāo)串中的第三個字符，a，其最小偏移位置是2，則下一次，模式串右移2.
第二次匹配
a b a a b
-----a a b
這一次，匹配成功。如果模式串右邊的第一個字符沒有在模式串中出現(xiàn)，則模式串右移模式串的長度。
雖然，最壞情況下，這種做法的時間復(fù)雜度也是O(mn)，但是實際上能節(jié)省的操作要多得多。
代碼：

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算法：
該算法參考鄧俊輝老師的數(shù)據(jù)結(jié)構(gòu)課程。
KMP構(gòu)造了一個next數(shù)組，用于存放當(dāng)前模式串的字符與文本串失配后，模式串下一個與當(dāng)前文本串字符做匹配的位置。next的獲取方式為：對于模式串P[0, j), n[j]為P[0,j)的最長的相等的前綴與后綴長度。比如abcmabc, 前綴abc與后綴abc可以自匹配，則n[7]=3.如果abcmabcx的x與當(dāng)前文本串字符失配，則變?yōu)閍bcm的m與當(dāng)前文本串字符做匹配。
這里，在-1設(shè)置了一個通配符作為哨兵（假想的），next數(shù)組在0處為-1，即如果P[0]與當(dāng)前文本串失配，下一次將-1處的通配符移到當(dāng)前位置，也就相當(dāng)于模式串整體右移一步。
還需注意的問題是，對于：

當(dāng)模式串在第四個位置與1失配后，模式串不應(yīng)該右移1，因為左邊都是0，都會與1失配。所以，在構(gòu)造next數(shù)組時，也應(yīng)該特別注意一下。

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;
}

};