知识点

双指针算法（求字符串最大回文子串，求最长不重复子串）
模板（找字符串中某段连续的子串）

外观数列 https://leetcode-cn.com/problems/count-and-say/

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return "1";
        string last = countAndSay(n - 1);
        string ans;
        for (int i = 0; i < last.size(); i++) {
            int cnt = 1;
            for (int j = i + 1; j < last.size() && last[i] == last[j]; j++) cnt++;
            ans += to_string(cnt) + last[i];
            i += cnt - 1;
        }
        return ans;
    }
};

递归求就完事了

字母异位词分组 https://leetcode-cn.com/problems/group-anagrams/

struct Node {
    vector<int> vec;
    Node(const string & str) {
        this->vec = vector<int>(26, 0);
        for (auto ch : str) vec[ch - 'a']++;
    }
    bool operator== (const Node & n2) const {
        bool ok = true;
        for (int i = 0; i < 26 && ok; i++) if (vec[i] != n2.vec[i]) ok = false;
        return ok;
    }
};
size_t node_hash(const Node & node) {
    auto tmp = hash<int>()(node.vec[0]);
    for (int i = 1; i < 26; i++) tmp ^= hash<int>()(node.vec[i]);
    return tmp;
}
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        return rand() % 2 ? f1(strs) : f2(strs);
    }
    vector<vector<string>> f1(vector<string> & strs) {
        unordered_map<Node, vector<string>, decltype(&node_hash)> m(2000, node_hash);
        for (auto str : strs) m[Node(str)].push_back(str);
        vector<vector<string>> ans;
        for (auto p : m) ans.push_back(p.second);
        return ans;
    }
    vector<vector<string>> f2(vector<string> & strs) {
        unordered_map<string, vector<string>> m;
        for (auto str : strs) {
            auto tmp = str;
            sort(tmp.begin(), tmp.end());
            m[tmp].push_back(str);
        }
        vector< vector<string> > ans;
        for (auto p : m) ans.push_back(p.second);
        return ans;
    }
};

两种写法，顺便学习了 unordered_map 如何自定义 hash 函数和使用自定义数据类型

翻转字符串里的单词 https://leetcode-cn.com/problems/reverse-words-in-a-string/

class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        for (int i = 0; i < s.size(); i++) {
            while (i < s.size() && s[i] == ' ') i++;
            if (i == s.size()) break;
            int j = i;
            while (j < s.size() && s[j] != ' ') j++;
            reverse(s.begin() + i, s.begin() + j);
            if (k) s[k++] = ' ';
            while (i != j) s[k++] = s[i++];
        }
        s.erase(s.begin() + k, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

先诸葛单词反转，再整体反转
还有个跳过多个空格的模板

比较版本号 https://leetcode-cn.com/problems/compare-version-numbers/

class Solution {
public:
    int compareVersion(string v1, string v2) {
        int i = 0, j = 0;
        int a = 0, b = 0;
        while (i < v1.size() || j < v2.size()) {
            int x = i;
            while (x < v1.size() && v1[x] != '.') x++;
            a = i < v1.size() ? atoi(v1.substr(i, x - i).c_str()) : 0;
            int y = j;
            while (y < v2.size() && v2[y] != '.') y++;
            b = j < v2.size() ? atoi(v2.substr(j, y - j).c_str()) : 0;

            if (a > b) return 1;
            else if (a < b) return -1;
            i = x + 1, j = y + 1;
        }
        return 0;
    }
};

有个技巧，让 a 保持为 0，而 b 继续在字符串里取值，这样可以少写很多行

独特的电子邮件地址 https://leetcode-cn.com/problems/unique-email-addresses/

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> m;
        for (auto email : emails) {
            int at_pos = email.find('@');
            string local;
            for (int i = 0; i < at_pos; i++) {
                if (email[i] == '+') break;
                else if (email[i] == '.') continue;
                else local += email[i];
            }
            local += email.substr(at_pos);
            m.insert(local);
        }
        return m.size();
    }
};

用 hash表瞎搞就好

https://leetcode-cn.com/problems/longest-palindromic-substring/

class Solution {
public:
    typedef unsigned long long ull;
    string longestPalindrome(string s) {
        string ans;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i, k = i; j >= 0 && k < s.size() && s[j] == s[k]; j--, k++) 
                if (ans.size() < k - j + 1) ans = s.substr(j, k - j + 1);
            for (int j = i, k = i + 1; j >= 0 && k < s.size() && s[j] == s[k]; j--, k++)
                if (ans.size() < k - j + 1) ans = s.substr(j, k - j + 1);
        }
        return ans;
    }
};

双指针法

class Solution {
public:
    typedef unsigned long long ull;
    string longestPalindrome(string s) {
        int n = s.size();
        vector<ull> f(1000 + 5);
        vector<ull> hash1(n + 1, 0), hash2(n + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            hash1[i] = hash1[i - 1] + (s[i - 1] - 'a' + 1) * f[i - 1];
            hash2[i] = hash2[i - 1] + (s[n - i] - 'a' + 1) * f[i - 1];
            f[i] = f[i - 1] * 131;
        }
        int len = 1, pos = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (j - i + 1 < len) continue;
                ull val1 = hash1[j + 1] - hash1[i];
                ull val2 = hash2[n - i] - hash2[n - j - 1];
                val1 *= f[n - j - 1];
                val2 *= f[i];
                if (val1 == val2) len = j - i + 1, pos = i;
            }
        return s.substr(pos, len);
    }
};

