Leetcode Contest 147 Jul 27 2019

No.1 DP problem

1
2
3
4
5
6
7
8
9
10
11
12
13
public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }

No.2 Alphebatic

//Be careful to process from the

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:
    string alphabetBoardPath(string target) {
        int r = 0, c = 0;
        string moves = "";

        for (char letter : target) {
            int row = (letter - 'a') / 5, col = (letter - 'a') % 5;

            while (c > col) {
                moves += 'L';
                c--;
            }

            while (r > row) {
                moves += 'U';
                r--;
            }

            while (r < row) {
                moves += 'D';
                r++;
            }

            while (c < col) {
                moves += 'R';
                c++;
            }

            moves += '!';
        }

        return moves;
    }
};

No.3 Most number of Largest grid border

// accumulated grid solution 

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
int findLargestSquare(vector<vector<int>>& mat) 
    { 
    int max = 0; int m = mat.size() , n = mat[0].size();
    vector<vector<int>> hor(m,vector<int> (n,0)) , ver(m,vector<int> (n,0));
   
    for (int i=0; i<m; i++) { 
        for (int j=0; j<n; j++) { 
            if (mat[i][j] == 1) 
            { 
                hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;   // auxillary horizontal array
                ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;  // auxillary vertical array
            } 
        } 
    } 
        
    for (int i = m-1; i>=0; i--) { 
        for (int j = n-1; j>=0; j--) { 
            int small = min(hor[i][j], ver[i][j]);  // choose smallest of horizontal and vertical value
            while (small > max) { 
                if (ver[i][j-small+1] >= small &&  hor[i-small+1][j] >= small)  // check if square exists with 'small' length
                    max = small; 
                small--; 
            } 
        } 
    } 
    return max*max; 
}