前言

鉴于LeetCode的题目太多了，刷题感觉无从下手，不如刷下曾经出过的面试题，看下难度、题型分布，以便于抓住重点，就先从字节跳动的面试题库开始刷吧。我选择刷题的语言用的C++，抱歉其他语言暂时不考虑了，刷算法题最重要的还是思路，然后能用自己熟悉的语言写出来其实就够格了。刷题的顺序是按照频度和最近考察时间来排序的。

刷题网站链接：CodeTop。

注意的是，这里我并没有将全部题目给出，因为有些题目着实比较水，就没必要占用时间来写了，只给出了我认为比较好和我自己第一遍没做出得题目。

闲言碎语不再讲，速速过招吧，开刷！

题解

139. 单词拆分

动态规划：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0] = true;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] &&
                    wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

回溯(记忆化搜索)：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<int, bool> memo;
        return backtrack(s, 0, memo, wordDict);
    }

    bool backtrack(const string& s, int pos, unordered_map<int, bool>& memo,
                   const vector<string>& wordDict) {
        if (memo.find(pos) != memo.end()) {
            return memo[pos];
        }
        if (pos == s.size()) {
            memo[pos] = true;
            return true;
        }
        for (int i = 0; i < wordDict.size(); i++) {
            if (wordDict[i] == s.substr(pos, wordDict[i].size()) &&
                backtrack(s, pos + wordDict[i].size(), memo, wordDict)) {
                memo[pos] = true;
                return true;
            }
        }
        memo[pos] = false;
        return false;
    }
};

5. 最长回文子串

双指针

class Solution {
private:
    int resLen;
    string res;

public:
    string longestPalindrome(string s) {
        resLen = 0;
        res = "";
        int n = s.size();
        for (int i = 0; i < n; i++) {
            helper(s, i, i);
            helper(s, i, i + 1);
        }
        return res;
    }

    void helper(const string& s, int start, int end) {
        int i = start, j = end;
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            i--;
            j++;
        }
        if (j - i - 1 > resLen) {
            resLen = j - i - 1;
            res = s.substr(i + 1, resLen);
        }
    }
};

200. 岛屿数量

深度优先搜索:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int row, int col, int rows, int cols) {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||
            grid[row][col] == '0') {
            return;
        }
        grid[row][col] = '0';
        dfs(grid, row - 1, col, rows, cols);
        dfs(grid, row + 1, col, rows, cols);
        dfs(grid, row, col - 1, rows, cols);
        dfs(grid, row, col + 1, rows, cols);
    }
};

广度优先搜索：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    grid[i][j] = '0';
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    while (!q.empty()) {
                        auto item = q.front();
                        q.pop();
                        int row = item.first, col = item.second;
                        if (row + 1 < rows && grid[row + 1][col] == '1') {
                            q.push({row + 1, col});
                            grid[row + 1][col] = '0';
                        }
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            q.push({row - 1, col});
                            grid[row - 1][col] = '0';
                        }
                        if (col + 1 < cols && grid[row][col + 1] == '1') {
                            q.push({row, col + 1});
                            grid[row][col + 1] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            q.push({row, col - 1});
                            grid[row][col - 1] = '0';
                        }
                    }
                }
            }
        }
        return res;
    }
};