Posted on | In , |
Words count in article: 235 | Reading time ≈ 1

790. Domino and Tromino Tiling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.

XX  <- domino

XX  <- "L" tromino
X
Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:
Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:

N  will be in range [1, 1000].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numTilings(int N) {
        long long MOD = 1e9+7;
        vector<vector<long long>> dp(1005, vector<long long>(4, 0));
        dp[1][0] = 1;
        dp[1][3] = 1;
        
        for(int i=2; i<=N; i++){
            dp[i][0] = dp[i-1][3];
            dp[i][1] = (dp[i-1][0] + dp[i-1][2])%MOD;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1])%MOD;
            dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3])%MOD; 
        }
        
        return dp[N][3];
    }
};

Posted on | In , |
Words count in article: 412 | Reading time ≈ 2

1287. Element Appearing More Than 25% In Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int a[100005] = {0};
        for(int i=0; i<arr.size(); i++){
            a[arr[i]]++;
            if(a[arr[i]] >= arr.size()/4+1)
                return arr[i];
        }
        return 0;
    }
};

1288. Remove Covered Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int count = intervals.size();
        int cur_left = intervals[0][0];
        int cur_right_max = intervals[0][1];
        for(auto i=intervals.begin()+1; i!=intervals.end(); ){
            if((*i)[1] <= cur_right_max){
                i = intervals.erase(i);
                count--;
                continue;
            }
            if((*i)[1] > cur_right_max){
                cur_right_max = (*i)[1];
                i++;
                continue;
            }
        }
        return count;
    }
};

1286. Iterator for Combination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class CombinationIterator {
public:
    vector<string> ret;
    int size;
    CombinationIterator(string ch, int Len) {
        string t = "";
        dfs(ch, 0, 0, Len, t);
        size = 0;
        //sort(ret.begin(), ret.end());
        //for(auto i: ret) cout << i << endl;
    }
    
    void dfs(string ch, int curi, int cur_size, int Len, string cur_str){
        if(Len == cur_size){
            ret.push_back(cur_str);
            return;
        }
        else if(ch.size() - curi + cur_size < Len) return;
        else if(curi >= ch.size()) return;
        for(int i=curi; i<ch.size(); i++){
            dfs(ch, i+1, cur_size+1, Len, cur_str + ch[i]);
        }
    }
    
    string next() {
        string r = ret[size++];
        return r;
    }
    
    bool hasNext() {
        return !(size == ret.size());
    }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

1289. Minimum Falling Path Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int dp[205][205];
    
    int dfs(vector<vector<int>>& arr, int i, int j){
        if(i == arr.size()) return 0;
        if(dp[i][j] != INT_MIN) return dp[i][j];
        int ans = INT_MAX;
        for(int cc=0; cc<arr.size(); cc++){
            if(cc == j) continue;
            ans = min(ans, dfs(arr, i+1, cc)+arr[i][cc]);
        }
        return dp[i][j] = ans;
    }
    
    int minFallingPathSum(vector<vector<int>>& arr) {
        for(int i=0; i<205; i++){
            for(int j=0; j<205; j++)
                dp[i][j] = INT_MIN;
        }
        int ret =  dfs(arr, 0, arr[0].size());
        return ret;
    }
};

Posted on | In , |
Words count in article: 590 | Reading time ≈ 3

1290. Convert Binary Number in a Linked List to Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ret = 0;
        ListNode* cur = head;
        while(cur != NULL){
            ret = ret * 2 + cur->val;
            cur = cur->next;
        }
        return ret;
    }
};

1291. Sequential Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ret;
        queue<int> q;
        for(int i=1; i<=9; i++)
            q.push(i);
        
        while(!q.empty()){
            int f = q.front();
            q.pop();
            
            if(f >= low && f <= high){
                ret.push_back(f);
            }
            if(f > high) break;
            if(f % 10 != 9){
                q.push(f*10 + f%10 + 1);
            }
        }
        return ret;
    }
};

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int target) {
        int max_len = 0;
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[0].size(); j++){
                if(mat[i][j] > target) continue;
                int cur_sum = 0;
                int cur_len = 1;
                while(true){
                    cur_sum = 0;
                    if(i+cur_len > mat.size()) {cur_len--; break;}
                    if(j+cur_len > mat[0].size()) {cur_len--; break;}
                    for(int ii=i; ii<i+cur_len; ii++){
                        for(int jj=j; jj<j+cur_len; jj++){
                            cur_sum += mat[ii][jj]; 
                        }
                    }
                    //cout << i << " "  << j << " " << mat[i][j] << " " << cur_sum << endl;
                    if(cur_sum < target){
                        cur_len++;
                    }else if(cur_sum == target){
                        break;
                    }else{
                        cur_len--; break;
                    }
                }
                //cout << i << " "  << j << " " << cur_len << endl;
                max_len = max_len > cur_len ? max_len : cur_len;
            }
        }
        return max_len;
    }
};

