Leetcode 301-400

301. Remove Invalid Parentheses (Hard)

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Input: "()())()"
Output: ["()()()", "(())()"]

思路

这里可以先数一遍已有的括号对，判断要删掉几个左括号和右括号，然后直接递归来做

判断是否valid，同样可以扫描一遍字符串来完成

void recursion(vector<string>& result, int start, string s, int cnt1, int cnt2) {
    if (cnt1 + cnt2 == 0) {
        int c1 = 0, c2 = 0;
        for (char c : s) {
            if (c == '(') c1 ++;
            else if (c == ')') {
                if (c1 > 0) c1 --;
                else c2 ++;
            }
        }
        if (c1 == 0 && c2 == 0) result.push_back(s);
        return;
    }
    for (int i = start; i < s.size(); i ++) {
        if (i > start && s[i] == s[i-1]) continue;
        char c = s[i];
        if (c == '(' && cnt1 > 0) recursion(result, i, s.substr(0, i) + s.substr(i+1), cnt1 - 1, cnt2);
        if (c == ')' && cnt2 > 0) recursion(result, i, s.substr(0, i) + s.substr(i+1), cnt1, cnt2 - 1);
    }
}
vector<string> removeInvalidParentheses(string s) {
    int cnt1 = 0, cnt2 = 0;
    for (char c : s) {
        if (c == '(') cnt1 ++;
        else if (c == ')') {
            if (cnt1 > 0) cnt1 --;
            else cnt2 ++;
        }
    }
    vector<string> result;
    recursion(result, 0, s, cnt1, cnt2);
    return result;
}

---

302. Smallest Rectangle Enclosing Black Pixels (Hard)

思路

二分搜索，这里将lambda传入参数，需要使用template

bool hasBlack(const vector<vector<char>>& image, int m, int d, int l, int r) {
    if (d == 0) {
        for (int i = l; i <= r; i ++)
            if (image[m][i] == '1') return true;
    } else {
        for (int i = l; i <= r; i ++)
            if (image[i][m] == '1') return true;
    }
    return false;
}
template <typename T>
int binSearch(const vector<vector<char>>& image, int l, int r, int d, int left, int right, T f) {
    while (l <= r) {
        int m = (l + r) / 2;
        if (hasBlack(image, f(m), d, left, right))
            l = m + 1;
        else
            r = m - 1;
    }
    return f(l - 1);
}
int minArea(vector<vector<char>>& image, int x, int y) {
    if (image.size() == 0 || image[0].size() == 0) return 0;
    int n = image.size(), m = image[0].size();
    int high = binSearch(image, 0, x, 0, 0, m - 1, [&x](int num){ return x - num; });
    int low = binSearch(image, x, n - 1, 0, 0, m - 1, [](int num) { return num; });
    int left = binSearch(image, 0, y, 1, high, low, [&y](int num){ return y - num; });
    int right = binSearch(image, y, m - 1, 1, high, low, [](int num){ return num; });
    return (right - left + 1) * (low - high + 1);
}

---

305. Number of Islands II (Hard)

并查集，哈希

class Solution {
using ull = unsigned long long;
public:
    ull find(const unordered_map<ull, ull>& dict, ull key) {
        while (dict.at(key) != key) key = dict.at(key);
        return key;
    }
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        if (m == 0 || n == 0) return {};
        vector<int> res;
        unordered_map<ull, ull> dict;
        ull N = max(n, m);
        vector<pair<int, int>> ds = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        int num = 0;
        for (auto v : positions) {
            ull key = N * v[0] + v[1];
            if (dict.count(key)) {
                res.push_back(num);
                continue;
            }
            dict[key] = key;
            num ++;
            for (auto p : ds) {
                int x = v[0] + p.first, y = v[1] + p.second;
                if (x < 0 || x >= m || y < 0 || y >= n) continue;
                ull tempKey = x * N + y;
                if (dict.count(tempKey)) {
                    ull val = find(dict, tempKey);
                    if (find(dict, key) != val) {
                        dict[find(dict, key)] = val;
                        num --;
                    }
                }
            }
            res.push_back(num);
        }
        return res;
    }
};

