LeetCode Weekly Contest 147

a.cpp

class Solution 
{
public:
    int tribonacci(int n) 
    {
        int a[6] = {0, 1, 1, 2, 4, 7};
        if(n < 6)
        {
            return a[n];
        }
        
        int t0 = 2, t1 = 4, t2 = 7;
        int t3 = t0 + t1 + t2;
        for(int i = 6; i <= n; i++)
        {
            t3 = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = t3;
        }
        return t3;
    }
};

b.cpp

#define mp make_pair
class Solution 
{
public:
    string alphabetBoardPath(string tg) 
    {
        vector<string>b = {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
        unordered_map<char, pair<int, int>>m; // char -> (row, col)

        for(int i = 0; i < 6; i++)
        {
            for(int j = 0; j < b[i].size(); j++)
            {
                m[b[i][j]] = mp(i, j);
            }
        }

        pair<int, int> last;
        pair<int, int> now;
        last = mp(0, 0);
        string res;
        for(auto s : tg)
        {
            now = m[s];
            int r = now.first, c = now.second;
            if(last == now)
            {
                res += "!";
            }
            else
            {
                int dr = r - last.first, dc = c - last.second;
                int postr = 0;

                for(int i = -1; i >= dr; i--)
                {
                    res += "U";
                }

                for(int i = 1; i <= dc; i++)
                {
                    res += "R";
                }

                for(int i = -1; i >= dc; i--)
                {
                    res += "L";
                }

                for(int i = 1; i <= dr; i++)
                {
                    res += "D";
                }
                res += "!";
            }
            last = now;
        }
        return res;
    }
};

c.cpp

#define N 100
class Solution 
{
public:
    int find_sq(vector<vector<int>>& grid)
    {
        int n = grid.size(), m = grid[0].size();
        int ver[N][N] = {0};
        int hor[N][N] = {0};
        hor[0][0] = ver[0][0] = (grid[0][0] == 1);

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if (grid[i][j] == 0)
                {
                    ver[i][j] = hor[i][j] = 0; 
                }
                else
                { 
                    hor[i][j] = (j == 0) ? 1 : hor[i][j-1] + 1; 
                    ver[i][j] = (i == 0) ? 1 : ver[i-1][j] + 1; 
                }
            }
        }

        int res = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = m - 1; j >= 0; j--)
            {
                int small = min (hor[i][j], ver[i][j]);
                while (small > res) 
                { 
                    if (ver[i][j - small + 1] >= small && hor[i - small + 1][j] >= small) 
                    { 
                        res = small;
                    }
                    small--; 
                } 
            }
        }
        return res;
    }
    int largest1BorderedSquare(vector<vector<int>>& grid) 
    {
        int res = find_sq(grid);
        return res == 0 ? 0 : res * res;
    }
};

d.cpp

// min - max memo solution, Alex tries to maximize himself and Lee try to minimize the opponent
class Solution 
{
    public:
    int dfs(int suffix_sum[101], int dp[101][101], int l, int M, int n) // l is the starting point, M as problem described and n is the border
    {
        // printf("L %d M %d ", l, M);
        if(l >= n) // out of bound, nothing to take
        {
            // printf("L >= n, return 0 \n");
            return 0; 
        }
        else if(dp[l][M] > 0) // return the cached answer if already computerd before
        {
            // printf("cached: %d\n", dp[l][M]);
            return dp[l][M];
        }
        else // update the max possibilities for Alex, starting from l and take at most 2M\
             // then maximize all the possibilities when compete with Lee
        {
            for(int i = 1; i <= 2 * M && l + i <= n; i++)
            {
                // printf("%d, %d call %d, %d \n", l, M,  i + l, max(M, i));
                dp[l][M] = max(dp[l][M], suffix_sum[l] - dfs(suffix_sum, dp, i + l, max(M, i), n)); // what Alex can take equals to the (suffix_sum from end to current l(start) minus all the posibilities that Lee can do starting from index i + l(since Alex has taken i stones)) 
            }
            return dp[l][M];
        }
    }
    int stoneGameII(vector<int>& piles) 
    {
        int n = piles.size();
        int dp[101][101] = {0}; // dp i j is the maximum value for Alex start at i and take at most M = j stones
        int suffix_sum[101] = {0};
        suffix_sum[n - 1] = piles[n -1];
        for(int i = n - 2; i >= 0; i--)
        {
            suffix_sum[i] = suffix_sum[i + 1] + piles[i];
        }
        return dfs(suffix_sum, dp, 0, 1, n);
    }
};