1293. Shortest Path in a Grid with Obstacles Elimination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int dp[41][41][1601];
    bool vis[41][41];
    int f(vector<vector<int>>& grid, int i, int j, int k){
        int n = grid.size(), m = grid[0].size();
        if(k < 0) return 1e7;
        if(i == n-1 && j == m-1) return 0;
        if(i < 0 || i >= n || j < 0 || j >= m) return 1e7;
        if(dp[i][j][k] != -1) return dp[i][j][k];
        int ans = 1e7;
        if(vis[i][j]) return ans;
        vis[i][j] = 1;
        vector<int> dx = {0, 1, 0, -1};
        vector<int> dy = {1, 0, -1, 0};
        for(int l=0; l<4; l++){
            int x = i+dx[l];
            int y = j+dy[l];
            if(x >= 0 && x < n && y >= 0 && y < m){
                int nk = k;
                if(grid[x][y] == 1) nk--;
                if(nk >= 0) ans = min(ans, f(grid, x, y, nk)+1);
            }
        }
        vis[i][j] = 0;
        return dp[i][j][k] = ans;
    }
    int shortestPath(vector<vector<int>>& grid, int k) {
        memset(dp, -1, sizeof(dp));
        if(grid[0][0] == 1) k--;
        memset(vis, false, sizeof(vis));
        int ans = f(grid, 0, 0, k);
        if(ans >= 1e7) return -1;
        return ans;
    }
};

Posted on | In , |
Words count in article: 608 | Reading time ≈ 3

1281. Subtract the Product and Sum of Digits of an Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int subtractProductAndSum(int n) {
        int sum = 0;
        int time = 1;
        while(n){
            sum += n % 10;
            time *= n % 10;
            n /= 10;
        }
        return  time-sum;
    }
};

1282. Group the People Given the Group Size They Belong To

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct node{
    int index;
    int key;
};

bool cmp(node& a, node&b){
    return a.key < b.key;
}

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ret;
        vector<node> arr;
        for(int i=0; i<groupSizes.size(); i++){
            node rem;
            rem.index = i;
            rem.key = groupSizes[i];
            arr.push_back(rem);
        }
        sort(arr.begin(), arr.end(), cmp);
        int cur_max = arr[0].key;
        int cur = 0;
        vector<int> tmp;
        for(int i=0; i<arr.size(); i++){
            if(cur == cur_max){
                cur_max = arr[i].key;
                cur = 0;
                ret.push_back(tmp);
                tmp.resize(0);
            }
            tmp.push_back(arr[i].index);
            cur++;
            if(i == arr.size()-1){
                ret.push_back(tmp);
            }
        }
        return ret;
    }
};

1283. Find the Smallest Divisor Given a Threshold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestDivisor(vector<int>& A, int threshold) {
        int left = 1, right = 1e6, m, sum;
        while(left < right){
            m = (left + right) / 2, sum = 0;
            for(int i: A)
                sum += (i + m - 1) / m;
            if(sum > threshold)
                left = m + 1;
            else
                right = m;
        }
        return left;
    }
};

1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    string toString(vector<vector<int>>& mat){
        string result="";
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[i].size(); j++){
                result += to_string(mat[i][j])+",";
            }
        }
        return result;
    }
    int minFlips(vector<vector<int>>& mat) {
        deque<vector<vector<int>>> q={mat};
        unordered_set<string> v = {toString(mat)};
        int c = 0;
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        int f = 0;
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[i].size(); j++)
                if(mat[i][j] == 1) f = 1;
        }
        if(f == 0) return 0;
        while(q.size() > 0){
            int s = q.size();
            c++;
            for(int i=0; i<s; i++){
                vector<vector<int>> p = q.front();
                q.pop_front();
                vector<vector<int>> temp = p;
                for(int j=0; j<temp.size(); j++){
                    for(int k=0; k<temp[j].size(); k++){
                        temp[j][k]^=1; //flip 0 to 1, 1 to 0
                        for(int d=0;d<4;d++)
                        {
                            int x=j+dx[d];
                            int y=k+dy[d];
                            if(x>=0&&x<temp.size()&&y>=0&&y<temp[0].size()) temp[x][y]^=1;
                        }
                        
                        string output=toString(temp);
                        if(v.find(output)==v.end()) //if not visited yet
                        {
                            int f=0; //check if all 0s
                            for(int c1=0;c1<temp.size();c1++)
                                for(int c2=0;c2<temp[c1].size();c2++)
                                    if(temp[c1][c2]==1) f=1;

                            if(f==0) return c;
                            q.push_back(temp);
                            v.insert(output);
                        }
                        temp=p; //restore the matrix after flipping
                    }
                }
            }
        }
        return -1;
    }
};

