Huahua’s Tech Road

花花酱 LeetCode 130. Surrounded Regions

By zxi on October 9, 2019

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Solution: DFS

Time complexity: O(m*n)
Space complexity: O(m*n)

Only starts DFS at border cells of O.

C++

// Author: Huahua

class Solution {

public:

void solve(vector<vector<char>>& board) {

const int m = board.size();

if (m == 0) return;

const int n = board[0].size();

function<void(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') return;

board[y][x] = 'G'; // mark it as good

dfs(x - 1, y);

dfs(x + 1, y);

dfs(x, y - 1);

dfs(x, y + 1);

};

for (int y = 0; y < m; ++y)

dfs(0, y), dfs(n - 1, y);

for (int x = 0; x < n; ++x)

dfs(x, 0), dfs(x, m - 1);

map<char, char> v{{'G','O'},{'O','X'}, {'X','X'}};

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

board[y][x] = v[board[y][x]];

}

};

花花酱 LeetCode 129. Sum Root to Leaf Numbers

By zxi on October 9, 2019

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution: Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua

class Solution {

public:

int sumNumbers(TreeNode* root) {

int ans = 0;

function<void(TreeNode*, int)> traverse = [&](TreeNode* t, int num) {

if (!t) return;

num = num * 10 + t->val;

if (t->left || t->right) {

traverse(t->left, num);

traverse(t->right, num);

} else {

ans += num;

}

};

traverse(root, 0);

return ans;

}

};

花花酱 LeetCode 122. Best Time to Buy and Sell Stock II

By zxi on October 9, 2019

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution: Greedy

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int> &prices) {

int profit = 0;

for (size_t i = 1; i < prices.size(); ++i)

profit += max(0, prices[i] - prices[i - 1]);

return profit;

}

};

花花酱 LeetCode 1220. Count Vowels Permutation

By zxi on October 5, 2019

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'.
Each vowel 'e' may only be followed by an 'a' or an 'i'.
Each vowel 'i' may not be followed by another 'i'.
Each vowel 'o' may only be followed by an 'i' or a 'u'.
Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3:

Input: n = 5
Output: 68

Constraints:

1 <= n <= 2 * 10^4

Solution: DP

dp[i][c] := number of strings of length i ends with letter c
transition: follow the definition
ans = sum(dp[n])

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(5));

fill(begin(dp[1]), end(dp[1]), 1);

// 0: a, 1: e, 2: i, 3: o, 4: u

for (int i = 2; i <= n; ++i) {

dp[i][1] += dp[i - 1][0]; // a -> e

dp[i][0] += dp[i - 1][1]; // e -> a

dp[i][2] += dp[i - 1][1]; // e -> i

for (int j = 0; j < 5; ++j) {

if (j == 2) continue;

dp[i][j] += dp[i - 1][2]; // i -> *

}

dp[i][2] += dp[i - 1][3]; // o -> i

dp[i][4] += dp[i - 1][3]; // o -> u

dp[i][0] += dp[i - 1][4]; // u -> a

for (int j = 0; j < 5; ++j)

dp[i][j] %= kMod;

}

return accumulate(begin(dp[n]), end(dp[n]), 0L) % kMod;

}

};

C++/O(1)

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

long a = 1, e = 1, i = 1, o = 1, u = 1;

for (int k = 2; k <= n; ++k) {

long aa = (i + e + u) % kMod;

long ee = (i + a) % kMod;

long ii = (e + o) % kMod;

long oo = i % kMod;

long uu = (i + o) % kMod;

a = aa;

e = ee;

i = ii;

o = oo;

u = uu;

}

return (a + e + i + o + u) % kMod;

}

};

Solution 2: Matrix multiplication

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

vector<vector<long>> operator*(const vector<vector<long>>& A, const vector<vector<long>>& B) {

int m = A.size();

int x = A[0].size();

int n = B[0].size();

vector<vector<long>> C(m, vector<long>(n));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

for (int k = 0; k < x; ++k)

C[i][j] += A[i][k] * B[k][j];

C[i][j] %= kMod;

}

return C;

}

class Solution {

public:

int countVowelPermutation(int n) {

vector<vector<long>> m{

{0, 1, 0, 0, 0}, // a

{1, 0, 1, 0, 0}, // e

{1, 1, 0, 1, 1}, // i

{0, 0, 1, 0, 1}, // o

{1, 0, 0, 0, 0} // u

};

vector<vector<long>> ans{{1}, {1}, {1}, {1}, {1}};

n -= 1;

while (n > 0) {

if (n % 2) ans = m * ans;

m = m * m;

n /= 2;

}

long sum = 0;

for (int i = 0; i < 5; ++i)

sum += ans[i][0];

return sum % kMod;

}

};

花花酱 LeetCode 1219. Path with Maximum Gold

By zxi on October 5, 2019

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can’t visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints:

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

Solution: DFS

Time compleixty: O(4^25) ???
Space complexity: O(25)

C++

// Author: Huahua

class Solution {

public:

int getMaximumGold(vector<vector<int>>& g) {

int n = g.size();

int m = g[0].size();

int ans = 0;

function<int(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= m || y < 0 || y >= n || g[y][x] == 0) return 0;

int c = 0;

swap(c, g[y][x]);

int r = c + max({dfs(x - 1, y), dfs(x + 1, y), dfs(x, y - 1), dfs(x, y + 1)});

swap(c, g[y][x]);

return r;

};

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

ans = max(ans, dfs(j, i));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 130. Surrounded Regions

Solution: DFS

C++

花花酱 LeetCode 129. Sum Root to Leaf Numbers

Solution: Recursion

C++

花花酱 LeetCode 122. Best Time to Buy and Sell Stock II

Solution: Greedy

C++

花花酱 LeetCode 1220. Count Vowels Permutation

Solution: DP

C++

C++/O(1)

Solution 2: Matrix multiplication

C++

花花酱 LeetCode 1219. Path with Maximum Gold

Solution: DFS

C++