Posts tagged as “recursion”

花花酱 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 226. Invert Binary Tree

By zxi on July 22, 2019

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Solution: Recursion

Recursive invert the left and right subtrees and swap them.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

if (!root) return nullptr;

TreeNode* tmp = root->right;

root->right = invertTree(root->left);

root->left = invertTree(tmp);

return root;

}

};

Python3

# Author: Huahua

class Solution:

def invertTree(self, root: TreeNode) -> TreeNode:

if not root: return None

root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

return root

花花酱 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 50. Pow(x, n)

By zxi on April 24, 2019

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2^-2 = 1/2² = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−2³¹, 2³¹− 1]

Solution: Recursion

square x and cut n in half.
if n is negative, compute 1.0 / pow(x, |n|)

pow(x, n) := pow(x * x, n / 2) * (x if n % 2 else 1)
pow(x, 0) := 1

Example:
pow(x, 5) = pow(x^2, 2) * x 
          = pow(x^4, 1) * x 
          = pow(x^8, 0) * x^4 * x
          = 1 * x^4 * x = x^5

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

C++

// Author: Huahua

class Solution {

public:

double myPow(double x, int n) {

return n >= 0 ? myPowImp(x, n) : 1.0 / myPowImp(x, n);

}

private:

double myPowImp(double x, int n) {

if (n == 0) return 1;

return myPowImp(x * x, n / 2) * (n % 2 ? x : 1);

}

};

花花酱 LeetCode 38. Count and Say

By zxi on April 17, 2019

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

// Author: Huahua, 4 ms, 8.6 MB

class Solution {

public:

string countAndSay(int n) {

string ans = "1";

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

ans = say(ans);

return ans;

}

private:

string say(const string& n){

string ans;

int s = 0, l = n.length();

for (int e = 1; e <= l; ++e)

if (e == l || n[s] != n[e]) {

int count = e - s;

ans += '0' + count;

ans += n[s];

s = e;

}

return ans;

}

};