Huahua’s Tech Road

花花酱 LeetCode 1221. Split a String in Balanced Strings

By zxi on October 13, 2019

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints:

1 <= s.length <= 1000
s[i] = 'L' or 'R'

Solution: Greedy

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

C++

// Author: Huahua

class Solution {

public:

int balancedStringSplit(string s) {

int b = 0;

int ans = 0;

for (char c : s) {

b += c == 'L' ? 1 : -1;

if (b == 0) ++ans;

}

return ans;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 1221. Split a String in Balanced Strings

Solution: Greedy

C++

花花酱 LeetCode 131. Palindrome Partitioning

Solution1: DP

C++

Solution 2: DFS

C++

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