Mind palace

637. Average of Levels in Binary Tree

Posted on 2021-01-15 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 665 Reading time ≈ 1 mins.

bfs O(n) time O(logn) space

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) return {};
        vector<double> res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            double sum = 0;
            for (int i = 0; i < n; ++i) {
                auto node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(sum / n);
        }
        return res;
    }
};

773. Sliding Puzzle

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 3.1k Reading time ≈ 3 mins.

bfs O(r*c*(r*c)!) time O(r*c*(r*c)!) space
这道题也可以用A*算法

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0, m = board.size(), n = board[0].size();
        string target = "123450", start;
        for (const auto &v : board) {
            for (char c : v) {
                start += '0' + c; // 得到初始状态的board
            }
        }
        vector<vector<int>> next{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}}; // 当0在每个位置时的下一步能去哪
        unordered_set<string> visited{start}; // 用字符串来保存状态
        queue<string> q{{start}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto cur = q.front(); q.pop();
                if (cur == target) return res;
                int zero_idx = cur.find("0");
                for (int v : next[zero_idx]) { // 查表来枚举所有可能产生的下个board状态
                    swap(cur[v], cur[zero_idx]);
                    if (!visited.count(cur)) {
                        visited.insert(cur);
                        q.push(cur);
                    }
                    swap(cur[v], cur[zero_idx]);
                }
            }
            ++res;
        }
        return -1;
    }
};

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0, m = board.size(), n = board[0].size();
        string target = "123450", start;
        vector<vector<int>> next{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}}; // 当0在每个位置时的下一步能去哪
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                start += '0' + board[i][j]; // 得到初始状态的board
            }
        }
        unordered_set<string> visited{start}; // 用字符串来保存状态
        queue<string> q{{start}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                string cur = q.front(); q.pop();
                if (cur == target) return res;
                int zero_idx = cur.find("0");
                for (int v : next[zero_idx]) { // 查表来枚举所有可能产生的下个board状态
                    string cand = cur;
                    swap(cand[v], cand[zero_idx]);
                    if (visited.count(cand)) continue;
                    visited.insert(cand);
                    q.push(cand);
                }
            }
            ++res;
        }
        return -1;
    }
};

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        auto hash = [](const vector<vector<int>> &b) {
            int res = 0;
            for (const auto &v : b) {
                for (int x : v) {
                    res = res * 10 + x;
                }
            }
            return res;
        };
        unordered_set<vector<vector<int>>, decltype(hash)> m(33, hash); // 必须要提供初始桶的个数！！
        queue<vector<vector<int>>> q;
        q.push(board);
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        int res = 0;
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                auto b = q.front(); q.pop();
                if (hash(b) == 123450) return res;
                if (m.count(b)) continue;
                m.insert(b);
                auto v = find(b);
                for (int j = 0; j < 4; ++j) {
                    auto t = v;
                    t[0] += dr[j];
                    t[1] += dc[j];
                    if (t[0] < 0 || t[0] > 1 || t[1] < 0 || t[1] > 2) continue;
                    swap(b[v[0]][v[1]], b[t[0]][t[1]]);
                    q.push(b);
                    swap(b[v[0]][v[1]], b[t[0]][t[1]]);
                }
            }
            ++res;
        }
        return -1;
    }

    vector<int> find(const vector<vector<int>> &b) {
        for (int r = 0; r < 2; ++r) {
            for (int c = 0; c < 3; ++c) {
                if (b[r][c] == 0) return {r, c};
            }
        }
    }
};

152. Maximum Product Subarray

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 454 Reading time ≈ 1 mins.

dp O(n) time O(1) space
看到这道题首先应该想到53. Maximum Subarray所以是dp
难点在于乘积受负数影响，只找最大乘积是行不通的，比较tricky的地方是要维护最大乘积和最小乘积，然后分情况对正负数进行讨论，讨论的思路和求最大和一致
mn和mx分别表示以x为结尾的连续子数组的最小和最大值

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        long mn = 1, mx = 1, res = LONG_MIN;
        for (long x : nums) {
            if (x < 0) {
                long t = mn;
                mn = min(x, mx * x);
                mx = max(x, t * x);
            } else {
                mn = min(x, mn * x);
                mx = max(x, mx * x);
            }
            res = max(res, mx);
        }
        return res;
    }
};

494. Target Sum

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