Posted on | In , |
Words count in article: 625 | Reading time ≈ 3

1275. Find Winner on a Tic Tac Toe Game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int count = 0;
        int map[3][3] = {0};
        // A : 1 , B : -1
        int cur = 1;
        for(auto& m : moves){
            if(count == 9){
                return "Draw";
            }
            map[m[0]][m[1]] = cur;
            if(map[0][0]==cur && map[0][1]==cur && map[0][2]==cur) return cur == 1 ? "A" : "B";
            if(map[1][0]==cur && map[1][1]==cur && map[1][2]==cur) return cur == 1 ? "A" : "B";
            if(map[2][0]==cur && map[2][1]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[0][0]==cur && map[1][0]==cur && map[2][0]==cur) return cur == 1 ? "A" : "B";
            if(map[0][1]==cur && map[1][1]==cur && map[2][1]==cur) return cur == 1 ? "A" : "B";
            if(map[0][2]==cur && map[1][2]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[0][0]==cur && map[1][1]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[2][0]==cur && map[1][1]==cur && map[0][2]==cur) return cur == 1 ? "A" : "B";
            cur *= -1;
            count++;
        }
        if(count == 9) return "Draw";
        else return "Pending";
    }
};

1276. Number of Burgers with No Waste of Ingredients

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> numOfBurgers(int tt, int cc) {
        // Jumbo Burger: 4 tomato slices and 1 cheese slice.
        // Small Burger: 2 Tomato slices and 1 cheese slice.
        vector<int> ret;
        int flag = 0;
        int i = 0;
        while(true){
            if(4 * i + (cc-i) * 2 == tt){
                ret.push_back(i);
                ret.push_back(cc-i);
                break;
            }
            if(i > cc) break;
            i++;
        }
        return ret;
    }
};

1277. Count Square Submatrices with All Ones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int ret = 0;
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                if(matrix[i][j] == 0) continue;
                ret++;
                int d = 1;
                while(true){
                    int ff = 1;
                    if(i + d >= matrix.size() || j + d >= matrix[0].size()) break;
                    for(int ii = i; ii <= i + d; ii++){
                        for(int jj = j; jj <= j + d; jj++){
                            if(matrix[ii][jj] != 1){
                                ff = 0;
                                break;
                            }
                        }
                    }
                    if(ff == 1) ret++;
                    else break;
                    d++;
                }
            }
        }
        return ret;
    }
};

1278. Palindrome Partitioning III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution 
{
    public:
    int moves(string s) //number of steps to make palindrome
    {
        int c=0;
        int p1=0;
        int p2=(int)s.length()-1;
        while(p1<p2)
        {
            if(s[p1]!=s[p2]) c++;
            p1++;
            p2--;
        }
        return c;
    }
    int dp(vector<vector<int>>& m,string& s,int l,int k) //l is the length of the string starting from 0, k is the number of partitions
    {
        if(m[l][k]!=2147483647) return m[l][k];
        if(k==1) m[l][k]=moves(s.substr(0,l));
        else for(int i=k-1;i<l;i++) m[l][k]=min(m[l][k],dp(m,s,i,k-1)+moves(s.substr(i,l-i)));
        return m[l][k];
    }
    int palindromePartition(string s, int k) 
    {
        int n=s.length();
        vector<vector<int>> m(n+1,vector<int>(k+1,2147483647));
        return dp(m,s,n,k);
    }
};

Posted on | In , |
Words count in article: 577 | Reading time ≈ 3

1271. Hexspeak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    string get_string_num(int a){
        if(a == 0)
            return "O";
        else if(a == 1)
            return "I";
        else if(a == 10)
            return "A";
        else if(a == 11)
            return "B";
        else if(a == 12)
            return "C";
        else if(a == 13)
            return "D";
        else if(a == 14)
            return "E";
        else if(a == 15)
            return "F";
        else
            return "X";
    }
    long long get_int_num(string num){
        long long ret = 0;
        for(int i=0; i<num.size(); i++){
            ret *= 10;
            ret += num[i]-'0';
        }
        return ret;
    }    
    string toHexspeak(string num) {
        string ret="";
        long long n = get_int_num(num);
        while(n){
            long long cur = n % 16;
            n /= 16;
            string cc = get_string_num(cur);
            if(cc == "X")
                return "ERROR";
            ret += cc;
        }
        string ret1 = "";
        for(int i=ret.size()-1; i>=0; i--){
            ret1 += ret[i];
        }
        return ret1;
    }
};

