[LeetCode]: 549. Binary Tree Longest Consecutive Sequence II

https://leetcode.com/contest/leetcode-weekly-contest-27/problems/binary-tree-longest-consecutive-sequence-ii/

Solution:
This is an interesting question. Similar to the one asking for the longest path for a binary tree, but this question add another constrain: the longest consecutive sequence. For each treenode, we need to check its left and right child. For the question asking for the longest path, we just need to return the larger one of longest paths from the left and right sub-trees, and the final result will be the maximum of (left + right + 1). But for this question, we need to return two values: one is the larger one of the two possible longest increasing paths from the left and right sub-trees, and the other is the larger one of the two possible longest decreasing paths from the left and right sub-trees. Since when move up to the next level (bottom-up direction), the longest consecutive sequence will be the maximum of (the larger one of the two possible longest increasing paths (could from the left sub-tree or the right sub-tree) + the larger one of the two possible longest decreasing paths (from the opposite side to the sub-tree in the first term)  + 1). See the 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:
    int longestConsecutive(TreeNode* root) {
        int res = 0;
        find(root, res);
        return res;
    }
private:
    pair<int, int> find(TreeNode *r, int &res){
        if(!r) return make_pair(0, 0);
        pair<int, int> ra = find(r->left, res), rb = find(r->right, res);
        int a = 1, b = 1;
        if(r->left&&r->left->val+1==r->val) a = max(a, 1 + ra.first);
        if(r->right&&r->right->val+1==r->val) a = max(a, 1 + rb.first);
        if(r->left&&r->left->val-1==r->val) b = max(b, 1 + ra.second);
        if(r->right&&r->right->val-1==r->val) b = max(b, 1 + rb.second);
        res = max(res, a + b - 1);
        return make_pair(a, b);
    }
}; 

[LeetCode]: 327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum/#/description

Solution:
This is an interesting question. As stated in the introduction, the O(n2) method is not accepted. So we need to find a faster way. For this question, we are look for ranges that satisfy:
                          sum[i to j] = sum[0 to j] - sum[0 to i] >= lower; and
                          sum[i to j] = sum[0 to j] - sum[0 to i] <= upper
which can be further re-wrote as:
                         sum[0 to i] <= sum[0 to j] - lower; and
                         sum[0 to i] >= sum[0 to j] - upper.
Now it becomes clear that once we have sum[0 to i] where 0<=i<n (which can be obtained easily with O(n)), we can calculate the elements numbers by just looking the range of [sum[0 to j] - upper, sum[0 to j] - lower]. In order to avoid the re-counting, we can count the number of elements in the process of constructing the sorted array of sum[0 to i]. In this way, all the ranges found have at least one unique end. We also need to do the counting before inserting the element sum[0 to i] into the sorted array, to avoid the case that the sum[0 to i] locates just between [sum[0 to j] - upper, sum[0 to j] - lower]. (in this case, we will mistakenly count the elements by 1 more.)

Some details:
1):We also need to consider the sum[0 to i] itself, which can be elegantly solving by add a '0' element inside the sorted array in the beginning.
2): the long type can be used to avoid overflow problem.

The key point is by constructing a sorted array, the complexity can be reduced from O(n2) to O(nlnn). See code below:

Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0;
        int n = nums.size();
        if(n==0) return res;
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            int left = findLeftPosition(sums, sum-upper);
            int right = findRightPosition(sums, sum-lower);
            res += right - left;
            int ind = findLeftPosition(sums, sum);
            sums.insert(sums.begin()+ind, sum);
        }
        return res;
    }
private:
    int findLeftPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<a) left = m+1;
            else right = m;
        }
        return left;
    }
    int findRightPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<=a) left = m + 1;
            else right = m;
        }
        return left;
    }
};

The code can be further simplified by using lower_bound() and upper_bound() functions. See below: Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0, n = nums.size();
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            auto left = lower_bound(sums.begin(), sums.end(), sum-upper);
            auto right = upper_bound(sums.begin(), sums.end(), sum-lower);
            res += (int) (right - left);
            sums.insert(lower_bound(sums.begin(), sums.end(), sum), sum);
        }
        return res;
    }
}; 

[LeetCode]: 548. Split Array with Equal Sum

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/split-array-with-equal-sum/

