[LeetCode] 529. Minesweeper

https://leetcode.com/contest/leetcode-weekly-contest-21/problems/minesweeper/

Solution:
This question is pretty straightforward. May consider the BSF strategy. (DSF also works, but usually the code length will be a little bit longer for "diffusion" problems in a 2D matrix). Also need a visit matrix to record the visiting status: for each element, if it has been visited(or pushed into a queue), then no more is needed. Without this visit matrix, infinity loop may occur. See code below:

Code:

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board.empty() || board.front().empty()) return board;
        int x=click[0], y=click[1];
        if(board[x][y]=='M'){
            board[x][y]='X';
            return board;
        }
        int m = board.size(), n = board.front().size();
        queue<pair<int, int>> q;
        vector<vector<bool>> visit(m, vector<bool>(n, true));
        q.push(make_pair(x, y));
        visit[x][y]=false;
        vector<vector<int>> d={{0,1},{1,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,0},{1,-1}};
        while(q.size()){
            pair<int, int> t=q.front();
            q.pop();
            int ct=0;
            for(auto a:d){
                int tx=t.first+a[0], ty=t.second+a[1];
                if(tx>=0&&tx<m&&ty>=0&&ty<n){
                    if(board[tx][ty]=='M') ++ct;
                }
            }
            if(ct==0) {
                board[t.first][t.second]='B';
                for(auto a:d){
                    int tx=t.first+a[0], ty=t.second+a[1];
                    if(tx>=0&&tx<m&&ty>=0&&ty<n){
                        if(visit[tx][ty]&&board[tx][ty]=='E') {
                            q.push(make_pair(tx, ty));
                            visit[tx][ty]=false;
                        }
                    }
                }
            }
            else board[t.first][t.second]=ct+'0';
        }
        return board;
    }
};

[LeetCode] 518. Coin Change 2

https://leetcode.com/problems/coin-change-2/?tab=Description

Solution:
This is one of the classical questions for dynamic programming. And it belongs to the complete 01 knapsack problem. Let's suppose dp[i][j] represents the number of ways to make up amount of j with 1 to ith coins. Then when we move onto the next coin, we have to make choice. If the denomination of the next coin larger than j, then we cannot use it; if smaller, we can use it. Thus, the transition formula is:
                       dp[i+1][j] = dp[i][j] + dp[i+1][j-v[i+1]]
The first term means the way without using the (i+1)th coin; and the second one means the way with using the (i+1)th coin. This equation can be further simplified into an one-dimensional vector,
                      dp[j] = dp[j] + dp[j-v[i+1]]
                  or, dp[j] += dp[j-v[i+1]]
 See code below.

Code:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(auto a:coins){
            for(int i=1; i<=amount; ++i){
                if(i>=a) dp[i] += dp[i-a];
            }
        }
        return dp[amount];
    }
};

[LeetCode] 517. Super Washing Machines

https://leetcode.com/contest/leetcode-weekly-contest-20/problems/super-washing-machines/

Solution:
To be honest, I don't exactly know how to solve this problem... Anyway, here I just post one answer that I obtained from the online contest submission from this author:
https://leetcode.com/tckwok0/

This solution looks like using idea of graph theory. When the number of the clothes is less than the average, (average-v[i]) clothes needs to be moved in; in the opposite, (v[i]-average) clothes needs to be moved out. If average == v[i], no net flux is needed.

If we scan the vector from the left to right, we can find the local flux needed to balance them. Since for every move, we can only adjust one clothes, the value of flux actually is the minimum number of move needed. The maximum of the local flux actually is then the minimum moves needed to guarantee the balancing of the whole vectors, which is the answer to this question.

Further thing: can we figure out each step of moving for the minimum move?

Code:

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int res = 0, n = machines.size(), sum = 0;
        for(auto a:machines) sum += a;
        if(sum%n) return -1;
        int ave = sum/n, s = 0;
        vector<int> outdegree(n, 0);
        for(int i=0; i<n; ++i){
            s += machines[i] - ave;
            if(s<0) {
                outdegree[i+1] -= s; 
                res = max(res, outdegree[i+1]);
            }
            else if(s>0) {
                outdegree[i] += s;
                res = max(res, outdegree[i]);
            }
        }
        return res;
    }
};   

[LeetCode] 525. Contiguous Array

https://leetcode.com/contest/leetcode-weekly-contest-20/problems/contiguous-array/

Solution:
The straightforward way is of O(n2) time complexity, which is not what the OJ wants. There are only two elements in the vectors: 0 and 1. So we can define one variable to record the number difference of 0 and 1: sum. When it is 0, --sum; and when it is 1, ++sum. A hashmap is needed to connect the sum to the current position from which we can calculate the length of the subarray with the same number of 0 and 1. Then we need find the one with the maximum length.