O(n*target)
把问题转换成真正的类背包问题
原来是每个数+或者-，现在每个数都乘2，这样就变成0个或者1个，也就是加这个数或者不加这个数

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S) return 0; // 所有数都加起来都到不了S，直接返回0
        for_each(nums.begin(), nums.end(), [](int &num){num <<= 1;});
        long target = sum + S; // 背包的目标值也要调整
        vector<vector<int>> f(target + 1, vector<int>(nums.size() + 1));
        f[0][0] = 1;
        for (int i = 0; i <= target; ++i) {
            for (int j = 1; j < f[i].size(); ++j) {
                f[i][j] = f[i][j - 1] + (i >= nums[j - 1] ? f[i - nums[j - 1]][j - 1] : 0);
            }
        }
        return f.back().back();
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S) return 0;
        for_each(nums.begin(), nums.end(), [](int &num){num <<= 1;});
        int target = sum + S, n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(target + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= target; ++j) {
            // for (int j = target; j >= 0; --j) {
                f[i][j] = f[i - 1][j] + (j >= nums[i - 1] ? f[i - 1][j - nums[i - 1]] : 0);
            }
        }
        return f[n][target];
    }
};

因为转换后的背包问题要求原来的所有数都要double，则新的target = sum + S也必须是个偶数，这样其实不需要修改nums，只需要把新的target除2即可，前提是target必须是偶数

原来的每个数放-1个或者1个转换成放0个或者2个
目标值从S变成sum + S，因为相当于在原来的每种可能基础上加了一个sum
这样相当于每个数都double了，进而变成标准0-1背包问题，即放这个数（原来的2倍）或者不放这个数
又因为原来的每个数要不是0个要不是2个，所以最后的目标值必须是偶数，所以可以不需要手动double每个数，仍然可以使用原来的数，只是目标值改成(sum + S) / 2

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = accumulate(nums.begin(), nums.end(), 0);
        long target = sum + S, n = nums.size();
        if (sum < S || target & 1) return 0; // 如果target不是偶数则得不到结果
        target >>= 1;
        vector<int> f(target + 1);
        f[0] = 1;
        for (int x : nums) {
            for (int t = target; t >= x; --t) { // 注意一维0-1背包一定要倒序
                f[t] += f[t - x];
            }
        }
        return f[target];
    }
};

153. Find Minimum in Rotated Sorted Array

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 343 Reading time ≈ 1 mins.

二分O(logn)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > nums[r]) { // compare m with r rather than l because m could be l but never be r (in that case, m == r == l, impossible)
                l = m + 1;
            } else {
                r = m;
            }
        }
        return nums[l];
    }
};

399. Evaluate Division

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

bfs O(n) 有向图连通性

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); ++i) {
            g[equations[i][0]][equations[i][1]] = values[i];
            g[equations[i][1]][equations[i][0]] = 1 / values[i];
        }
        vector<double> ret;
        for (auto&& query : queries) {
            ret.emplace_back(helper(query[0], query[1]));
        }
        return ret;
    }

    double helper(const string &begin, const string &end) {
        if (g.count(begin) == 0 || g.count(end) == 0) return -1.0;
        if (g.count(begin) && g[begin].count(end)) return g[begin][end]; // 假如cache里有则直接返回
        unordered_set<string> s; // 避免重复访问
        queue<pair<string, double>> q{{{begin, 1.0}}}; // key是点value是从begin到这个点的累乘结果，也就是begin / key的结果
        while (!q.empty()) {
            auto [u, product] = q.front(); q.pop();
            if (s.count(u)) continue;
            if (g[u].count(end)) return product * g[u][end];
            s.emplace(u);
            g[begin][u] = product; // cache中间结果
            g[u][begin] = 1 / product;
            for (auto [v, quotient] : g[u]) {
                q.emplace(v, product * quotient);
            }
        }
        return -1.0;
    }

    unordered_map<string, unordered_map<string, double>> g; // 这道题需要用邻接矩阵
};

1055. Shortest Way to Form String

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