Solution:
This question is not very difficult, but the brute force loop cannot pass the OJ. So we need to find some way to use the intermediate information which means the one we have already calculated. Since we have already calculated it, there's no need to calculate it again. Instead, we can use the result from the previous calculation directly. That is exactly what is called memorization. DP is the one of the most common ways of memorization. The key point is: can the question be divided into sub-questions? If the answer is yes, then we can apply memorization.

For this question, for example, suppose we have already calculated that sum[i], meaning sum from 0 to i, is NOT the place where we can split the array with equal sum as required by the question, then in the latter processing, once we meet with the same value (sum[ii] == sum[i]), we can directly make a negative judge. (if sum[ii] == sum[i], which means the sum from i+1 to ii-1 is 0, so if the final result for sum[ii] is yes, then sum[i] should be yes too. But it is not, so sum[ii] must be no.) A hash map is enough to do memorization. See the code below:

Code:

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sum;
        for(int i=0; i<n; ++i) i==0?sum.push_back(nums[i]):sum.push_back(nums[i] + sum[i-1]);
        unordered_map<int, bool> m;
        for(int i=0; i<n-1; ++i){
            if(m.find(sum[i]) == m.end()){
                for(int j=i+2; j<n-1; ++j){
                    if(sum[j]-sum[i+1]==sum[i]){
                        for(int k=j+2; k<n-2; ++k){
                            if(sum[k]-sum[j+1]==sum[i]&&sum[n-1]-sum[k+1]==sum[i]) return true;
                        }
                    }
                }
                m[sum[i]] = false;
            }
        }
        return false;
    }
};

[LeetCode]: 547. Friend Circles

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/friend-circles/

Solution:
Will use bsf strategy: once find an element with value of 1, put it into a queue; then check all its "neighbors" that are friends with at least one of people in the "element" inside the queue. If the neighbor has a value of 1, indicating they are friends, put it into the queue. After checking all the neighbors, pop out the initial element. Then repeat the above process from the front of the queue until no element left. This is exactly why it is called "Breath Search First". Now we find one circle. We can move on to the rest un-visited elements in the matrix. A visiting matrix is used to label the visiting status of each elements, to make sure each element can only be visited once.

So, the routine procedure for bsf:
1: need a queue;
2: need a visiting matrix for labeling the visiting status.

For this question, we can use the symmetry of the matrix, to make the code a little bit simpler. See code below:

Code:

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int res = 0, n = M.size();
        vector<vector<bool>> v(n, vector<bool>(n, true));
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<n; ++i){
            for(int j=i; j<n; ++j){
                if(M[i][j]==1&&v[i][j]){
                    q.push(tp(i, j));
                    v[i][j]=false;
                    while(q.size()){
                        tp t = q.front();
                        q.pop();
                        int x=t.first, y=t.second;
                        for(int k=0; k<n; ++k){
                            if(v[x][k]&&M[x][k]==1){
                                q.push(tp(x, k));
                                v[x][k]=false;
                            }
                            if(v[k][x]&&M[k][x]==1){
                                q.push(tp(k, x));
                                v[k][x]=false;
                            }
                            if(v[y][k]&&M[y][k]==1){
                                q.push(tp(y, k));
                                v[y][k]=false;
                            }
                            if(v[k][y]&&M[k][y]==1){
                                q.push(tp(k, y));
                                v[k][y]=false;
                            }
                        }
                    }
                    ++res;
                }
            }
        }
        return res;
    }
};  

[LeetCode]: 545. Boundary of Binary Tree

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/boundary-of-binary-tree/

Solution:
Need to get the left boundary, the right boundary, and the leaves. It is straightforward for the first two. For the last one, we need to the transverse of the tree. For simplicity, we can do it recursively. See code below:

