Posts published in “Uncategorized”

花花酱 LeetCode 226. Invert Binary Tree

By zxi on July 23, 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 1124. Longest Well-Performing Interval

By zxi on July 14, 2019

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

Solution: Target sum == 1

This problem can be reduced to find the longest subarray with sum of 1, or the longest subarray starting from left-most that has a sum greater than 0.

e.g. [6, 6, (6, 9, 9), 6, 6] => sum = 1
e.g. [9, 9, 9] => sum = 3

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

C++

// Author: Huahua

class Solution {

public:

int longestWPI(vector<int>& hours) {

const int n = hours.size();

for (int& v : hours) v = v > 8 ? 1 : -1;

int s = 0;

unordered_map<int, int> idx;

int ans = 0;

for (int i = 0; i < hours.size(); ++i) {

s += hours[i];

if (s > 0)

ans = i + 1;

if (!idx.count(s))

idx[s] = i;

if (idx.count(s - 1))

ans = max(ans, i - idx[s - 1]);

}

return ans;

}

};

花花酱 LeetCode Weekly Contest 130 (1017, 1018, 1019, 1020)

By zxi on March 31, 2019

1017. Convert to Base -2

Solution: Math / Simulation

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

C++

// Author: Huahua

class Solution {

public:

string baseNeg2(int N) {

if (N == 0) return "0";

vector<char> ans;

while (N) {

ans.push_back((N & 1) + '0');

N = -(N >> 1);

}

return {rbegin(ans), rend(ans)};

}

};

base K

// Author: Huahua

class Solution {

public:

string baseNeg2(int N) {

if (N == 0) return "0";

return baseNegK(N, -2);

}

private:

string baseNegK(int N, int K) {

vector<char> ans;

while (N) {

int r = N % K;

N /= K;

if (r < 0) {

r += -K;

N += 1;

}

ans.push_back(r + '0');

}

return {rbegin(ans), rend(ans)};

}

};

1018. Binary Prefix Divisible By 5

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> prefixesDivBy5(vector<int>& A) {

int num = 0;

vector<bool> ans(A.size());

for (int i = 0; i < A.size(); ++i) {

num = ((num << 1) | A[i]) % 5;

ans[i] = num == 0;

}

return ans;

}

};

1019. Next Greater Node In Linked List

Solution: Reverse + Monotonic Stack

Process in reverse order and keep a monotonically increasing stack, pop all the elements that are smaller than the current one, then the top of the stack (if exists) will be the next greater node.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> nextLargerNodes(ListNode* head) {

vector<int> nums;

while (head) {

nums.push_back(head->val);

head = head->next;

}

stack<int> s;

vector<int> ans(nums.size());

for (int i = nums.size() - 1; i >= 0; --i) {

while (!s.empty() && s.top() <= nums[i]) s.pop();

ans[i] = s.empty() ? 0 : s.top();

s.push(nums[i]);

}

return ans;

}

};

1020. Number of Enclaves

Solution: DFS / Connected Components

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

int numEnclaves(vector<vector<int>>& A) {

int ans = 0;

for (int i = 0; i < A.size(); ++i)

for (int j = 0; j < A[0].size(); ++j) {

int count = 0;

if (!dfs(A, j, i, count))

ans += count;

}

return ans;

}

private:

static constexpr int dirs[5]{0, -1, 0, 1, 0};

bool dfs(vector<vector<int>>& A, int x, int y, int& count) {

if (x < 0 || x == A[0].size() || y < 0 || y == A.size()) return true;

if (A[y][x] == 0) return false;

++count;

A[y][x] = 0;

bool valid = false;

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

valid |= dfs(A, x + dirs[i], y + dirs[i + 1], count);

return valid;

}

};

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

By zxi on March 3, 2019

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Example 2:

Input: "abcabcababcc"
Output: true
Explanation: 
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

Example 3:

Input: "abccba"
Output: false

Example 4:

Input: "cababc"
Output: false

Note:

1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'

Solution: Stack

If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.

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

C++

// Author: Huahua, running time: 28 ms, 11.9 MB

class Solution {

public:

bool isValid(string S) {

stack<string> st;

for (char ch : S) {

if (st.empty()) {

st.push("");

}

string& s = st.top();

char exp = 'a' + s.length();

if (ch == exp) {

s += ch;

if (s == "abc") st.pop();

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

return false;

} else {

st.push("a");

}

return st.empty();

}

};

花花酱 LeetCode 964. Least Operators to Express Number

By zxi on December 28, 2018

Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, *, or /). For example, with x = 3, we might write 3 * 3 / 3 + 3 - 3 which is a value of 3.

When writing such an expression, we adhere to the following conventions:

The division operator (/) returns rational numbers.
There are no parentheses placed anywhere.
We use the usual order of operations: multiplication and division happens before addition and subtraction.
It’s not allowed to use the unary negation operator (-). For example, “x - x” is a valid expression as it only uses subtraction, but “-x + x” is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given target. Return the least number of operators used.

Example 1:

Input: x = 3, target = 19 
Output: 5 
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.

Example 2:

Input: x = 5, target = 501 
Output: 8 
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.

Example 3:

Input: x = 100, target = 100000000 
Output: 3 
Explanation: 100 * 100 * 100 * 100.  The expression contains 3 operations.

Note:

2 <= x <= 100
1 <= target <= 2 * 10^8

Solution: Dijkstra

Find the shortest path from target to 0 using ops.

Time complexity: O(nlogn)
Space complexity: O(nlogn)
n = x * log(t) / log(x)

C++/set

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

set<pair<int, int>> q; // # x -> number

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const auto it = begin(q);

const int c = it->first;

const int t = it->second;

q.erase(it);

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

C++/heap

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const int c = q.top().first;

const int t = q.top().second;

q.pop();

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

Solution 2: DFS + Memoization

Time complexity: O(x * log(t)/log(x))
Space complexity: O(x * log(t)/log(x))

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

return dp(x, target);

}

private:

unordered_map<int, int> m_;

int dp(int x, int t) {

if (t == 0) return 0;

if (t < x) return min(2 * t - 1, 2 * (x - t));

if (m_.count(t)) return m_.at(t);

int k = log(t) / log(x);

long p = pow(x, k);

if (t == p) return m_[t] = k - 1;

int ans = dp(x, t - p) + k; // t - p < t

long left = p * x - t;

if (left < t) // only rely on smaller sub-problems

ans = min(ans, dp(x, left) + k + 1);

return m_[t] = ans;

}

};