头像

adnil8130

SJTU


访客:12004

离线:9分钟前



逆向思维 + floodfill $time O(n^2)$

先对边界的’O’做Floodfill,然后翻转剩余的未被Floodfill到的”O”

class Solution {
private:
    int m, n;
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        m = board.size(), n = board[0].size();

        vector<vector<bool>> canFlip(m, vector<bool>(n, true));

        // 第一行
        for (int j = 0; j < n; ++j)
            if (board[0][j] == 'O' && canFlip[0][j])
                dfs(0, j, canFlip, board);
        // 最后一行
        for (int j = 0; j < n; ++j)
            if (board[m - 1][j] == 'O' && canFlip[m - 1][j])
                dfs(m - 1, j, canFlip, board);
        // 左右两条边
        for (int i = 1; i < m - 1; ++i){
            if (board[i][0] == 'O' && canFlip[i][0])
                dfs(i, 0, canFlip, board);
            if (board[i][n - 1] == 'O' && canFlip[i][n - 1])
                dfs(i, n - 1, canFlip, board);
        }
        // 最终转换
        for (int i = 1; i < m - 1; ++i)
            for (int j = 1; j < n - 1; ++j)
                if (board[i][j] == 'O' && canFlip[i][j])
                    board[i][j] = 'X';
    }

    void dfs(int r, int c, vector<vector<bool>> &canFlip, vector<vector<char>> &board){
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
        canFlip[r][c] = false;

        for (int k = 0; k < 4; ++k){
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O' && canFlip[nr][nc])
                dfs(nr, nc, canFlip, board);
        }
    }
};


活动打卡代码 AcWing 126. 单词接龙 II

BFS层序遍历建图 + DFS枚举求方案

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());

        if (beginWord == endWord) return {{beginWord}};
        if (!wordSet.count(endWord)) return {};

        unordered_map<string, vector<string>> g;
        queue<string> Q; Q.push(beginWord); wordSet.erase(beginWord);
        bool found = false;

        while (Q.size()){
            int size = Q.size();
            unordered_set<string> visited;

            while (size--){
                string word = Q.front(); Q.pop();
                string ori_w = word;
                for (int i = 0; i < word.size(); ++i){
                    char ori = word[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        if (c == ori) continue;
                        word[i] = c;
                        if (wordSet.count(word)){
                            if (word == endWord) found = true;
                            // 虽然找到了目标,但是这一层图还是要建完的
                            g[ori_w].push_back(word);
                            // 没有访问过的才加入队列,并且标记为访问过了
                            if (!visited.count(word)){
                                visited.insert(word);
                                Q.push(word);
                            }
                        }
                    }
                    word[i] = ori;
                }
            }
            for (string w: visited) wordSet.erase(w);
            if (found) break; // 层序遍历到目标了,就不用再建多余的图了
        }

        vector<vector<string>> res;
        vector<string> path = {beginWord};
        dfs(path, res, endWord, g);

        return res;
    }

    void dfs(vector<string> &path, vector<vector<string>> &res, string endWord, unordered_map<string, vector<string>> &g){
        if (path.back() == endWord){
            res.push_back(path);
            return;
        }

        for (string head: g[path.back()]){
            path.push_back(head);
            dfs(path, res, endWord, g);
            path.pop_back();
        }
    }
};


活动打卡代码 AcWing 127. 单词接龙

朴素BFS $time O(n)$

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (beginWord == endWord) return 1;
        if (!wordSet.count(endWord)) return 0;
        queue<string> Q; Q.push(beginWord); wordSet.erase(beginWord);
        int step = 2;

        while (Q.size()){
            int size = Q.size();
            while (size--){
                string word = Q.front(); Q.pop();
                for (int i = 0; i < word.size(); ++i){
                    char ori = word[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        if (c == ori) continue;
                        word[i] = c;
                        if (wordSet.count(word)){
                            if (word == endWord) return step;
                            Q.push(word);
                            wordSet.erase(word);
                        }
                    }
                    word[i] = ori;
                }
            }
            ++step;
        }

        return 0;
    }
};

双向BFS $time O(n)$

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());

        if (beginWord == endWord) return 1;
        if (!wordSet.count(endWord)) return 0;

        unordered_set<string> head, tail, *go = nullptr, *wait = nullptr;
        head.insert(beginWord); wordSet.erase(beginWord);
        tail.insert(endWord); wordSet.erase(endWord);
        int step = 2;

        while (head.size() && tail.size()){
            if (head.size() < tail.size()) go = &head, wait = &tail;
            else go = &tail, wait = &head;
            unordered_set<string> tmp;
            for (string word: *go){
                for (int i = 0; i < word.size(); ++i){
                    char ori = word[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        if (c == ori) continue;
                        word[i] = c;
                        if (wait->count(word)) return step;
                        if (wordSet.count(word)){
                            tmp.insert(word);
                            wordSet.erase(word);
                        }
                    }
                    word[i] = ori;
                }
            }
            go->swap(tmp);
            ++step;
        }

        return 0;
    }
};


活动打卡代码 AcWing 128. 最长连续序列