并查集，数组

class Solution {
public:
    int find(const vector<int>& dict, int key) {
        while (dict[key] != key) key = dict[key];
        return key;
    }
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        if (m == 0 || n == 0) return {};
        vector<int> area(n * m, -1);
        vector<int> res;
        vector<pair<int, int>> ds = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        int num = 0;
        for (auto v : positions) {
            int key = n * v[0] + v[1];
            if (area[key] == -1) {
                area[key] = key;
                num ++;
                for (auto p : ds) {
                    int x = v[0] + p.first, y = v[1] + p.second, idx = x * n + y;
                    if (x < 0 || x >= m || y < 0 || y >= n || area[idx] == -1) continue;
                    int parent = find(area, key);
                    int val = find(area, idx);
                    if (parent != val) {
                        area[parent] = val;
                        num --;
                    }
                }
            }
            res.push_back(num);
        }
        return res;
    }
};

---

307. Range Sum Query (Medium)

线段树

class NumArray {
private:
    int N = 1;
    vector<int> tree;
public:
    NumArray(vector<int>& nums) {
        while (N < nums.size()) N *= 2;
        tree.assign(2 * N, 0);
        for (int i = 0; i < nums.size(); i ++) tree[N + i] = nums[i];
        for (int i = N - 1; i >= 1; i --)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    void update(int i, int val) {
        int delta = val - tree[N + i];
        int l = 0, r = N - 1, root = 1;
        while (l <= r) {
            tree[root] += delta;
            if (l == r) break;
            int mid = (l + r) / 2;
            if (mid >= i) {
                root = 2 * root;
                r = mid;
            } else {
                root = 2 * root + 1;
                l = mid + 1;
            }
        }
    }
    int query(int rank, int l, int r, int i, int j) {
        if (rank >= 2 * N) return 0;
        if (l >= i && r <= j) return tree[rank];
        else if (l > j || r < i) return 0;
        else {
            int mid = (l + r) / 2;
            return query(2 * rank, l, mid, i, j) + query(2 * rank + 1, mid + 1, r, i, j);
        }
    }
    int sumRange(int i, int j) {
        return query(1, 0, N - 1, i, j); 
    }
};

树状数组

class NumArray {
public:
    vector<int> BIT;
    vector<int> nums;
    NumArray(vector<int>& nums) {
        this->nums.assign(nums.size(), 0);
        BIT.assign(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i ++) update(i, nums[i]);
    }
    void update(int i, int val) {
        int delta = val - nums[i];
        nums[i] = val;
        i++;
        for (; i <= nums.size(); i += i&-i) BIT[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i&-i) sum += BIT[i];
        return sum;
    }
    int sumRange(int i, int j) {
        return query(j + 1) - query(i);
    }
};

---

308. Range Sum Query 2D Mutable (Hard)

二维矩阵，支持范围和查询操作以及更新操作

树状数组

class NumMatrix {
private:
    vector<vector<int>> matrix;
    vector<vector<int>> bit;
    int M, N;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return;
        M = matrix.size();
        N = matrix[0].size();
        this->matrix.assign(M, vector<int>(N, 0));
        bit.assign(M + 1, vector<int>(N + 1, 0));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++)
                update(i, j, matrix[i][j]);
        }
    }
    void update(int row, int col, int val) {
        int delta = val - matrix[row][col];
        matrix[row][col] = val;
        for (int i = row + 1; i <= M; i += i&-i)
            for (int j = col + 1; j <= N; j += j&-j)
                bit[i][j] += delta;
    }
    int query(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i&-i)
            for (int j = col; j > 0; j -= j&-j)
                sum += bit[i][j];
        return sum;
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row2 + 1, col2 + 1) - query(row1, col2 + 1) \
            - query(row2 + 1, col1) + query(row1, col1);
    }
};