1272. Remove Interval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& t) {
        vector<vector<int>> ret;
        for(auto& a: intervals){
            if(a[0] >= t[0] && a[1] <= t[1])
                continue;
            else if(a[0] <= t[0] && a[1] <= t[1] && a[1] > t[0]){
                vector<int> cur;
                cur.push_back(a[0]);
                cur.push_back(t[0]);
                ret.push_back(cur);
            }
            else if(a[0] >= t[0] && a[0] < t[1] && a[1] >= t[1]){
                vector<int> cur;
                cur.push_back(t[1]);
                cur.push_back(a[1]);
                ret.push_back(cur);
            }
            else if(a[0] < t[0] && a[1] > t[1]){
                vector<int> cur1;
                cur1.push_back(a[0]);
                cur1.push_back(t[0]);
                ret.push_back(cur1);
                vector<int> cur2;
                cur2.push_back(t[1]);
                cur2.push_back(a[1]);
                ret.push_back(cur2);
            }
            else
                ret.push_back(a);
        }
        return ret;
    }
};

1273. Delete Tree Nodes

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int deleteTreeNodes(int n, vector<int>& parent, vector<int>& value) {
        vector<int> res(n);
        for(int i=n-1; i>0; --i){
            value[parent[i]] += value[i];
            res[parent[i]] += value[i] ? res[i] + 1 : 0;
        }
        return value[0] ? res[0] + 1 : 0;
    }
};

1274. Number of Ships in a Rectangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public:
 *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        return helper(sea, topRight[0], topRight[1], bottomLeft[0], bottomLeft[1]);
    }
    int helper(Sea& sea, int top, int right, int bottom, int left){
        int h = top-bottom;
        int w = right-left;
        
        if(!sea.hasShips({top, right},{bottom, left}))
            return 0;
        if(h == 0 && w == 0)
            return 1;
        if(h > w){
            int a = helper(sea, top, right, bottom+h/2+1, left);
            int b = helper(sea, bottom+h/2, right, bottom, left);
            return a + b;
        }
        else{
            int a = helper(sea, top, right, bottom, left+w/2+1);
            int b = helper(sea, top, left+w/2, bottom, left);
            return a + b;
        }
    }
};

Posted on | In , |
Words count in article: 302 | Reading time ≈ 1

You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

1
2
3
4
5
6
Example 1:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

  • One employee has at most one direct leader and may have several subordinates.
  • The maximum number of employees won’t exceed 2000.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        queue<int> qq;
        int ret = 0;
        qq.push(id);
        while(!qq.empty()){
            int cur_id = qq.front();
            qq.pop();
            for(auto& e: employees){
                if(e->id == cur_id){
                    ret += e->importance;
                    for(auto& i: e->subordinates){
                        qq.push(i);
                    }
                }
            }
        }
        return ret;
    }
};

Posted on | In , |
Words count in article: 457 | Reading time ≈ 2

1266. Minimum Time Visiting All Points

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int maxn = 0;
        for(int i=0; i<points.size()-1; i++){
            int maxx = abs(points[i][0]-points[i+1][0]);
            int maxy = abs(points[i][1]-points[i+1][1]);
            maxn += maxx > maxy ? maxx : maxy;
        }
        return maxn;
    }
};

1267. Count Servers that Communicate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int ret = 0;
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[0].size(); j++){
                if(grid[i][j] == 1){
                    int flag = 0;
                    // cout << i << " " << j << endl;
                    for(int x=0; x<grid[0].size(); x++){
                        if(grid[i][x] == 1 && x != j){
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 1){
                        ret ++;
                        continue;
                    }
                    for(int x=0; x<grid.size(); x++){
                        if(grid[x][j] == 1 && x != i){
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 1){
                        ret ++;
                        continue;
                    }
                }
            }
        }
        return ret;
    }
};

1268. Search Suggestions System

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& p, string src) {
        int m = src.size(), n = p.size();
        sort(p.begin(), p.end());
        vector<vector<string>> ret;
        vector<int> cnt;
        for(string t : p){
            int i = 0;
            for(i = 0; i < src.size() && i < t.size() && src[i] == t[i]; i++);
            cnt.push_back(i);
        }
        for(int i=0; i<m; i++){
            vector<string> v;
            for(int j=0; j<n; j++){
                if(cnt[j] > i && v.size() < 3){
                    v.push_back(p[j]);
                }
            }
            ret.push_back(v);
        }
        return ret;
    }
};

1269. Number of Ways to Stay in the Same Place After Some Steps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define ll long long int

class Solution {
public:
    ll dp[501][501];
    ll MOD = 1e9 + 7;
    