In short, we will use map[sum] = i to record the position of i when the difference of the 0's and 1's number is sum. When the same sum appears again, let's say at position of j, then the subarray between i and j must contain the same number of 0 and 1.

Further thinking: how about there are three different elements in the array, and ask for the maximum subarray with the same number of each of them?

Code:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0, sum = 0, n = nums.size();
        unordered_map<int, int> m;
        m[0] = 0;
        for(int i=0; i<n; ++i){
            if(nums[i] == 0) --sum;
            else ++sum;
            if(m.find(sum) != m.end()) res = max(res, i+1-m[sum]);
            else m[sum] = i+1;
        }
        return res;
    }
}; 
 
  

[leetcode] 322. Coin Change

https://leetcode.com/problems/coin-change/?tab=Description

Solution:
A good question for dynamic programming. It also belongs to 01 knapsack problem. Let's suppose dp[i] represents the minimum coins needed to make up the amount, then the transition formula will be
              dp[i] = min(dp[i], dp[i-c[j]] + 1),   c[j] <= i;

Some details for implementation:
1): dp[0] can be set as 0; since it means the minimum number of coins needed for 0 is 0, which is legal based on the definition of dp[0];
2): All the rest dp[i] can be set (as amount + 1) since if there's at least one way to make up the amount, then minimum coins needed will be no larger than amount itself, because the worst situation (or the largest) is there are coins with 1 as the denomination and it is the only way to make up the amount.
3): to speed up a little bit, we can sort the coins. For coins bigger than i, we can just ignore them.

Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        if(coins.empty()) return -1;
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for(int i=1; i<=amount; ++i){
            for(int j=0; j<coins.size(); ++j){
                if(i>=coins[j]){
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
                else break;
            }
        }
        return dp[amount]==amount + 1?-1:dp[amount];
    }
};    
 

[LeetCode] 387. First Unique Character in a String

https://leetcode.com/contest/warm-up-contest/problems/first-unique-character-in-a-string/

Solution:
This is an easy level question. We may use the hash map to count the time of appearances for  each element. Then find the first element with count number of 1 (or the total number of this kind of element is 1). Since all the letters are in lower case, we can use a 26-letter long vector, instead of a hashmap. See code below.

Code:

class Solution {
public:
    int firstUniqChar(string s) {
        int res = -1, n = s.size();
        vector<int> count(26, 0);
        for(auto a:s) ++count[a-'a'];
        for(int i=0; i<n; ++i){
            if(count[s[i]-'a'] == 1) {
                res = i;
                break;
            }
        }
        return res;
    }
};

[LeetCode] 386. Lexicographical Numbers

https://leetcode.com/contest/warm-up-contest/problems/lexicographical-numbers/

Solution:
The idea is to think in a "tree" like structure: the root is 0, then its leaves are from 1 to 9; then for the next layer, each element from the upper layer will has 10 leaves, respectively. For example, for 1 as the root, the 10 leaves for it will be 10, to 19; for 2 as the root, the 10 leaves will be 20 to 29; ... Then we just need to travel this "virtual tree" recursively by root-first and leaves-second way.

However, we may don't need to build a tree for this question, and we can do this in vector. But the idea is similar. Firstly, we will put 1-9 into the vector. Then we will iterate the vector from the beginning. For 1, we will add 10-19 after it; for 2, we will add 20-29 after it; ... Of course, all the newly added elements need to be no larger than n. See code below.

We can also use a queue structure to implement this. So the algorithm involved is some sort of BSF fashion. 

Code:

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        int l = min(n, 9);
        for(int i=1; i<=l; ++i) res.push_back(i);
        if(n>9){
            vector<int> t;
            int layer = 1;
            while(res.size()<n){
                 for(auto a:res){
                     t.push_back(a);
                     if(a>=layer && a*10<=n){
                         for(int j=0; j<=9; ++j){
                             int val = a*10 + j;
                             if(val<=n) t.push_back(val);
                             else break;
                         }
                     }
                 }
                 layer *=10;
                 res.clear();
                 res = t;
                 t.clear();
            }
        }
        return res;
    }
};

[LeetCode] 493. Reverse Pairs

https://leetcode.com/contest/leetcode-weekly-contest-19/problems/reverse-pairs/

Solution:

The straightforward way is of O(n2) time complexity, which is not accepted by the OJ. So we need to find a quicker way. One way is to sort the processed elements. The details are that we will start from the end of the original vector, then gradually built a sorted vector as the processing goes. For each later element in the original vector, we just need to find the index of the element whose double value is smaller than the target element. Because that we start with the end of the original vector, all the elements inside the sorted vector have larger index than the target element in the original vector. Since we will do this in a sorted vector, the time complexity can be O(ln n) by using standard binary search. After we know many elements satisfy the condition, we can insert the target element into the sorted vector in the right position. So it will be O(ln n) again. The overall time complexity is (nln n). We may also need to use long long to avoid possible overflow problem. See code below. 