---

309. Best Time to Buy and Sell Stock with Cooldown (Medium)

n天股票数据，但卖股票后第二天不能买，求最大profit

思路

动归，dp[i]表示前i天最大profit，但不能i-1天卖，即保证第二天出现更大的price时可以直接加上去

• 当prices[i] > prices[i-1]时，直接在前一天的profit上加上prices[i]-prices[i-1]即可，因为如果前一天卖了，那么用今天的价格代替前一天卖的价格即可，如果前一天没有卖，那么i-1天买i天卖即可
• prices[i] <= prices[i-1]，和前两天做比较，是否能增加

再和包括前两天在内所有天的max值比较，取较大值

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) return 0;
    int result = 0;
    vector<int> dp(prices.size(), 0);
    dp[1] = (prices[1] > prices[0]) ? prices[1] - prices[0] : 0;
    if (prices.size() == 2) return dp[1];
    int mx = dp[0];
    for (int i = 2; i < prices.size(); i ++) {
        if (prices[i-1] < prices[i])
            dp[i] = dp[i-1] + prices[i] - prices[i-1];
        else
            dp[i] = dp[i-2] + ((prices[i-2] <= prices[i]) ? prices[i] - prices[i-2] : 0);
        dp[i] = max(dp[i], mx);
        mx = max(mx, dp[i-1]);
    }
    return max(mx, dp[dp.size()-1]);
}

思路二

buy表示最后一次操作为买时的收益，sell表示最后一次操作为卖时的收益

• buy[i] = max(sell[i-2] - price, buy[i-1])
• sell[i] = max(buy[i-1] + price, sell[i-1])

遇到动归问题时，不妨先把数组开多一些，把问题描述清楚

int maxProfit(vector<int>& prices) {
    int buy = INT_MIN, pre_buy = 0, sell = 0, pre_sell = 0;
    for (int price : prices) {
        pre_buy = buy;
        buy = max(pre_sell - price, pre_buy);
        pre_sell = sell;
        sell = max(pre_buy + price, pre_sell);
    }
    return sell;
}

---

312. Burst Balloons (Hard)

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

思路

和矩阵链乘法思路一样，$dp[i,j]$表示从i-j气球戳破所得最大分数，这里要注意的是，分割时k表示最后一个戳破的气球，因此分数是和前后相乘再加起来

为了计算方便，将dp开成$(n+2) \times (n+2)$的vector

int maxCoins(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    int n = nums.size();
    vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0));
    for (int l = 1; l <= n; l ++) {
        for (int i = 1; i <= n-l+1; i ++) {
            int j = i + l - 1;
            int mx = 0;
            for (int q = i; q <= j; q ++)
                mx = max(dp[i][q-1] + dp[q+1][j] + ((i>1)?nums[i-2]:1)*nums[q-1]*((j<n)?nums[j]:1), mx);
            dp[i][j] = mx;
        }
    }
    return dp[1][n];
}

---

316. Remove Duplicate Letters (Hard)

给一个只包含小写字母的字符串，去除其中重复的字母，返回字典序最小值

Input: "bcabc"
Output: "abc"
Input: "cbacdcbc"
Output: "acdb"

思路

自己一开始又想太复杂了，想把每个字母出现的位置罗列一下，然后每次从中选取某个合适的值加入，这其实不是算法思路，从中选取合适值加入这个操作就很难

然后自己想到可以以每个字母最后出现位置，然后加上前面可能出现的最小排列，这样是可以做，但是细节很多，WA了好多次才改对，代码很繁琐

但其实可以用同样思路，直接对整个字符串进行操作，维护一个最小字符串即可，将更多的细节逻辑消除掉，交给数据结构解决，这才是算法题的正确思路

如下，在加入一个字符时，如果当前字符串末尾字符在后面还会出现，而且大于该字符，就清除这些字符，同时记录已经在字符串中的字符，如果已经在里面，不做操作