    ll f(int steps, int i, int len){
        if(i >= len || i < 0) return 0;
        if(steps == 0) return (i == 0);
        if(dp[steps][i] != -1) return dp[steps][i];
        ll op1 = f(steps-1, i+1, len) % MOD;
        ll op2 = f(steps-1, i-1, len) % MOD;
        ll op3 = f(steps-1, i, len) % MOD;
        return dp[steps][i] = (op1 + op2 + op3) % MOD;
    }
    
    int numWays(int steps, int arrLen) {
        memset(dp, -1, sizeof(dp));
        if(arrLen > steps) arrLen = steps;
        return (int)(f(steps, 0, arrLen) % MOD);
    }
};

Posted on | In , |
Words count in article: 841 | Reading time ≈ 5

Synchronization of Selling Tickets at the Window

1
2
3
4
5
6
7
8
package MultiThread;

public class Main {
	public static void main(String[] args) {
        Window w = new Window();
        w.window();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package MultiThread;

class Test  implements Runnable {
	private static int num = 1;
	int f = 0;
	
	@Override
	public void run() {
		while(true) {
			synchronized(this) {
				if(num <= 20) {
					System.out.println(Thread.currentThread().getName() + ": ticket " + num++);
					try {
	                    Thread.sleep(50);
	                } catch (InterruptedException e) {
	                    e.printStackTrace();
	                }
				}
				else {
					if(f == 0) {
						System.out.println("Sold Out");
						f = 1;
					}
					return;
				}
			}
		}
	}
	
}


public class Window {
	void window() {
		Test tr = new Test();
		Thread t1 = new Thread(tr, "Window 1");
        Thread t2 = new Thread(tr, "Window 2");
        Thread t3 = new Thread(tr, "Window 3");
        t1.start();
        t2.start();
        t3.start();
	}
}

Inter-Thread Synchronization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package MultiThread1;

class Test  implements Runnable {
	private static int aaa = 100;
	private static int bbb = 0;
	private static int ccc = 0;
	
	@Override
	public void run() {
		while(true) {
			synchronized(this) {
				if((Thread.currentThread().getName().equals("B") && bbb < 1000)||(Thread.currentThread().getName().equals("C") && ccc < 1000)) {
					aaa += 100;
					System.out.println("account "+Thread.currentThread().getName()+" transfer $100 to account A, balance of account A: $" + aaa);
					
					if(Thread.currentThread().getName().equals("B")) bbb+=100;
					else ccc+=100;
					
					try {
	                    Thread.sleep(50);
	                } catch (InterruptedException e) {
	                    e.printStackTrace();
	                }
				}
				else {
					if(bbb >= 1000 && ccc >= 1000){
						System.out.println("account B transfer $1000 to account A in total");
						System.out.println("account C transfer $1000 to account A in total");
						System.out.println("balance of account A: $2100");
					}
					return;
				}
			}
		}
	}
	
}

public class Bank {
	void bank(){
		System.out.println("balance of account A: $100");
		Test tr = new Test();
		Thread t1 = new Thread(tr, "B");
        Thread t2 = new Thread(tr, "C");
        t1.start();
        t2.start();
	}
}
1
2
3
4
5
6
7
8
package MultiThread1;

public class Main {
    public static void main(String[] args) {
        Bank b = new Bank();
        b.bank();
    }
}

Deadlock: Dining Philosopher Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package MultiThread2;

public class Customer extends Thread {
	Text text;

	Customer(Text text) {
	   this.text = text;
	}
	
	@Override
    public void run() {
		int i = 1;
	    while(true) {
	       text.Get(i++);
	       if(i > 10) return;
	    }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package MultiThread2;

class Text {
	int count = 0;
	
	synchronized void Set(int num) {
		while(count == 1) {
			try {
				wait();
			} catch (InterruptedException ie) {
				ie.printStackTrace();
				System.exit(0);
			}
		}
		int f = num % 2;
		if(f == 1) {
			System.out.println("Set "+ num +"-> Item1 : 12345");
		}else if(f == 0) {
			System.out.println("Set "+ num +"-> Item2 : abcde");
		}
		count = 1;
		notifyAll();
	}
	
	synchronized void Get(int num) {
		while(count == 0) {
			try {
				wait();
			} catch (InterruptedException ie) {
				ie.printStackTrace();
				System.exit(0);
			}
		}
		int f = num % 2;
		if(f == 1) {
			System.out.println("Get "+ num +"-> Item1 : 12345");
		}else if(f == 0) {
			System.out.println("Get "+ num +"-> Item2 : abcde");
		}
		count = 0;
		notifyAll();
	}
}


public class Master {
	void master(){
		Text text = new Text();
	    new Producer(text).start();
	    new Customer(text).start();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package MultiThread2;

public class Producer extends Thread {
	Text text;

	Producer(Text text) {
	   this.text = text;
	}
	
	@Override
    public void run() {
		int i = 1;
	    while(true) {
	       text.Set(i++);
	       if(i > 10) return;
	    }
    }
}
1
2
3
4
5
6
7
8
package MultiThread2;

public class Main {
	public static void main(String[] args){
        Master m = new Master();
        m.master();
    }
}

Deadlock: Dining Philosopher Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package Deadlock;

class MEN extends Thread{
    private String name;
    private Fork cur;
    public MEN(String name,Fork cur){
        super(name);
        this.name=name;
        this.cur=cur;
    }
    
    public void run(){
        while(true){
            thinking();
            cur.tryTodo();
            eating();
            cur.OverDo();
        }
    }
    
    public void eating(){
        System.out.println(name + " is eating.");
        try {
            sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    
    public void thinking(){
        System.out.println(name + " is thinking.");
        try {
            sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class Fork{
    private boolean[] flag = {false,false,false,false,false,false};
    
    public synchronized void tryTodo(){
        int i = Thread.currentThread().getName().charAt(3)-'0';
        int a = i, b = i+1; 
        if(b == 6) b = 1;
        while(flag[a]||flag[b]){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        flag[a]=true;  flag[b]=true;
    }
    
    public synchronized void OverDo(){
        int i = Thread.currentThread().getName().charAt(3)-'0';
        int a = i, b = i+1; 
        if(b == 6) b = 1;
        flag[a]=false;  flag[b]=false;
        System.out.println(Thread.currentThread().getName() + " is over eating.");
        notifyAll();
    }
}


public class Deadlock {
    public static void main(String []args){
        Fork cur = new Fork();
        // 1 2 3 4 5 -> 1
        for(int i=1; i<=5; i++)
        	new MEN("men" + i, cur).start();
    }
}

Posted on | In , |
Words count in article: 1.6k | Reading time ≈ 9

abstract class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package abstractclass;

public class Circle extends Shape{
	double radius;
	Circle(){
		super();
		this.radius = 0;
	}
	Circle(double r, String c, boolean f){
		super(c, f);
		this.radius = r;
	}
	Circle(double r){
		super();
		this.radius = r;
	}
	public double getRadius() {
		return this.radius;
	}
	
	@Override
	public double getArea() {
		return Math.PI * radius * radius;
	}
	
	@Override
	public double getPerimeter() {
		return Math.PI * 2 * radius;
	}
	
	public String toString() {
		return "A Circle with radius = " + radius + ", which is a subclass of " + super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package abstractclass;

public class Rectangle extends Shape{
	double width;
	double length;
	
	Rectangle(){
		super();
		this.width = 0;
		this.length = 0;
	}
	Rectangle(double w, double l, String c, boolean f){
		super(c, f);
		this.width = w;
		this.length = l;
	}
	Rectangle(double w, double l){
		super();
		this.width = w;
		this.length = l;
	}
	public double getWidth() {
		return this.width;
	}
	
	public double getLength() {
		return this.length;
	}
	
	@Override
	public double getArea() {
		return width * length;
	}
	
	@Override
	public double getPerimeter() {
		return 2*(width + length);
	}
	
	public String toString() {
		return "A Rectangle with width = "+width+" and length = "+length+", which is a subclass of "+ super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package abstractclass;

public abstract class Shape {
	protected String color;
	protected boolean filled;
	
	Shape(){
		this.color = "red";
		this.filled = true;
	}
	
	Shape(String c, boolean f){
		this.color = c;
		this.filled = f;
	}
	
	public String getColor() {
		return color;
	}
	
	public boolean isFilled() {
		return filled;
	}
	
	public String toString() {
		if(filled == true)
			return "A Shape with color of " + color + " and filled";
		else
			return "A Shape with color of " + color + " and NOT filled";
	}
	
	public abstract double getArea();
	
	public abstract double getPerimeter();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package abstractclass;
	
public class Square extends Rectangle{
	public Square(double side) {
		 super(side, side); // Call superclass Rectangle(double, double)
	}
	
	public double getSide() {
		return super.getWidth();
	}
	
	public String toString() {
		return "A Square with side = "+super.getLength()+", which is a subclass of "+super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package abstractclass;

public class Main {
	public static void main(String[] args) {
		
		java.text.DecimalFormat df =new java.text.DecimalFormat("#.00");
		Shape s1 = new Circle(5.5, "green", false); // Upcast Circle to Shape
		System.out.println(s1);  // which version?
		double Area1 = s1.getArea();
		double Perimeter1 = s1.getPerimeter();
		System.out.println(df.format(Area1)); // which version?
		System.out.println(df.format(Perimeter1)); 
		System.out.println(s1.getColor());
		System.out.println(s1.isFilled());
//Shape.test
		
		Circle c1 = (Circle)s1; // Downcast back to Circle
		System.out.println(c1);
		double Area2 = c1.getArea();
		double Perimeter2 = c1.getPerimeter();
		System.out.println(df.format(Area2)); 
		System.out.println(df.format(Perimeter2)); 
		System.out.println(c1.getColor());
		System.out.println(c1.isFilled());
		System.out.println(c1.getRadius());
		
         //       Shape s2 = new Shape(); // Why wrong? : Abstract class cannot be instantiated

//Circle.test
			
		Shape s3 = new Rectangle(1.0, 2.0, "green", false); // Upcast
		System.out.println(s3);
		double Area3 = s3.getArea();
		double Perimeter3 = s3.getPerimeter();
		System.out.println(df.format(Area3)); 
		System.out.println(df.format(Perimeter3)); 
		System.out.println(s3.getColor());

			
		Rectangle r1 = (Rectangle)s3; // downcast
		System.out.println(r1);
		double Area4 = r1.getArea();
		System.out.println(df.format(Area4)); 
		System.out.println(r1.getColor());
		System.out.println(r1.getLength());
//Rectangle.test
		
		Shape s4 = new Square(6.6); // Upcast
		System.out.println(s4);
		double Area5 = s4.getArea();
		System.out.println(df.format(Area5)); 
		System.out.println(s4.getColor());
		
		Rectangle r2 = (Rectangle)s4;
		System.out.println(r2);
		double Area6 = r2.getArea();
		System.out.println(df.format(Area6)); 
		System.out.println(r2.getColor());
		System.out.println(r2.getLength());
		
		Square sq1 = (Square)r2;
		System.out.println(sq1);
		double Area7 = sq1.getArea();
		System.out.println(df.format(Area7)); 
		System.out.println(sq1.getColor());
		System.out.println(sq1.getSide());
		System.out.println(sq1.getLength());
//Square.test

	}
	
	
}

exception

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package exception;

class CircleWithException {
	double radius;
	static int numberOfObjects = 0;
	
	CircleWithException(){
		radius = 0;
		numberOfObjects++;
	}
	
	CircleWithException(double r){
		if(r >= 0)
		{
			radius = r;
			numberOfObjects++;
		}
		else
			throw new IllegalArgumentException("Radius cannot be negative");
	}
	
	public double getRadius() {
		return radius;
	}
	
	public void setRadius(double r) {
		radius = r;
	}
	
	public static int getNumberOfObjects() {
		return numberOfObjects;
	}
	
	public double getArea() {
		return Math.PI * radius * radius;
	}
	
}


public class Main1 {
	public static void main(String[] args) {
		try {
			CircleWithException c1 = new CircleWithException(5);
			CircleWithException c2 = new CircleWithException(-5);
			CircleWithException c3 = new CircleWithException(0);
		}
		catch (IllegalArgumentException ex) {
			System.out.println(ex);
		}
		System.out.println("Number of objects created: " + CircleWithException.getNumberOfObjects() );
	}
}

interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package Interface;

public class MovablePoint implements Movable {
	// instance variables
    int x, y, xSpeed, ySpeed; // package access

    // Constructor
    public MovablePoint(int x, int y, int xSpeed, int ySpeed) {
        this.x = x;
        this.y = y;
        this.xSpeed = xSpeed;
        this.ySpeed = ySpeed;
    }

    // Implement abstract methods declared in the interface Movable
    @Override
    public void moveUp() {
        y += ySpeed; 
    }
    
    @Override
    public void moveDown() {
        y -= ySpeed; 
    }
    
    @Override
    public void moveLeft() {
        x -= xSpeed;
    }
    
    @Override
    public void moveRight() {
        x += xSpeed; 
    }
    
    public String toString() {
    	return "MovablePoint (" + x + ", " + y + ") with xSpeed = " + xSpeed + " and ySpeed = " + ySpeed;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package Interface;

public class MovableCircle implements Movable { // saved as "MovableCircle.java"
    // instance variables
    private MovablePoint center; // can use center.x, center.y directly
    // because they are package accessible
    private int radius;

    // Constructor
    public MovableCircle(int x, int y, int xSpeed, int ySpeed, int radius) {
        // Call the MovablePoint's constructor to allocate the center instance.
        center = new MovablePoint(x, y, xSpeed, ySpeed);
        this.radius = radius;
    }
    
    // Implement abstract methods declared in the interface Movable
    @Override
    public void moveUp() {
        center.y += center.ySpeed;
    }
    
    @Override
    public void moveDown() {
        center.y -= center.ySpeed;
    }
    
    @Override
    public void moveLeft() {
        center.x -= center.xSpeed;
    }
    
    @Override
    public void moveRight() {
        center.x += center.xSpeed;
    }
    
    public String toString() {
    	return "MovableCircle at point " + center.toString() + " with radius = " + radius;
    }
}
1
2
3
4
5
6
7
8
package Interface;

public interface Movable {
	public void moveUp();
	public void moveDown();
	public void moveLeft();
	public void moveRight();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package Interface;

public class Main{
	public static void main(String[] args) {
        Movable m1 = new MovablePoint(5, 6, 10, 15); // upcast
        System.out.println(m1);
        m1.moveLeft();
        System.out.println(m1);
        m1.moveUp();
        System.out.println(m1);

        Movable m2 = new MovableCircle(1, 2, 3, 4, 20); // upcast
        System.out.println(m2);
        m2.moveRight();
        System.out.println(m2);
        m2.moveDown();
        System.out.println(m2);
    }
}

superclass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package superclass;

public class Circle extends Shape{
	double radius;
	Circle(){
		super();
		this.radius = 0;
	}
	Circle(double r, String c, boolean f){
		super(c, f);
		this.radius = r;
	}
	Circle(double r){
		super();
		this.radius = r;
	}
	public double getRadius() {
		return this.radius;
	}
	
	public double getArea() {
		return Math.PI * radius * radius;
	}
	
	public double getPerimeter() {
		return Math.PI * 2 * radius;
	}
	
	public String toString() {
		return "A Circle with radius = " + radius + ", which is a subclass of " + super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package superclass;

public class Rectangle extends Shape{
	double width;
	double length;
	
	Rectangle(){
		super();
		this.width = 0;
		this.length = 0;
	}
	Rectangle(double w, double l, String c, boolean f){
		super(c, f);
		this.width = w;
		this.length = l;
	}
	Rectangle(double w, double l){
		super();
		this.width = w;
		this.length = l;
	}
	public double getWidth() {
		return this.width;
	}
	
	public double getLength() {
		return this.length;
	}
	
	
	public double getArea() {
		return width * length;
	}
	
	public double getPerimeter() {
		return 2*(width + length);
	}
	
	public String toString() {
		return "A Rectangle with width = "+width+" and length = "+length+", which is a subclass of "+ super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package superclass;

public class Shape {
	String color;
	boolean filled;
	
	Shape(){
		this.color = "red";
		this.filled = true;
	}
	
	Shape(String c, boolean f){
		this.color = c;
		this.filled = f;
	}
	
	public String getColor() {
		return color;
	}
	
	public boolean isFilled() {
		return filled;
	}
	
	public String toString() {
		if(filled == true)
			return "A Shape with color of " + color + " and filled";
		else
			return "A Shape with color of " + color + " and NOT filled";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package superclass;

public class Square extends Rectangle{
	public Square(double side) {
		 super(side, side); // Call superclass Rectangle(double, double)
	}
	
	public double getSide() {
		return super.getWidth();
	}
	
	public String toString() {
		return "A Square with side = "+super.getLength()+", which is a subclass of "+super.toString();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package superclass;

public class Main {
	public static void main(String[] args) {
	
	// Upcast Circle to Shape
	Shape s1 = new Circle(5.5, "green", false); 
	System.out.println(s1);
	System.out.println(s1.getColor());
	System.out.println(s1.isFilled());

	// Downcast back to Circle
	Circle c1 = (Circle)s1; 
	System.out.println(c1);
	System.out.println(c1.getColor());
	System.out.println(c1.isFilled());

	// Upcast
	Shape s2 = new Rectangle(1.0, 2.0, "green", false); 
	System.out.println(s2);
	System.out.println(s2.getColor());

	//Downcast
	Rectangle r1 =  (Rectangle)s2; 
	System.out.println(r1);
	System.out.println(r1.getArea());
	System.out.println(r1.getColor());
	System.out.println(r1.getLength());

	// Upcast
	Shape s3 = new Square(6.6); 
	System.out.println(s3);
	System.out.println(s3.getColor());

	
	Rectangle r2 =  (Rectangle)s3; 
	System.out.println(r2);
	java.text.DecimalFormat df =new java.text.DecimalFormat("#.00");
	double area1 = r2.getArea();
	System.out.println(df.format(area1));
	System.out.println(r2.getColor());
	System.out.println(r2.getLength());

	
	// Downcast Rectangle r2 to Square
	Square sq1 = (Square)r2;
	System.out.println(sq1);
	area1 = sq1.getArea();
	System.out.println(df.format(area1));
	System.out.println(sq1.getColor());
	System.out.println(sq1.getSide());
	System.out.println(sq1.getLength());
}


}