哈希表$O(n)$
哈希表记录的是一个数字左边能延展多长,右边又能延展多长。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size(), res = 0;
        unordered_map<int, int> l_len, r_len;

        for (int num: nums){
            if (l_len.count(num)) continue;
            l_len[num] = r_len[num] = 0;
            if (l_len.count(num - 1)) l_len[num] = l_len[num - 1] + 1;
            if (r_len.count(num + 1)) r_len[num] = r_len[num + 1] + 1;

            r_len[num - l_len[num]] = l_len[num] + r_len[num];
            l_len[num + r_len[num]] = r_len[num] + l_len[num];

            res = max(res, l_len[num] + r_len[num] + 1);
        }

        return res;
    }
};

更简洁的写法

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        unordered_map<int, int> endat, startat;
        int res = 0;

        for (int num: nums){
            int l = endat[num - 1], r = startat[num + 1];
            int len = l + r + 1;
            res = max(res, len);
            startat[num - l] = max(startat[num - l], len);
            endat[num + r] = max(endat[num + r], len);
        }
        return res;
    }
};



DFS遍历 $time O(n)$
遍历所有节点,遍历过程中记录当前路径的和,到达叶子节点了更新一下答案即可。

class Solution {
private:
    int res = 0;
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;
        dfs(root, 0);
        return res;
    }

    void dfs(TreeNode *root, int cur_sum){
        if (!root) return;
        cur_sum = 10 * cur_sum + root->val;
        if (!root->left && !root->right){
            res += cur_sum;
            return;
        }

        dfs(root->left, cur_sum);
        dfs(root->right, cur_sum);
    }
};


活动打卡代码 LeetCode 125. 验证回文串

双指针模拟 $O(n)$
isalnum,tolower这种函数名经常写错,复习一下

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) return true;
        int n = s.size(), i = 0, j = n - 1;
        while (i < j){
            while (i < j && !isalnum(s[i])) ++i;
            while (i < j && !isalnum(s[j])) --j;
            if (tolower(s[i]) == tolower(s[j])) ++i, --j;
            else return false;
        }

        return true;
    }
};



后序遍历 $time O(n)$
这道题需要特别注意负数的情况。

class Solution {
private:
    int res = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        if (!root) return 0;
        dfs(root);
        return res;
    }

    int dfs(TreeNode *root){
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);

        res = max(res, left + root->val + right);

        return max(0, max(left, right) + root->val);
    }
};



前后缀分解 $time O(3n)$ $space O(3n)$
前后缀分解比较生疏,复习一波。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.empty()) return 0;
        int n = p.size(), INF = 0x3f3f3f3f;
        int l[n + 2], r[n + 2];
        memset(l, 0, sizeof l);
        memset(r, 0, sizeof r);

        int cur_min = INF;
        for (int i = 1; i <= n; ++i){
            cur_min = min(cur_min, p[i - 1]);
            l[i] = max(l[i - 1], p[i - 1] - cur_min);
        }

        int cur_max = -INF;
        for (int i = n; i >= 1; --i){
            cur_max = max(cur_max, p[i - 1]);
            r[i] = max(r[i + 1], cur_max - p[i - 1]);
        }

        int res = 0;
        for (int i = 2; i <= n; ++i){
            res = max(res, l[i] + r[i + 1]);
        }

        return res;
    }
};

状态机DP $time O(5n)$ $space O(5n)$

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.empty()) return 0;
        int n = p.size(), INF = 0x3f3f3f3f;
        int f[n + 1][5]; memset(f, -INF, sizeof f);
        for (int i = 0; i <= n; ++i) f[i][0] = 0;

        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= 4; ++j){
                if (j & 1) f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] - p[i - 1]);
                else f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + p[i - 1]);
            }
        }

        return max(0, max(f[n][2], f[n][4]));
    }
};

状态机DP 空间优化版 $time O(5n)$ $space O(5)$

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.empty()) return 0;
        int n = p.size(), INF = 0x3f3f3f3f;
        int begin = 0, buy1 = -INF, sell1 = -INF, buy2 = -INF, sell2 = -INF;

        for (int i = 1; i <= n; ++i){
            sell2 = max(sell2, buy2 + p[i - 1]);
            buy2 = max(buy2, sell1 - p[i - 1]);
            sell1 = max(sell1, buy1 + p[i - 1]);
            buy1 = max(buy1, begin - p[i - 1]);
        }

        return max(0, max(sell1, sell2));
    }
};



贪心 $time O(n)$

有利可图就买卖,无利可图就蹲。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.empty()) return 0;
        int res = 0;

        for (int i = 1; i < p.size(); ++i){
            if (p[i] > p[i - 1]) res += p[i] - p[i - 1];
        }

        return res;
    }
};



贪心 $time O(n)$
实时更新最小值,用当前价格去减最小值来更新最大利润。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        if (p.empty()) return 0;
        int res = 0, cur_min = 0x3f3f3f3f;

        for (int num: p){
            cur_min = min(cur_min, num);
            res = max(res, num - cur_min);
        }

        return res;
    }
};