花花酱 LeetCode 965. Univalued Binary Tree

By zxi on December 30, 2018

Problem

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: [2,2,2,5,2]
Output: false

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

bool isUnivalTree(TreeNode* root) {

if (!root) return true;

if (root->left && root->val != root->left->val) return false;

if (root->right && root->val != root->right->val) return false;

return isUnivalTree(root->left) && isUnivalTree(root->right);

}

};

Python3

# Author: Huahua, running time: 68 ms

class Solution:

def isUnivalTree(self, root):

if not root: return True

if root.left and root.left.val != root.val: return False

if root.right and root.right.val != root.val: return False

return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

花花酱 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;

}

};

花花酱 LeetCode 963. Minimum Area Rectangle II

By zxi on December 26, 2018

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: HashTable

Iterate all possible triangles and check the opposite points that creating a quadrilateral.

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

C++

class Solution {

public:

double minAreaFreeRect(vector<vector<int>>& points) {

constexpr double INF_AREA = 1e100;

const auto n = points.size();

unordered_set<int> s;

for (const auto& p : points)

s.insert(p[0] << 16 | p[1]);

double min_area = INF_AREA;

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

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

if (i == j) continue;

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

if (i == k || j == k) continue;

const auto& p1 = points[i];

const auto& p2 = points[j];

const auto& p3 = points[k];

int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +

(p2[1] - p1[1]) * (p3[1] - p1[1]);

if (dot != 0) continue;

int p4_x = p2[0] + p3[0] - p1[0];

int p4_y = p2[1] + p3[1] - p1[1];

if (!s.count(p4_x << 16 | p4_y)) continue;

double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);

double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);

double area = a * b;

min_area = min(min_area, area);

}

return min_area < INF_AREA ? sqrt(min_area) : 0;

}

};

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

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

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

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

while (!s.empty() && A[i] >= A[s.top()]) {

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

for i in range(len(A) - 1, -1, -1):

while s and A[i] >= A[s[-1]]:

ans = max(ans, i - s.pop())

return ans

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

By zxi on December 23, 2018

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

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

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution: Randomization

Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.

Time complexity: O(1) expected 4
Space complexity: O(1)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int repeatedNTimes(vector<int>& A) {

int i = 0;

int j = 0;

while (i == j || A[i] != A[j]) {

i = rand() % A.size();

j = rand() % A.size();

}

return A[i];

}

};

Huahua's Tech Road

花花酱 LeetCode 965. Univalued Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problems

花花酱 LeetCode 964. Least Operators to Express Number

Solution: Dijkstra

C++/set

C++/heap

Solution 2: DFS + Memoization

C++

花花酱 LeetCode 963. Minimum Area Rectangle II

Solution: HashTable

C++

花花酱 LeetCode 962. Maximum Width Ramp

Solution: Stack

C++

Python3

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

Solution: Randomization

C++