对于这类问题，可以从复杂度来入手，如果有感觉是线性解法，那就尝试着来线性思考，在扫过一段后，前面需要维护什么数据，然后当前如何更新这个维护的数据，最后如何返回结果，这样思考更利于解答

string removeDuplicateLetters(string s) {
    string res = "";
    vector<int> visit(256, 0);
    vector<int> cnt(256, 0);
    for (char c : s) cnt[c] ++;
    for (char c : s) {
        cnt[c]--;
        if (visit[c]) continue;
        while (!res.empty() && cnt[res.back()] > 0 && res.back() > c) {
            visit[res.back()] = 0;
            res.pop_back();
        }
        res += c;
        visit[c] = 1;
    }
    return res;
}

---

317. Shortest Distance from All Buildings (Hard)

一个二维矩阵，取值为0 1 2，0代表空地，1代表城市，2代表障碍，现在要在空地新建一个城市，要求选一个到各城市距离和最小的位置

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0
Output: 7 

思路

从各个城市开始进行宽搜，各空地的距离和累加，再找出距离和最短的空地位置即可

需要注意的是要保证空地的距离和是所有城市之和，这里另开一个二维数组，完成一次bfs后更新搜到的空地位置上的值，以此进行判断

int shortestDistance(vector<vector<int>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return 0;
    int num = 0;
    vector<vector<int>> dist(grid.size(), vector<int>(grid[0].size(), 0));
    for (int i = 0; i < grid.size(); i ++) {
        for (int j = 0; j < grid[0].size(); j ++) {
            if (grid[i][j] == 1) {
                dfs(grid, dist, i, j, num);
                num --;
            }
        }
    }
    int mn = -1;
    for (int i = 0; i < dist.size(); i ++) {
        for (int j = 0; j < dist[0].size(); j ++) {
            if (grid[i][j] == num)
                mn = mn == -1 ? dist[i][j] : min(mn, dist[i][j]);
        }
    }
    return mn;
}
void dfs(vector<vector<int>>& grid, vector<vector<int>>& dist, int i, int j, int num) {
    vector<vector<int>> step = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    deque<vector<int>> q = {{i, j}};
    int distance = 0;
    while (!q.empty()) {
        distance ++;
        int size = q.size();
        while (size --) {
            auto& node = q.front();
            for (auto d : step) {
                int newi = node[0] + d[0], newj = node[1] + d[1];
                if (newi < 0 || newi >= grid.size() || newj < 0 || newj >= grid[0].size()) continue;
                if (grid[newi][newj] == num) {
                    grid[newi][newj] --;
                    dist[newi][newj] += distance;
                    q.push_back({newi, newj});
                }
            }
            q.pop_front();
        }
    }
}

---

322. Coin Change (Medium)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

思路

dp来做，注意amount可能是0，以及coin数可能特别大超出amount需要做判断

vector的dp时间为48ms，改为int*时间为40ms

int coinChange(vector<int>& coins, int amount) {
    if (amount == 0) return 0;
    int *dp = new int[amount + 1]();
    for (int c : coins) 
        if (c <= amount) dp[c] = 1;
    for (int i = 0; i <= amount; i ++) {
        if (dp[i] == 0) continue;
        for (int c : coins) {
            if (c > amount || i + c > amount) continue;
            if (dp[i + c] == 0) dp[i + c] = dp[i] + 1;
            else dp[i + c] = min(dp[i+c], dp[i] + 1);
        }
    }
    return (dp[amount] == 0) ? -1 : dp[amount];
}

---

337. House Robber III (Medium)

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Input: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

思路

递归来做，重要的是如何减少递归次数，如果每个点抢不抢都递归的话，次数为$2^N$，太多

以下写法可以只递归$N$次，重点是一次运行除过返回该点最大值，还返回左右孩子最大值

