Huahua’s Tech Road

花花酱 LeetCode 1382. Balance a Binary Search Tree

By zxi on March 15, 2020

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.

Solution: Inorder + recursion

Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* balanceBST(TreeNode* root) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

vals.push_back(root->val);

inorder(root->right);

};

function<TreeNode*(int, int)> build = [&](int l, int r) {

if (l > r) return (TreeNode*)nullptr;

int m = l + (r - l) / 2;

auto root = new TreeNode(vals[m]);

root->left = build(l, m - 1);

root->right = build(m + 1, r);

return root;

};

inorder(root);

return build(0, vals.size() - 1);

}

};

花花酱 LeetCode 1381. Design a Stack With Increment Operation

By zxi on March 15, 2020

Design a stack which supports the following operations.

Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
int pop() Pops and returns the top of stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Solution: Simulation

Time complexity:
init: O(1)
pop: O(1)
push: O(1)
inc: O(k)

C++

// Author: Huahua

class CustomStack {

public:

CustomStack(int maxSize): max_size_(maxSize) {}

void push(int x) {

if (data_.size() == max_size_) return;

data_.push_back(x);

}

int pop() {

if (data_.empty()) return -1;

int val = data_.back();

data_.pop_back();

return val;

}

void increment(int k, int val) {

for (int i = 0; i < min(static_cast<size_t>(k),

data_.size()); ++i)

data_[i] += val;

}

private:

int max_size_;

vector<int> data_;

};

/**

* Your CustomStack object will be instantiated and called as such:

* CustomStack* obj = new CustomStack(maxSize);

* obj->push(x);

* int param_2 = obj->pop();

* obj->increment(k,val);

花花酱 LeetCode 1380. Lucky Numbers in a Matrix

By zxi on March 15, 2020

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints:

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.

Solution: Pre-processing

Two pass. First pass, record the min val of each row, and max val of each column.
Second pass, identify lucky numbers.

Time complexity: O(m * n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> luckyNumbers (vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<int> rows(m, INT_MAX);

vector<int> cols(n, INT_MIN);

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

for (int j = 0; j < n; ++j) {

rows[i] = min(rows[i], matrix[i][j]);

cols[j] = max(cols[j], matrix[i][j]);

}

vector<int> ans;

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

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

if (matrix[i][j] == rows[i] &&

matrix[i][j] == cols[j])

ans.push_back(matrix[i][j]);

return ans;

}

};

花花酱 LeetCode 87. Scramble String

By zxi on March 14, 2020

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution: Recursion

isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:

s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]

Time complexity: O(n^5)
Space complexity: O(n^4)

C++

class Solution {

public:

bool isScramble(string_view s1, string_view s2) {

const int l = s1.length();

if (s1 == s2) return true;

if (freq(s1) != freq(s2)) return false;

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

if (isScramble(s1.substr(0, i), s2.substr(0, i))

&& isScramble(s1.substr(i), s2.substr(i))

|| isScramble(s1.substr(0, i), s2.substr(l - i, i))

&& isScramble(s1.substr(i), s2.substr(0, l - i)))

return true;

return false;

}

private:

vector<int> freq(string_view s) {

vector<int> f(26);

for (char c : s) ++f[c - 'a'];

return f;

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None) # optional

def isScramble(self, s1: str, s2: str) -> bool:

if s1 == s2: return True

# important, TLE if commneted out

if Counter(s1) != Counter(s2): return False

L = len(s1)

for l in range(1, L):

if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]):

return True

if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]):

return True

return False

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

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

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

for (int i = 1; i <= s.size(); ++i)

for (int j = 1; i + j <= s.size(); ++j)

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False

Huahua's Tech Road

花花酱 LeetCode 1382. Balance a Binary Search Tree

Solution: Inorder + recursion

C++

花花酱 LeetCode 1381. Design a Stack With Increment Operation

Solution: Simulation

C++

花花酱 LeetCode 1380. Lucky Numbers in a Matrix

Solution: Pre-processing

C++

花花酱 LeetCode 87. Scramble String

Solution: Recursion

C++

Python3

花花酱 LeetCode 306. Additive Number

Solution: DFS

C++

Python3