字符串hash，发现可以不用记花里胡哨的了，按照字符串顺序，把 hash表建出来
比较的时候，不用画图了，直接看哪个长，同意按照长的那个乘以 131

Z 字形变换 https://leetcode-cn.com/problems/zigzag-conversion/

class Solution {
public:
    string convert(string s, int numRows) {
        string ans;
        if (numRows == 1) return s;
        for (int i = 1; i <= numRows; i++) {
            if (i == 1 || i == numRows) for (int j = i - 1; j < s.size(); j += 2 * (numRows - 1)) ans.push_back(s[j]);
            else {
                int j1 = i - 1, j2 = 2 * (numRows - 1) - i + 1;
                bool ok = true;
                while (j1 < s.size() || j2 < s.size()) {
                    if (j1 < s.size()) ans.push_back(s[j1]), j1 += 2 * (numRows - 1);
                    if (j2 < s.size()) ans.push_back(s[j2]), j2 += 2 * (numRows - 1);
                }
            }
        }
        return ans;
    }
};

找规律题，第一行和最后一行是正常的等差梳理，其他行是错开来的等差数列

无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int a[256] = {};
        int len = 0;
        for (int i = 0, j = 0; i < s.size(); i++) {
            a[s[i]]++;
            while (a[s[i]] > 1) a[s[j++]]--;
            len = max(len, i - j + 1);
        }
        return len;
    }
};

双指针法，有个固定套路：

先想暴力怎么做
看问题是否有单调性
利用双指针优化

实现 Trie (前缀树) https://leetcode-cn.com/problems/implement-trie-prefix-tree/

class Trie {
public:
    /** Initialize your data structure here. */
    struct Node {
        bool end;
        int *a;
        Node() {
            end = false;
            a = new int[26];
            for (int i = 0; i < 26; i++) a[i] = 0;
        }
    };
    vector<Node*> tree;
    Trie() {
        tree.push_back(new Node());
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        int j = 0;
        for (auto ch : word) {
            if (tree[j]->a[ch - 'a'] == 0) {
                tree.push_back(new Node());
                tree[j]->a[ch - 'a'] = tree.size() - 1;
                j = tree.size() - 1;
            } else {
                j = tree[j]->a[ch - 'a'];
            }
        }
        tree[j]->end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        int j = 0;
        for (auto ch : word) {
            j = tree[j]->a[ch - 'a'];
            if (j == 0) return false;
        }
        return tree[j]->end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int j = 0;
        for (auto ch : prefix) {
            j = tree[j]->a[ch - 'a'];
            if (!j) return false;
        }
        return true;
    }
};

就是 Trie 的模板

整数转换英文表示 https://leetcode-cn.com/problems/integer-to-english-words/

class Solution {
public:
    unordered_map<int, string> m;
    string numberToWords(int num) {
        string strs[] = {
            "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
            "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen",
            "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety",
            "Hundred", "Thousand", "Million", "Billion"
        };
        int j = 0;
        for (int i = 0; i <= 10; i++, j++) m[i] = strs[j];
        for (int i = 11; i <= 19; i++, j++) m[i] = strs[j];
        for (int i = 20; i <= 100; i += 10, j++) m[i] = strs[j];
        m[1000] = strs[j++];
        m[1000 * 1000] = strs[j++];
        m[1000 * 1000 * 1000] = strs[j];
        function<void (int, vector<string> &)> f = [&](int val, vector<string> & vec) {
            if (val < 20) vec.push_back(m[val]);
            else if (val < 100) vec.push_back(m[val / 10 * 10]), f(val % 10, vec);
            else if (val < 1000) vec.push_back(m[val / 100]), vec.push_back(m[100]), f(val % 100, vec);
            else for (long long i = 1000, j = 0; j < 3; j++, i *= 1000)
                    if (val < i * 1000) {
                        f(val / i, vec), vec.push_back(m[i]), f(val % i, vec);
                        break;
                    }
        };
        vector<string> ans_vec;
        f(num, ans_vec);
        auto ans = accumulate(ans_vec.begin(), ans_vec.end(), string(""), [](auto a, auto b) {
            if (b == "") return a;
            if (a == "") return b;
            return a + " " + b;
        });
        return ans == "" ? "Zero" : ans;
    }
};

利用递归实现

小于 20 直接返回
小于100的，返回几个十 + f(val % 10)
小于1000的，返回几个 hundred + f(val % 100)
小于1000 * 1000 的，返回几个 thousand + f(val % 1000)
小于 1000 1000 1000 的，返回几个 million + f(val % (1000 * 1000))
小于 1000 1000 1000 1000 的，返回几个 billion + f(val % (1000 1000 * 1000))

算法学习笔记

字符串专题

知识点