greedy O(m+n) time
f[i][c]表示在source中从下标i开始第一次出现的字母c在source中的下标，这样做可以跳过中间不符合要求的那些字母方便快速查找

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        vector<vector<int>> f(m, vector<int>(26, -1));
        f[m - 1][source[m - 1] - 'a'] = m - 1;
        for (int i = m - 2; i >= 0; --i) {
            f[i] = f[i + 1]; // 先copy后一个index的内容
            f[i][source[i] - 'a'] = i; // 再修改当前index所对应的字符的下标
        }
        int res = 1, i = 0; // res要从1开始因为target最后一个字符结束以后没法更新res
        for (char c : target) {
            if (f[0][c - 'a'] == -1) return -1; // 如果source所有字符里都不包含c
            if (i == m || f[i][c - 'a'] == -1) { // 如果source所有字符都比对完或者尚未比对完但是source当前位置之后没有c（之前可能有）则重置指针并更新res
                i = 0;
                ++res;
            }
            i = f[i][c - 'a'] + 1; // 移动指针到下一个可能的位置（跳过中间不符合要求的字符）
        }
        return res;
    }
};

greedy O(m*n) time
worst case比如[“abcd”, “ddddd”]

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = size(source), n = size(target);
        int res = 0;
        for (int i = 0; i < n;) {
            int t = i;
            for (int j = 0; j < m; ++j) {
                if (i < n && source[j] == target[i]) {
                    ++i;
                }
            }
            if (i == t) return -1;
            ++res;
        }
        return res;
    }
};

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        bool f[26] = {false};
        for (char c : source) {
            f[c - 'a'] = true;
        }
        int res = 1;
        for (int i = 0, j = 0; i < n; ++i, ++j) {
            if (!f[target[i] - 'a']) return -1;
            while (j < m && source[j] != target[i]) ++j;
            if (j == m) {
                j = -1;
                --i;
                ++res;
            }
        }
        return res;
    }
};

dp O(m*m+(n-m)*n) time
f[i]表示target前i个字符需要几个source的子序列才能构成

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int k = m - 1;
            for (int j = i - 1; j >= 0; --j) {
                while (k >= 0 && source[k] != target[j]) --k;
                if (k == -1) {
                    if (f[i] == INT_MAX) return -1;
                    break;
                } else {
                    f[i] = min(f[i], f[j] + 1);//cout<<"f["<<i<<"] = "<<f[i]<<endl;
                    --k;
                }
            }
        }
        return f[n];
    }
};

698. Partition to K Equal Sum Subsets

Posted on 2021-01-14 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 3.4k Reading time ≈ 3 mins.

