Posts published in “Recursion”

花花酱 LeetCode 224. Basic Calculator

By zxi on March 9, 2020

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution: Recursion

Make a recursive call when there is an open parenthesis and return if there is close parenthesis.

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

C++

// Author: Huahua

class Solution {

public:

int calculate(string s) {

function<int(int&)> eval = [&](int& pos) {

int ret = 0;

int sign = 1;

int val = 0;

while (pos < s.size()) {

const char ch = s[pos];

if (isdigit(ch)) {

val = val * 10 + (s[pos++] - '0');

} else if (ch == '+' || ch == '-') {

ret += sign * val;

val = 0;

sign = ch == '+' ? 1 : -1;

++pos;

} else if (ch == '(') {

val = eval(++pos);

} else if (ch == ')') {

++pos;

break;

} else {

++pos;

}

return ret += sign * val;

};

int pos = 0;

return eval(pos);

}

};

Python3

# Author: Huahua

class Solution:

def calculate(self, s: str) -> int:

self.pos = 0

def eval():

val = 0

sign = 1

ret = 0

while self.pos < len(s):

ch = s[self.pos]

if ch == ' ':

self.pos += 1

elif ch == '(':

self.pos += 1

val = eval()

elif ch == ')':

self.pos += 1

ret += sign * val

return ret

elif ch == '+' or ch == '-':

ret += sign * val

val = 0

sign = 1 if ch == '+' else -1

self.pos += 1

else:

val = val * 10 + (ord(ch) - ord('0'))

self.pos += 1

ret += val * sign

return ret

return eval()

花花酱 LeetCode 1140. Stone Game II

By zxi on July 27, 2019

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Solution: Recursion + Memoization

def solve(s, m) = max diff score between two players starting from s for the given M.

cache[s][M] = max{sum(piles[s:s+x]) – solve(s+x, max(x, M)}, 1 <= x <= 2*M, s + x <= n

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

C++

// Author: Huahua, 12 ms / 9.7 MB

class Solution {

public:

int stoneGameII(vector<int>& piles) {

const int n = piles.size();

unordered_map<int, int> cache;

// Maximum diff starting from piles[s] given M.

function<int(int, int)> solve = [&](int s, int M) {

if (s >= n) return 0;

const int key = (s << 8) | M;

if (cache.count(key)) return cache[key];

int best = INT_MIN;

int curr = 0;

for (int x = 1; x <= 2 * M; ++x) {

if (s + x > n) break;

curr += piles[s + x - 1];

best = max(best, curr - solve(s + x, max(x, M)));

}

return cache[key] = best;

};

int total = accumulate(begin(piles), end(piles), 0);

return (total + solve(0, 1)) / 2;

}

};

花花酱 LeetCode 1106. Parsing A Boolean Expression

By zxi on June 30, 2019

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

"t", evaluating to True;
"f", evaluating to False;
"!(expr)", evaluating to the logical NOT of the inner expression expr;
"&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
"|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

Input: expression = "|(f,t)"
Output: true

Example 3:

Input: expression = "&(t,f)"
Output: false

Example 4:

Input: expression = "|(&(t,f,t),!(t))"
Output: false

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

bool parseBoolExpr(string expression) {

int s = 0;

return parse(expression, s);

}

private:

bool parse(const string& exp, int& s) {

char ch = exp[s++];

if (ch == 't') return true;

if (ch == 'f') return false;

if (ch == '!') {

bool ans = !parse(exp, ++s);

++s;

return ans;

}

bool is_and = (ch == '&');

bool ans = is_and;

++s;

while (true) {

if (is_and) ans &= parse(exp, s);

else ans |= parse(exp, s);

if (exp[s++] == ')') break;

}

return ans;

}

};

Java

class Solution {

private int s;

private char[] exp;

public boolean parseBoolExpr(String expression) {

exp = expression.toCharArray();

s = 0;

return parse() == 1;

}

private int parse() {

char ch = exp[s++];

if (ch == 't') return 1;

if (ch == 'f') return 0;

if (ch == '!') {

++s;

int ans = 1 - parse();

++s;

return ans;

}

boolean is_and = (ch == '&');

int ans = is_and ? 1 : 0;

++s;

while (true) {

if (is_and) ans &= parse();

else ans |= parse();

if (exp[s++] == ')') break;

}

return ans;

}

花花酱 LeetCode 394. Decode String

By zxi on April 10, 2019

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution 1: Recursion

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

C++

// Author: Huahua, 4ms

class Solution {

public:

string decodeString(string s) {

if (s.empty()) return "";

string ans;

int i = 0;

int n = s.length();

int c = 0;

while (isdigit(s[i]) && i < n)

c = c * 10 + (s[i++] - '0');

int j = i;

if (i < n && s[i] == '[') {

int open = 1;

while (++j < n && open) {

if (s[j] == '[') ++open;

if (s[j] == ']') --open;

}

} else {

while (j < n && isalpha(s[j])) ++j;

}

// "def2[ac]" => "def" + decodeString("2[ac]")

// | |

// i j

if (i == 0)

return s.substr(0, j) + decodeString(s.substr(j));

// "3[a2[c]]ef", ss = decodeString("a2[c]") = "acc"

// | |

// i j

string ss = decodeString(s.substr(i + 1, j - i - 2));

while (c--)

ans += ss;

// "3[a2[c]]ef", ans = "abcabcabc", ans += decodeString("ef")

ans += decodeString(s.substr(j));

return ans;

}

};

花花酱 LeetCode 464. Can I Win

By zxi on February 4, 2018

题目大意：两个人从1到M中每次取出一个数加到当前的总和上，第一个达到或超过T的人获胜。问你第一个玩家能不能获胜。

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:

maxChoosableInteger = 10

desiredTotal = 11

Output:

false

Explanation:

No matter which integer the first player choose, the first player will lose.

The first player can choose an integer from 1 up to 10.

If the first player choose 1, the second player can only choose integers from 2 up to 10.

The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.

Same with other integers chosen by the first player, the second player will always win.

Solution: Recursion with memoization

Time complexity: O(2^M)

Space complexity: O(2^M)

C++

// Author: Huahua

// Running time: 19 ms (<98.70%)

class Solution {

public:

bool canIWin(int M, int T) {

const int sum = M * (M + 1) / 2;

if (sum < T) return false;

if (T <= 0) return true;

m_ = vector<char>(1 << M, 0);

return canIWin(M, T, 0);

}

private:

vector<char> m_; // 0: unknown, 1: won, -1: lost

bool canIWin(int M, int T, int state) {

if (T <= 0) return false;

if (m_[state]) return m_[state] == 1;

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

if (state & (1 << i)) continue; // number i used

// The next player can not win, current player wins

if (!canIWin(M, T - (i + 1), state | (1 << i)))

return m_[state] = 1;

}

// Current player loses.

m_[state] = -1;

return false;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

private byte[] m_;

public boolean canIWin(int M, int T) {

int sum = M * (M + 1) / 2;

if (sum < T) return false;

if (T <= 0) return true;

m_ = new byte[1 << M];

return canIWin(M, T, 0);

}

private boolean canIWin(int M, int T, int state) {

if (T <= 0) return false;

if (m_[state] != 0) return m_[state] == 1;

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

if ((state & (1 << i)) > 0) continue;

if (!canIWin(M, T - (i + 1), state | (1 << i))) {

m_[state] = 1;

return true;

}

m_[state] = -1;

return false;

}

Python3

"""

Author: Huahua

Running time: 706 ms

"""

class Solution:

def canIWin(self, M, T):

def win(M, T, m, state):

if T <= 0: return False

if m[state] != 0: return m[state] == 1

for i in range(M):

if (state & (1 << i)) > 0: continue

if not win(M, T - i - 1, m, state | (1 << i)):

m[state] = 1

return True

m[state] = -1

return False

s = M * (M + 1) / 2

if s < T: return False

if T <= 0: return True

if s == T: return (M % 2) == 1

m = [0] * (1 << M)

return win(M, T, m, 0)