/**
 * 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> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> l, res, r;
        if(!root) return l;
        l.push_back(root->val);
        TreeNode* p = root->left, *p1 = root->right;
        if(!p && !p1) return l;
        while(p){
            if(p->left || p->right) l.push_back(p->val);
            if(p->left) p = p->left;
            else p = p->right;
        }
        while(p1){
            if(p1->left || p1->right) r.push_back(p1->val);
            if(p1->right) p1 = p1->right;
            else p1 = p1->left;
        }
        help(res, root);
        reverse(res.begin(), res.end());
        while(res.size()){
            l.push_back(res.back());
            res.pop_back();
        }
        while(r.size()){
            l.push_back(r.back());
            r.pop_back();
        }
        return l;
    }
private:
    void help(vector<int> &r, TreeNode* t){
        if(!t) return;
        help(r, t->left);
        if(!t->left && !t->right) {
            r.push_back(t->val);
        }
        help(r, t->right);
    }
};

[LeetCode]: 546. Remove Boxes

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/remove-boxes/

Solution:
This question is not easy. May use the dsf strategy, but the brutal force one cannot pass the OJ. One way to optimize it is to use memorization of the intermediate states. The parameters for the states needs include the range, the number of repeated elements, and the earned points. The range needs two parameters: the left and right. So we need a three-dimensional array to represent the states, and the value of it will be earned points. Let us dp[l][r][ct] represent the highest points earned in the range of l to r, where l is the left boundary, r is the right boundary, and ct is the number of repeated elements. The we need to calculate dp[0][n-1][0].

We can first calculate the dp[l][r][ct] = dsf(l+1, r, 0) + (ct+1)*(ct+1), which is equivalent to separate the original array into the first element and the rest ones;
Then is the key part:  since we need to find the maximum, we need to loop the whole array, and when the same elements as the first element is found, the transition equation can be wrote:
                 dp[l][r][ct] = max(dp[l][r][ct], dsf(l+1, i-1, 0) + dsf(i, r, ct+1)),  when arr[l] == arr[i].
where i is between l+1 and r. The second term in the max() is to divide the array into two parts: the first one is from l+1 to i-1 with 0 repeated elements; the other is from i to r with ct+1 repeated elements so far (arr[l] == arr[i]). (or the l element is now adjacent with the ith element.)

In order to reduce the complexity of the dsf, we can assign some unique initial value to dp[l][r][ct], for example, a negative value. Then when the dp[l][r][ct] becomes positive, it means it has already been calculated. So we can just use the calculated results directly. This is exactly how memorization works. See code below for details:

Code:

const int N = 100;
int dp[N][N][N];

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        memset(dp, -1, sizeof(dp));
        return dsf(boxes, 0, n-1, 0);
    }

    int dsf(vector<int> &b, int l, int r, int ct){
        if(l>r) return 0;
        int t = dp[l][r][ct];
        if(t!=-1) return t;
        t = dsf(b, l+1, r, 0) + (ct+1)*(ct+1);
        for(int i=l+1; i<=r; ++i){
            if(b[i]==b[l]) t=max(t, dsf(b, l+1, i-1, 0) + dsf(b, i, r, ct+1));
        }
        return dp[l][r][ct]=t;
    }
};

[LeetCode]: 544. Output Contest Matches

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/output-contest-matches/

Solution:
This question is pretty straightforward: will used string vector to store the initial array, then gradually combine them by adding the first one with the last one, ... until only one array left. See code below: 

Code:

class Solution {
public:
    string findContestMatch(int n) {
        if(n<2) return"";
        vector<string> res;
        for(int i=1; i<=n; ++i){
            res.push_back(to_string(i));
        }
        while(res.size()>1){
            int t = res.size();
            for(int i=0;i<t/2; ++i){
                res[i] = '(' + res[i] + ',' + res.back() + ')';
                res.pop_back();
            }
        }
        return res[0];
    }
}; 

[LeetCode] 542. 01 Matrix

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/01-matrix/

Solution:
This question seems not hard, but it is not easy to pass the OJ. One way to do it is kind of brute force bfs: for each element, gradually expand the searching range step by step until find the 0 element. But it is not fast enough.

One way to improve it is to think it in an opposite way: starting from elements with 0 value. Then gradually expand it: the first layer of neighbors should be 1; then the next layer should be 2; ... It's kind of using memorization. See code below:

Code:

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        vector<vector<int>> res = matrix;
        if(!matrix.size() || !matrix.front().size()) return res;
        int m = matrix.size(), n = matrix.front().size();
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j]==0) q.push(tp(i, j));
                else res[i][j] = -1;
            }
        }
        vector<tp> d={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(q.size()){
            tp tt = q.front();
            int a = tt.first, b = tt.second;
            q.pop();
            for(auto t:d){
                int x = a + t.first, y = b + t.second;
                if(x>=0&&x<m&&y>=0&&y<n&&res[x][y]==-1){
                    res[x][y] = res[a][b] + 1;
                    q.push(tp(x,y));
                }
            }
        }
        return res;
    }
};

[LeetCode] 536. Construct Binary Tree from String

https://leetcode.com/contest/leetcode-weekly-contest-23/problems/construct-binary-tree-from-string/

Solution:
The basic idea is to form the root first; then form the left children; then the right one. So we will use recursion strategy. See code below:

Note: The description for this question is not very clear, for example: the meaning of the '-' (it means negative number actually), and also the number can be larger than 10...

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:
    TreeNode* str2tree(string s) {
        TreeNode* res;
        int n = s.size(), i = 0;
        if(n==0) return NULL;
        int flag = 1;
        if(s[i] == '-'){
            flag = -1;
            ++i;
        }
        if(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) {
            int t=0; 
            while(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) t = t*10 + (s[i++]-'0');
            res = new TreeNode(flag*t); 
        }
        if(i<n&&s[i]=='('){
            int t = 1, ct = i+1;
            while(t>0&&ct<n){
                if(s[ct]=='(') ++t;
                if(s[ct]==')') --t;
                ++ct;
            } 
            if(t==0)res->left = str2tree(s.substr(i+1, ct-i-1)); //left children;
            if(t==0&&ct<n&&s[ct]=='(')res->right = str2tree(s.substr(ct+1, n-ct-2));//right children;
        }
        return res;
    }
};

[LeetCode] 514. Freedom Trail

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/freedom-trail/

Solution:
Basically, there are two ways to switch into the target position. One is to from left to right; the other is the opposite direction. And we need to pick up the shorter one to continue. The difficult part is that there are duplicates in both the ring and key, so we need to try each of them, so we can use brute force DSF and then return the one with the shortest length. To reduce the time complexity, a hash map can be used to built up the relationship between the char in the key and the corresponding positions in the ring. See code below, (even though it is still too slow to pass the OJ)

Code:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m=ring.size(), n=key.size();
        if(!m || !n) return 0;
        int res = m*n;
        unordered_map<int, vector<int>> map;
        for(auto a: key){
            if(map.find(a-'a') == map.end()){
                for(int i=0; i<m; ++i){
                    if(ring[i]==a) map[a-'a'].push_back(i);
                }
            }
        }
        findDSF(ring, 0, key, 0, 0, map, res);
        return res;
    }
private:
    void findDSF(string r, int i, string key, int j, int l, unordered_map<int, vector<int>> &m, int &res){
        if(l>=res) return;
        if(j==key.size()){res = l; return;}
        for(auto k:m[key[j]-'a']){
            int t1 = abs(k-i), t = r.size(), t2 = t - t1;
            findDSF(r, k, key, j+1, l+min(t1, t2)+1, m, res);
        }
    }
}; 

Since the above brute force DSF cannot pass the OJ, we need to think about something else that is faster. DP is one choice. Let's use dp[i][j] represent the shortest length to match key [0, to i] and ring[0-j]. When key[i] == ring[j], 
                             

dp[i][j] = min(dp[i-1][k] + min steps from k to j)  for  all k (0<= k < ring.size())

The min steps from k to j can be obtained by comparing the two way mentioned above: one is from left to right; the other is the opposite way. And we need to choose the shorter one.
Some details for initialization:
1): the maximum steps will be the length of ring times the length of the key; (why? because this is the worst case: for every char in the key, we need to search the whole ring);
2): We can initialize the dp[i][j] with the maximum steps, since we are looking for minimum;
3): dp[0][0] can be set as 0, which is legal for empty ring and empty key.

Code:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m=ring.size(), n=key.size();
        if(!m || !n) return 0;
        int res = m*n;
        vector<vector<int>> dp(n+1, vector<int>(m, res));
        dp[0][0] = 0;
        for(int i=1; i<=n; ++i){
            for(int j=0; j<m; ++j){
                if(ring[j]==key[i-1]){
                    for(int k=0; k<m; ++k){
                        int t1 = abs(k-j), t2 = m-t1;//two ways from k to j;
                        dp[i][j]=min(dp[i][j], dp[i-1][k] + min(t1, t2) + 1); //+1 for the "click" step;
                        if(i==n) res = min(res, dp[i][j]);
                    }
                }
            }
        }
        return res;
    }
};

[LeetCode] 533. Lonely Pixel II

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/lonely-pixel-ii/

Solution:
First step need to scan the 2D matrix to figure out how many columns and rows having the N 'B'. And we can record the index into two vectors: one for the row collections; and the other for the column collection. Then for each column inside the column collection, we need to check the validity by going though the associated row to the 'B' element inside the column. If there's no same row existing in the previously row collection with N 'B', just go to the next column; if yes, we need to further check all the associated rows to the rest 'B' elements inside the same column. If all of them (associated rows) are the same, count +1; or, go to the next column. Finally, return count * N.

An alternative way is that when counting the columns, after knowing there's N 'B' elements, we can further make sure all the associated rows to the 'B' element inside the column are the same. If not, it is not necessary to keep it in the column collection. Then in the following step, we just need to make sure there's at least one row existing in the row collections matches the associated row to the 'B' element inside the column to be checked.

Code:

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        if(picture.empty() || picture.front().empty()) return 0;
        int res = 0;
        int m = picture.size(), n = picture.front().size();
        vector<int> v1, v2;
        for(int i=0; i<m; ++i){
            int t = 0;
            for(int j=0; j<n; ++j){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v1.push_back(i);
        }
        for(int j=0; j<n; ++j){
            int t = 0;
            for(int i=0; i<m; ++i){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v2.push_back(j);
        }
        for(int j=0; j<v2.size(); ++j){
            for(int i=0; i<m; ++i){
                if(picture[i][v2[j]] !='B') continue;
                if(picture[i][v2[j]]=='B'&&isV(picture, i, v1)){
                    vector<int> v3(1, i);
                    bool flag = true;
                    for(int k=0; k<m; ++k){
                        if(picture[k][v2[j]]=='B'&&!(isV(picture, k, v3))){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) ++res;
                }
                break;
            }
        }
        return res*N;
    }
private:
bool isV(vector<vector<char>> &p, int x, vector<int> &v1){
        for(int i=0; i<v1.size(); ++i){
            bool flag = true;
            for(int j=0; j<p.front().size(); ++j){
                if(p[v1[i]][j] != p[x][j]){
                    flag = false;
                    break;
                }
            }
            if(flag) return true;
        }
        return false;
    }
};

[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;
    }
};

[LeetCode] 499. The Maze II

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/the-maze-ii/

Solution:
will use DSF strategy. Use a bool flag to represent the status of the ball, true for stop and false for moving. The reason for distinguishing these two is that once it stops, it can move all the directions (if OK); but once it moves, it can only goes one direction (recorded in the trace string) until hits on the wall. And once the ball hits on the wall, there will be a switch between stop and move. In order to avoid duplicates, a visit vector is used to trace the visiting status of the ball positions only when it stops. For the smallest path, we will trace the steps needed. Once find the steps needed are larger than the one that have already been found, the recursion can return since it is not necessary. 

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        vector<string> ss;
        string s;
        vector<vector<bool>> visit(maze.size(), vector<bool>(maze.front().size(), true));
//label only when stop;
        visit[ball[0]][ball[1]] = false;
        int step = 0, l = 0;
        bool flag = true;//stop;
        findDSF(maze, ball[0], ball[1], hole, visit, s, ss, step, l, flag);
        if(ss.empty()) return "impossible";
        sort(ss.begin(), ss.end());
        return ss[0];
    }
private:
    void findDSF(vector<vector<int>> &m, int x, int y, vector<int> &h, vector<vector<bool>> &v, 
string s, vector<string> &ss, int step, int &l, bool flag){
        if(ss.size()&&step>l) return;//if more step needed, can give up;
        if(x==h[0] && y==h[1]){
            if(ss.empty() || step == l){ ss.push_back(s); l = step;}
            else{
                if(step<l){ ss.clear(); ss.push_back(s); l = step;}
            }
            return;
        }
        if(flag){//ball stops now, and is going to move;
            if(x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                flag = false;
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s+'u', ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = true;
            }
            if(x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                flag = false;
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s+'d', ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = true;
            }
            if(y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                flag = false;
                if((y+1==m.front().size()-1)||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag=true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s+'r', ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = true;
            }
           if(y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                flag = false;
                if((y-1==0)||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s+'l', ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = true;
            }
        }
        else{//ball is moving, and it may stop when hits on the wall;
            if(s.back()=='u'&&x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s, ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = false;
            }
            else if(s.back()=='d'&&x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s, ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = false;
            }
            else if(s.back()=='r'&&y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                if(y+1==m.front().size()-1||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag = true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s, ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = false;
            }
            else if(s.back() =='l'&&y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                if(y-1==0||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s, ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = false;
            }
            else return;
        }
    }
};

The code length is too long for DSF, and it should be shorter if using BSF. But we need to trace the path and steps too. So we need some data structure to connect the positions with the steps and paths. Pair structure (pair<int, string> is chosen for step and path, and positions can be represented by a two dimensional array. So the data structure overall looks like this: vector<vector<pair<int, string>>>.  The code below is based on BSF strategy.

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        pair<int, string> dp[30][30];
        int n=maze.size(), m=maze[0].size();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) dp[i][j]=make_pair(10000000,"");
        vector<int> dx={1, 0, 0, -1};
        vector<int> dy={0, -1, 1, 0};
        string c="dlru"; 
        queue<pair<int,int>> q;
        q.push(make_pair(ball[0],ball[1]));
        dp[ball[0]][ball[1]]=make_pair(0,"");
        while(q.size()){
            pair<int, int> t=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                pair<int, int> now=t;
                int v=0;
                while(1){
                    if(now.first==hole[0]&&now.second==hole[1])break;
                    pair<int, int> next=make_pair(now.first+dx[i],now.second+dy[i]);
                    if(next.first<0||next.second<0||next.first>=n||next.second>=m)break;
                    if(maze[next.first][next.second]==1)break;
                    v++;
                    now=next;
                }
                pair<int, string>tt=make_pair(dp[t.first][t.second].first+v,dp[t.first][t.second].second+c[i]);
                if(v&&dp[now.first][now.second]>tt){
                    dp[now.first][now.second]=tt;
                    q.push(now);
                }
            }
        }
        if(dp[hole[0]][hole[1]].first==10000000)return "impossible";
        return dp[hole[0]][hole[1]].second;
    }
};

[LeetCode] 495. Teemo Attacking

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/teemo-attacking/

Solution:
This question should be an easy level question. The only thing need to do is to compare the difference of the adjacent elements in the array with that of the duration time. If larger, then it will take duration time to recover; if smaller, it will take the difference.

Code:

class Solution {
public:
    int findPosisonedDuration(vector<int>& timeSeries, int duration) {
        int res = duration, l = timeSeries.size();
        if(l == 0) res = 0;
        for(int i=1; i<l; ++i){
            int t = timeSeries[i]-timeSeries[i-1];
            res += t>=duration?duration:t;
        }
        return res;
    }
};

[LeetCode] 501. Find Mode in Binary Tree

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/find-mode-in-binary-tree/
Find all the elements that appears mostly.

Solution:
Use a hashmap to count the time of duplicates. Then save the elements with the highest appearing time into the output.

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> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int ct = 0;
        findM(root, m, ct);
        for(auto a:m){
            if(a.second == ct) res.push_back(a.first);
        }
        return res;
    }
private:
    void findM(TreeNode* root, unordered_map<int, int> &m, int &c){
        if(!root) return;
        c = max(c, ++m[root->val]);
        findM(root->left, m, c);
        findM(root->right, m, c);
    }
};

[LeetCode] 316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Solution:
The hard part is the smallest in lexicographical order. So in addition to a hashmap, we also need an extra vector to label each elements for the status of visiting. First to count the appearance times for each letters in the input string. Then when scan the input string, for each new element, we need to compare it with the last letter in the output string. If the new element is smaller than the last letter in the string and also the counting for the last element is larger than 0 (which means there is still more than 0 elements in the rest part of the input string), we need to set the status of the last letter to be un-visited and remove it. Otherwise, we can add the new elements in the back of the output string and set the visiting status as true. See code below.

Code:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "0";
        vector<int> m(26, 0), visit(26, 0);
        for(auto a:s) ++m[a-'a'];
        for(auto a:s){
            int t = a-'a';
            --m[t];
            if(visit[t]) continue;
            while(a<res.back() && m[res.back()-'a']){
                visit[res.back()-'a'] = 0;
                res.pop_back();
            }
            res.push_back(a);
            visit[t] = 1;
        }
        return res.substr(1);
    }
}; 

Further thinking:
How about the largest lexicographical order?
Ans: set the res to be "~" or some others that are larger than 'z'; and then change the "a<res.back()" inside the while condition into "a>res.back()". Done.

http://www.cnblogs.com/grandyang/p/5085379.html

[LeetCode] 312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

Solution:
A very good question since that I have to change the way how I do analysis usually. Initially I started with to pick one element (k), then think about how to deal with the rest part. (I think this is may be the common way to think about this question, which will eventually lead to brute force DSF).

But if we change the way to think it a little bit, we will surprise ourselves (at least to me). Instead of picking up element k firstly, how about choose it at the end? Imagine we have elements array from i to j (we can put 1 at each end for boundary conditions). Let's use dp[i][j] represents the max we can get in this range, then dp[i][j] = max{dp[i][j], d[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]}, where i<= k <= j. The key point for understanding this is that we will pick element k as the end.  Amazing, isn't it?

Some details for implementation of dp:
From the transition equation, we can see that dp[i][j] will be calculated from dp[i][k-1] and dp[k+1][j], and k-1 < j and k+1 > i. This indicates that one possible way to do it is to start with larger i and smaller j.  And dp[1][n] is the final answer we need. (for i>j, dp[i][j] is apparently zero due to definition.)

Code:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int>(n+2,0));
        for(int i=n; i>=1; --i){
            for(int j=i; j<=n; ++j){
                for(int k=i; k<=j; ++k){
                    dp[i][j] = max(dp[i][j],  dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);
                }
            }
        }
        return dp[1][n];
    }
}; 

[LeetCode] 464. Can I Win

https://leetcode.com/problems/can-i-win/


Solution:
One of the important constrains is that each element can only be used once. Therefore, if we use dp strategy, we have to take it into account since it will change the "status" of the sub-questions.

We can use binary representation for the status of the element usage. For each element, if it is not used yet, its status is 1; once used, become 0. So there will be 2^n status in total, where n is the total number of elements.

In order to increase efficiency, we need memorization of the results for the status visited previously, which is a very common trick to short the running time. Since we have already calculated it, there's no need for re-calculation. For this question, we will use a hashmap for implementation.

Another parameter for each sub-status is the target value, and it will also changes (becomes smaller) as some elements is chosen. So here we will use a vector<unordered_map<int, bool> > structure to store the status information, to memorize both the target value and status information. The index of the vector will be used for the target value.

The two players in this game will always play optimally, so once there is one way that the second player cannot win, the first will win. If for all the possible ways, the second player can always win, then the first player have to lose. At this point, we will use dsf strategy for searching.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        vector<unordered_map<int, bool>> dp(d);
        int t = (1<<m) - 1;
        return canWin(m, d, dp, t);
    }
private:
    bool canWin(int m, int d, vector<unordered_map<int, bool>> &dp, int sta){
        if(dp[d-1].count(sta)) return dp[d-1][sta];
        for(int i=0; i<m; ++i){
            if((1<<i)&sta){// i element is not used.
                if(i+1>=d || !canWin(m, d-i-1, dp, sta^(1<<i))){
                    dp[d-1][sta] = true;
                    return true;
                }
            }
        }
        dp[d-1][sta] = false;//the second player always win.
        return false;
    }
}; 

After finishing this, also noticed that there are some other way for implementation, and here is one example with discussion:

https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation

"After solving several "Game Playing" questions in leetcode, I find them to be pretty similar. Most of them can be solved using the top-down DP approach, which "brute-forcely" simulates every possible state of the game.
The key part for the top-down dp strategy is that we need to avoid repeatedly solving sub-problems. Instead, we should use some strategy to "remember" the outcome of sub-problems."

"For this question, the key part is: what is the state of the game? Intuitively, to uniquely determine the result of any state, we need to know:

1. The unchosen numbers
2. The remaining desiredTotal to reach

A second thought reveals that 1) and 2) are actually related because we can always get the 2) by deducting the sum of chosen numbers from original desiredTotal.
Then the problem becomes how to describe the state using 1)."
(one of the equivalent ways to understand this is that if we know condition 1 (the unchosen numbers) only, then we can determine the state completely, since that every element can be only used once.)

So only one hashmap is enough to memorize the sub-status for choosing elements.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        unordered_map<int, bool> dp;
        return canWin(m, d, dp, 0);
    }
private:
    bool canWin(int m, int d, unordered_map<int, bool> &dp, int sta){
        if(dp.count(sta)) return dp[sta];
        for(int i=0; i<m; ++i){
            if(((1<<i)&sta)==0){
                if(i+1>=d || !canWin(m, d-i-1, dp, sta|(1<<i))){
                    dp[sta] = true;
                    return true;
                }
            }
        }
        dp[sta] = false;
        return false;
    }
};