backtracking time O(2ⁿ) space O(n)
每次递归的深度是O(n)
先找到target，然后对数组从大到小排序，用回溯试数即可

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false; // 这行必须要有！全靠后边handle速度太慢！
        int n = nums.size();
        vector<bool> v(n);
        return dfs(target, nums, v, k, target); // 从target往下减
    }

    bool dfs(int s, const vector<int> &A, vector<bool> &v, int k, int target) {
        if (k == 0) return true; // 找到了k组
        // if (s < 0) return false; // 不合要求
        if (s == 0) return dfs(target, A, v, k - 1, target); // 找到一组可能的，尝试找下一组
        for (int i = 0; i < A.size(); ++i) {
            if (v[i] || A[i] > s) continue;
            // if (A[i] > s) return false; // 这行能加速？！匪夷所思
            v[i] = true;
            if (dfs(s - A[i], A, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

最快版本

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false;
        int n = nums.size();
        vector<bool> v(n);
        return dfs(target, nums, 0, v, k, target);
    }

    bool dfs(int s, const vector<int> &A, int b, vector<bool> &v, int k, int target) {
        if (k == 0) return true;
        if (s < 0) return false;
        if (s == 0) return dfs(target, A, 0, v, k - 1, target); // 注意是从0开始，因为找到一组并不意味着前边的都放到某个组里了，只能从头再找
        for (int i = b; i < A.size(); ++i) {
            if (v[i]) continue;
            v[i] = true;
            if (dfs(s - A[i], A, i + 1, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false;
        int n = nums.size();
        vector<bool> v(n);
        // int i = 0; // 跳过那些自成一组的
        // for (; i < n && nums[i] == target; ++i) {
        //     v[i] = true;
        //     --k;
        // }
        return dfs(0, nums, v, k, target);
    }

    bool dfs(int s, const vector<int> &A, vector<bool> &v, int k, int target) {
        if (s > target) return false;
        if (s == target) {
            s = 0;
            if (--k == 0) return true;
        }
        for (int i = 0; i < A.size(); ++i) {
            if (v[i] || s + A[i] > target) continue;
            v[i] = true;
            if (dfs(s + A[i], A, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

状态压缩dp O(n*2ⁿ) time O(2ⁿ) space
f[state]表示该state所指的这些数可以凑成多个和为target的partition外加一个和小于等于target的一部分，target是sum/k
s[state]为对应state所指的这些数构成的和
f[0] = true
对于每个state从小到大尝试加数看能不能凑成新的和为target的partition，即使不能凑成，能缩小gap也行，因为已知总和一定能被k和target整除

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (nums[n - 1] > target) return false;
        vector<int> s(1 << n);
        vector<bool> f(1 << n);
        f[0] = true;
        for (int state = 0; state < (1 << n); ++state) {
            if (!f[state]) continue;
            for (int i = 0; i < n; ++i) {
                int next = state | (1 << i);
                if (next != state && !f[next]) {
                    if (nums[i] <= target - s[state] % target) {
                        f[next] = true;
                        s[next] = s[state] + nums[i];
                    } else break;
                }
            }
        }
        return f[(1 << n) - 1];
    }
};

742. Closest Leaf in a Binary Tree

Posted on 2021-01-13 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

O(n) time O(n) space
跟863. All Nodes Distance K in Binary Tree类似
把树转成图再bfs找最近端点，如果只有k一个点，则图为空，返回k，如果k只有一个邻居且k不是根，则k一定是叶子，返回k，如果图中某个『最近』端点不是根，返回该点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findClosestLeaf(TreeNode* root, int k) {
        unordered_map<int, unordered_set<int>> g;
        createGraph(root, g);
        if (g.empty() || g[k].size() == 1 && root->val != k) return k; // 如果k自己是leaf那就是他自己
        queue<int> q;
        q.push(k);
        while (!q.empty()) {
            int p = q.front(); q.pop();
            if (g[p].empty() && root->val != p) return p; // 没有邻居说明之前邻居已经把它从我的邻居里删除，我是根或者叶，如果我不是根，则返回我
            for (auto n : g[p]) {
                q.push(n);
                g[n].erase(p); // 从邻居那移除我，防止邻居继续访问我
            }
        }
        return k;
    }

    void createGraph(TreeNode *root, unordered_map<int, unordered_set<int>> &g) {
        if (!root) return;
        if (root->left) {
            g[root->val].insert(root->left->val);
            g[root->left->val].insert(root->val);
            createGraph(root->left, g);
        }
        if (root->right) {
            g[root->val].insert(root->right->val);
            g[root->right->val].insert(root->val);
            createGraph(root->right, g);
        }
    }
};

962. Maximum Width Ramp

Posted on 2021-01-13 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

O(n) time O(n) space
小数在左边，大数在右边，对于右边每一个大数，尽可能找到左边第一个比大数小的数，所以在左边维护一个递减栈，所有可能的小数一定在这个栈里
greedy从后往前遍历每个数，对于每个数要找到从左边开始第一个不大于它的数，保存每个数字第一次出现的位置，而且依次只用保留最小的即可，比如[6, 0, 3]，只需要保存6和0即可，3在0的右边且大于0，则3永远不可能成为最优解，所以可以直接跳过

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        stack<int> s;
        int n = A.size();
        for (int i = 0; i < n; ++i) {
            if (s.empty() || A[s.top()] >= A[i]) {
                s.push(i);
            }
        }
        int res = 0;
        for (int i = n - 1; i > res; --i) {
            while (!s.empty() && A[s.top()] <= A[i]) {
                res = max(res, i - s.top());
                s.pop();
            }
        }
        return res;
    }
};

O(nlogn) time O(n) space

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        vector<int> v(n);
        iota(begin(v), end(v), 0);
        auto cmp = [&A](int i, int j){return A[i] < A[j] || A[i] == A[j] && i < j;};
        sort(begin(v), end(v), cmp);
        int mn = INT_MAX, res = 0;
        for (int i : v) {
            mn = min(mn, i);
            res = max(res, i - mn);
        }
        return res;
    }
};

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        auto cmp = [&A](int i, int j){return A[i] < A[j] || A[i] == A[j] && i < j;};
        set<int, decltype(cmp)> s(cmp);
        int n = A.size();
        for (int i = 0; i < n; ++i) {
            s.insert(i);
        }
        int mn = INT_MAX, res = 0;
        for (int i : s) {
            mn = min(mn, i);
            res = max(res, i - mn);
        }
        return res;
    }
};