Posts tagged as “recursion”

花花酱 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 273. Integer to English Words

By zxi on April 3, 2019

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Solution: Recursion

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

C++

// Author: Huahua

constexpr char * kUnder20[] = {"One", "Two", "Three", "Four", "Five",

"Six", "Seven", "Eight", "Nine","Ten",

"Eleven", "Twelve", "Thirteen", "Fourteen",

"Fifteen", "Sixteen", "Seventeen", "Eighteen",

"Nineteen"};

constexpr char * kUnder100[] = {"Twenty", "Thirty", "Forty", "Fifty",

"Sixty", "Seventy", "Eighty", "Ninety"};

constexpr char * kHTMB[] = {"Hundred", "Thousand", "Million", "Billion"};

constexpr long kP[] = {100, 1000, 1000*1000, 1000*1000*1000};

class Solution {

public:

string numberToWords(int n) {

if (n == 0) return "Zero";

return convert(n).substr(1);

}

private:

string convert(int n) {

if (n == 0) return "";

if (n < 20) return string(" ") + kUnder20[n - 1]; // 1 - 19

if (n < 100) return string(" ") + kUnder100[n / 10 - 2] + convert(n % 10); // 20 ~ 99

for (int i = 3; i >= 0; --i)

if (n >= kP[i]) return convert(n / kP[i]) + " " + kHTMB[i] + convert(n % kP[i]);

return "";

}

};

花花酱 LeetCode 988. Smallest String Starting From Leaf

By zxi on February 2, 2019

Given the root of a binary tree, each node has a value from 0 to 25representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

Note:

The number of nodes in the given tree will be between 1 and 1000.
Each node in the tree will have a value between 0 and 25.

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

string smallestFromLeaf(TreeNode* root) {

if (!root) return "|"; // '|' > 'z'

const char v = static_cast<char>('a' + root->val);

if (!root->left && !root->right) return string(1, v);

string l = smallestFromLeaf(root->left);

string r = smallestFromLeaf(root->right);

return min(l, r) + v;

}

};

Python3

class Solution:

def smallestFromLeaf(self, root: 'TreeNode') -> 'str':

if not root: return '~'

c = chr(root.val + ord('a'))

if not root.left and not root.right: return c

return min(self.smallestFromLeaf(root.left),

self.smallestFromLeaf(root.right)) + c

花花酱 LeetCode 979. Distribute Coins in Binary Tree

By zxi on January 20, 2019

Given the root of a binary tree with N nodes, each node in the tree has node.valcoins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

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

Example 4:

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

Note:

1<= N <= 100
0 <= node.val <= N

Solution: Recursion

Compute the balance of left/right subtree, ans += abs(balance(left)) + abs(balance(right))
balance(root) = balance(left) + balance(right) + root.val – 1

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

C++

class Solution {

public:

int distributeCoins(TreeNode* root) {

int ans = 0;

balance(root, ans);

return ans;

}

private:

int balance(TreeNode* root, int& ans) {

if (!root) return 0;

int l = balance(root->left, ans);

int r = balance(root->right, ans);

ans += abs(l) + abs(r);

return l + r + root->val - 1;

}

};

花花酱 LeetCode 968. Binary Tree Cameras

By zxi on December 31, 2018

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Solution: Greedy + Recursion

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

C++

enum class State { NONE = 0, COVERED = 1, CAMERA = 2 };

class Solution {

public:

int minCameraCover(TreeNode* root) {

if (dfs(root) == State::NONE) ++ans_;

return ans_;

}

private:

int ans_ = 0;

State dfs(TreeNode* root) {

if (!root) return State::COVERED;

State l = dfs(root->left);

State r = dfs(root->right);

if (l == State::NONE || r == State::NONE) {

++ans_;

return State::CAMERA;

}

if (l == State::CAMERA || r == State::CAMERA)

return State::COVERED;

return State::NONE;

}

};