There's maybe even faster way to do it, will update later. Stay tuned.

Code:

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int res = 0, n = nums.size();
        if(n<2) return res;
        vector<long long> v;
        v.push_back(2*(long long)nums[n-1]);
        for(int i=n-2; i>=0; --i){
            int ind1 = findP(v, (long long)nums[i]);
            res += ind1;
            int ind2 = findP(v, 2*(long long)nums[i]);
            v.insert(v.begin()+ind2, 2*(long long)nums[i]);
        }
        return res;
    }
private:
    int findP(vector<long long> &v, long long t){
        int left = 0, right = v.size();
        while(left<right){
            int mid = left + (right-left)/2;
            if(v[mid] < t) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

[LeetCode] 498. Diagonal traverse

https://leetcode.com/contest/leetcode-weekly-contest-18b/problems/diagonal-traverse/

Solution:
This question is pretty straightforward. So it is designed for implementation details, i.e. boundary conditions.

Code:

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.empty()||matrix.front().empty()) return res;
        int m = matrix.size(), n=matrix.front().size();
        for(int i=0; i<n+m-1; ++i){
            if(!(i%2)){//slop as 1;
                int x = min(i, m-1), y = i-x; //initial position;
                while(x>=0&&y<n) res.push_back(matrix[x--][y++]);
            }
            else{//slop as -1;
                int y = min(i, n-1), x = i-y;//initial position;
                while(x<m&&y>=0) res.push_back(matrix[x++][y--]);
            }
        }
        return res;
    }
};

[LeetCode] 508. Most Frequent Subtree Sum

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/most-frequent-subtree-sum/

Solution:
first step to find all the sums of the subtrees; then save the ones appearing mostly. So the first step is the key for this question.
Using the properties of Tree, we can recursively find the sums of all the subtrees in a "bottom-up" fashion. See code below.

Code:

/**
 * 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<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int count = -1;
        findFTS(root, 0, m, count);
        for(auto a:m){
            if(a.second == count)
                res.push_back(a.first);
        } 
        return res;
    }
private: 
    int findFTS(TreeNode *r, int s, unordered_map<int, int> &m, int &ct){
        if(!r) return 0;
        int lt = findFTS(r->left, s, m, ct);
        int rt = findFTS(r->right, s, m, ct);
        s = lt + rt + r->val;
        ++m[s];
        ct = max(ct, m[s]);
        return s;
    }
};

[LeetCode] 500. Keyboard Row

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/keyboard-row/

Solution:
may use a hashmap to label the letters in the same row. Also need to pay attention to the upper or lower letters.

Code:

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> res;
        string v1="qwertyuiop", v2="asdfghjkl", v3="zxcvbnm";
        unordered_map<char, int> m;
        for(auto a:v1) m[a]=0;
        for(auto a:v2) m[a]=1;
        for(auto a:v3) m[a]=2;
        for(auto a:words){
            if(a.size()){
                int t = -1;
                if(m.find(a.front())!=m.end()) t = m[a.front()];
                else t = m[(a.front()+32)];
                bool flag = true;
                for(auto b:a){
                    if((m.find(b)!=m.end()&&m[b]==t) || (m.find(b+32)!=m.end()&&m[b+32]==t)) continue;
                    else{
                        flag = false;
                        break;
                    }
                }
                if(flag) res.push_back(a);
            }
        }
        return res;
    }
};

[LeetCode] 502. IPO

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/ipo/

Solution:
The profits are the pure profits, which means the costs have already been taken into account. Since this question is looking for the maximum profit, we can first sort the projects based on their costs. In order to keep the information of the corresponding profits, we need a pair structure to connect them. Then for all the projects that are available right now(costs smaller than the capital in hand), we can choose the one with maximum profit. Then we need to update the capital, which will possible make more projects available (that were not previously.) Then we can repeat the above processes starting with find the maximum profit among the projects available, until reaching k projects or no more projects available.

Code:

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        int res = W, l = Profits.size();
        vector<pair<int, int>> v;
        for(int i=0; i<l; ++i) v.push_back(make_pair(Capital[i], Profits[i]));
        sort(v.begin(), v.end());
        priority_queue<int> q;//q.top() is the maximum;
        int i = 0;
        for(; i<l; ++i){
            if(v[i].first<=res) q.push(v[i].second);
            else break;
        }
        while(q.size()&&k){
            int t = q.top();
            q.pop();
            res +=t;
            --k;
            for(; i<l; ++i){
                if(v[i].first<=res) q.push(v[i].second);
                else break;
            }
        }
        return res;
    }
};