Huahua's Tech Road

花花酱 LeetCode 131. Palindrome Partitioning

By zxi on October 10, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution1: DP

dp[i] := ans of str[0:i]
dp[j] = { x + str[i:len] for x in dp[i] }, 0 <= i < len

Time complexity: O(2^n)
Space complexity: O(2^n)

C++

// Author: Huahua

bool isPalindrome(const string& s) {

const int n = s.length();

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

if (s[i] != s[n - 1 - i]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<vector<string>>> dp(n + 1);

for (int len = 1; len <= n; ++len) {

for (int i = 0; i < len; ++i) {

string right = s.substr(i, len - i);

if (!isPalindrome(right)) continue;

if (i == 0) dp[len].push_back({right});

for (const auto& p : dp[i]) {

dp[len].push_back(p);

dp[len].back().push_back(right);

}

return dp[n];

}

};

Solution 2: DFS

Time complexity: O(2^n)
Space complexity: O(n)

C++

// Author: Huahua

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<string>> ans;

vector<string> cur;

function<void(int)> dfs = [&](int start) {

if (start == n) {

ans.push_back(cur);

return;

}

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

if (!isPalindrome(s, start, i)) continue;

cur.push_back(s.substr(start, i - start + 1));

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 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;

}

};