int recursion(TreeNode *root, int &l, int &r) {
    if (root == nullptr) return 0;
    int ll = 0, lr = 0, rl = 0, rr = 0;
    l = recursion(root->left, ll, lr);
    r = recursion(root->right, rl, rr);
    return max(root->val + ll + lr + rl + rr, l + r);
}
int rob(TreeNode* root) {
    int l = 0, r = 0;
    return recursion(root, l ,r);
}

---

338. Counting Bits (Medium)

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Input: 2
Output: [0,1,1]

思路

vector每次加倍，并且加一即可

vector<int> countBits(int num) {
    vector<int> result = {0};
    while (result.size() <= num) {
        int size = result.size();
        for (int i = 0; i < size && result.size() <= num; i ++) result.push_back(result[i] + 1);
    }
    return result;
}

---

347. Top K Frequent Elements (Medium)

Given a non-empty array of integers, return the k most frequent elements.

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

解法一 优先级队列

map来记录每个数出现次数，然后用优先级队列来排列pair

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> m;
    priority_queue<pair<int, int>> q;
    vector<int> res;
    for (auto a : nums) ++m[a];
    for (auto it : m) q.push({it.second, it.first});
    for (int i = 0; i < k; ++i) {
        res.push_back(q.top().second); q.pop();
    }
    return res;
}

解法二 桶排序

同样用map来记录每个数出现次数，然后直接按次数插入到对应桶中

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> m;
    vector<vector<int>> bucket(nums.size() + 1);
    vector<int> res;
    for (auto a : nums) ++m[a];
    for (auto it : m) {
        bucket[it.second].push_back(it.first);
    }
    for (int i = nums.size(); i >= 0; --i) {
        for (int j = 0; j < bucket[i].size(); ++j) {
            res.push_back(bucket[i][j]);
            if (res.size() == k) return res;
        }
    }
    return res;
}

---

378. Kth Smallest Element in a Sorted Matrix (Medium)

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

思路

二分查找，巧妙之处在于用值的二分而不是用rank的二分，这样其实也是可以很快完成

具体来说，一开始可以知道最小元素(左上角)和最大元素(右下角)，然后以此为界开始二分，每次得到mid后统计矩阵中小于该值的元素个数num，如果num小于k，则l要增大，大于等于，则r置为m

这样反复操作，过程中l一直在target左边或重合，r一直在右边或重合，直到最后重合为止

统计比value小的数目，可以借助矩阵特性，从右上角开始统计，如果统计到matrix[i][j]大于value，那么matrix[i'>i][j]也都大于value，所以将j左移即可也不用复位，即可以在2n时间内得到统计出结果，每次j左移若干位或者i下移一位

算法复杂度为$O(nlogv)$，v是最大值-最小值的范围

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size(), l = matrix[0][0], r = matrix.back().back();
    while (l < r) {
        int mid = l + (r - l) / 2;
        int i = 0, j = n - 1;
        int num = 0;
        while (i < n && j >= 0) {
            while (j >= 0 && matrix[i][j] > mid) j --;
            num += (j + 1);
            i ++;
        }
        if (num < k) l = mid + 1;
        else r = mid;
    }
    return l;
}

---

394. Decode String (Medium)

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

思想

用栈来记录num和在[前出现的字符串，然后维护一个变量记录之后要重复的串，如果num栈为空，那么将已有串加到结果上

string decodeString(string s) {
    stack<int> nums;
    stack<string> strs;
    string temp = "";
    string result = "";
    int times = 0;
    for (char c : s) {
        if (c <= '9' && c >= '0') times = times * 10 + (c - '0');
        else if (c == '[') {
            nums.push(times);
            times = 0;
            strs.push(temp);
            temp = "";
        } else if (c == ']') {
            int t = nums.top();
            nums.pop();
            string ts = strs.top();
            strs.pop();
            for (int i = 0; i < t; i ++) ts += temp;
            temp = ts;
            if (nums.size() == 0) {
                result += temp;
                temp = "";
            }
        }
        else temp += c;
    }
    return result + temp;
}