Posts tagged as “recursion”

花花酱 LeetCode 808. Soup Servings

By zxi on August 1, 2018

Problem

There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:
Input: N = 50
Output: 0.625
Explanation: 
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.

Solution 1: Recursion with Memorization

Time complexity: O(N^2) N ~ 5000 / 25 = 200

Space complexity: O(N^2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

double soupServings(int N) {

if (N >= 5000) return 1.0;

return prob(N, N);

}

private:

unordered_map<int, unordered_map<int, double>> m_;

double prob(int A, int B) {

static int ops[][2] = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};

if (A <= 0 && B <= 0) return 0.5;

if (A <= 0) return 1.0;

if (B <= 0) return 0.0;

if (m_.count(A) && m_[A].count(B)) return m_[A][B];

m_[A][B] = 0.0;

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

m_[A][B] += 0.25 * prob(A - ops[i][0], B - ops[i][1]);

return m_[A][B];

}

};

花花酱 LeetCode 101. Symmetric Tree

By zxi on July 26, 2018

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isSymmetric(TreeNode* root) {

return isMirror(root, root);

}

private:

bool isMirror(TreeNode* root1, TreeNode* root2) {

if (!root1 && !root2) return true;

if (!root1 || !root2) return false;

return root1->val == root2->val

&& isMirror(root1->right, root2->left)

&& isMirror(root1->left, root2->right);

}

};

Python

"""

Author: Huahua

Running time: 48 ms

"""

class Solution:

def isSymmetric(self, root):

def isMirror(root1, root2):

if not root1 and not root2: return True

if not root1 or not root2: return False

return root1.val == root2.val \

and isMirror(root1.left, root2.right) \

and isMirror(root2.left, root1.right)

return isMirror(root, root)

Problem

We want to use quad trees to store an N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same.

Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.

Your task is to use a quad tree to represent a given grid. The following example may help you understand the problem better:

Given the 8 x 8 grid below, we want to construct the corresponding quad tree:

It can be divided according to the definition above:

The corresponding quad tree should be as following, where each node is represented as a (isLeaf, val)pair.

For the non-leaf nodes, val can be arbitrary, so it is represented as *.

Note:

N is less than 1000 and guaranteened to be a power of 2.
If you want to know more about the quad tree, you can refer to its wiki.

Solution: Recursion

Time complexity: O(n^2*logn)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

bool all_zeros = true;

bool all_ones = true;

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

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

if (grid[i][j] == 0)

all_ones = false;

else

all_zeros = false;

if (all_zeros || all_ones)

return new Node(all_ones, true, nullptr, nullptr, nullptr, nullptr);

return new Node(true, false,

construct(grid, x, y, n/2), // topLeft

construct(grid, x + n/2, y, n/2), // topRight

construct(grid, x, y + n/2, n/2), // bottomLeft

construct(grid, x + n/2, y + n/2, n/2)); // bottomRight

}

};

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 56 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

if (n == 1) return new Node(grid[y][x], true, nullptr, nullptr, nullptr, nullptr);

auto tl = construct(grid, x, y, n/2); // topLeft

auto tr = construct(grid, x + n/2, y, n/2); // topRight

auto bl = construct(grid, x, y + n/2, n/2); // bottomLeft

auto br = construct(grid, x + n/2, y + n/2, n/2); // bottomRight

if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf

&& tl->val == tr->val && tl->val == bl->val && tl->val == br->val) {

auto root = new Node(tl->val, true, nullptr, nullptr, nullptr, nullptr);

delete tl;

delete tr;

delete bl;

delete br;

return root;

}

return new Node(true, false, tl, tr, bl, br);

}

};

花花酱 LeetCode 814. Binary Tree Pruning

By zxi on April 7, 2018

Problem:

题目大意：把不含有1的节点的子树全部删除。

https://leetcode.com/problems/binary-tree-pruning/description/

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

TreeNode* pruneTree(TreeNode* root) {

if (!root) return root;

root->left = pruneTree(root->left);

root->right = pruneTree(root->right);

if (root->val == 1 || root->left || root->right)

return root;

delete root;

return nullptr;

}

};

Java

// Author: Huahua

// Running time: 2 ms

class Solution {

public TreeNode pruneTree(TreeNode root) {

if (root == null) return root;

root.left = pruneTree(root.left);

root.right = pruneTree(root.right);

return (root.val == 1 || root.left != null || root.right != null) ? root : null;

}

Python3

// Author: Huahua

// Running time: 36 ms

class Solution:

def pruneTree(self, root):

if not root: return root

root.left = self.pruneTree(root.left)

root.right = self.pruneTree(root.right)

return root if root.val == 1 or root.left or root.right else None

花花酱 LeetCode 94. Binary Tree Inorder Traversal

By zxi on March 23, 2018

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

vector<int> ans;

inorderTraversal(root, ans);

return ans;

}

private:

void inorderTraversal(TreeNode* root, vector<int>& ans) {

if (root == nullptr) return;

inorderTraversal(root->left, ans);

ans.push_back(root->val);

inorderTraversal(root->right, ans);

}

};

Solution 2: Iterative

// Author: Huahua

// Running time: 3 ms

lass Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

if (root == nullptr) return {};

vector<int> ans;

stack<TreeNode*> s;

TreeNode* curr = root;

while (curr != nullptr || !s.empty()) {

while (curr != nullptr) {

s.push(curr);

curr = curr->left;

}

curr = s.top(); s.pop();

ans.push_back(curr->val);

curr = curr->right;

}

return ans;

}

};

Posts tagged as “recursion”

花花酱 LeetCode 808. Soup Servings

Problem

Solution 1: Recursion with Memorization

花花酱 LeetCode 101. Symmetric Tree

Problem

Solution: Recursion

C++

Python

Related Problems

花花酱 LeetCode 427. Construct Quad Tree

Problem

Solution: Recursion

花花酱 LeetCode 814. Binary Tree Pruning

Problem:

Solution: Recursion

花花酱 LeetCode 94. Binary Tree Inorder Traversal

Problem

Solution: Recursion

Solution 2: Iterative