Posts tagged as “medium”

花花酱 LeetCode 991. Broken Calculator

By zxi on February 10, 2019

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Solution: Greedy

Thinking backwards, making Y <= X by adding 1 or dividing 2.

If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd

Time complexity: O(log(Y-X))
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms, 4.7 MB

class Solution {

public:

int brokenCalc(int X, int Y) {

if (X <= Y) return X - Y;

return 1 + brokenCalc(X, Y % 2 ? Y + 1 : Y / 2);

}

};

花花酱 LeetCode 990. Satisfiability of Equality Equations

By zxi on February 10, 2019

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.

Example 2:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: ["a==b","b==c","a==c"]
Output: true

Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false

Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true

Note:

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] and equations[i][3] are lowercase letters
equations[i][1] is either '=' or '!'
equations[i][2] is '='

Solution: Union Find

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

C++

// Author: Huahua, running time: 12 ms, 7.1 MB

class Solution {

public:

bool equationsPossible(vector<string>& equations) {

iota(begin(parents_), end(parents_), 0);

for (const auto& eq : equations)

if (eq[1] == '=')

parents_[find(eq[0])] = find(eq[3]);

for (const auto& eq : equations)

if (eq[1] == '!' && find(eq[0]) == find(eq[3]))

return false;

return true;

}

private:

array<int, 128> parents_;

int find(int x) {

if (x != parents_[x])

parents_[x] = find(parents_[x]);

return parents_[x];

}

};

花花酱 LeetCode 781. Rabbits in Forest

By zxi on February 9, 2019

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

answers will have length at most 1000.
Each answers[i] will be an integer in the range [0, 999].

Solution: Math

Say there n rabbits answered x.
if n <= x: they can have the same color
if n > x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n / (x+1)) groups.
So there will be ceil(n / (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) / (x + 1) * (x + 1) in programming languages. (n + x) // (x + 1) * (x + 1) for Python3.

C++

// Author: Huahua, running time: 8 ms / 5.2 MB

class Solution {

public:

int numRabbits(vector<int>& answers) {

vector<int> counts(*max_element(begin(answers), end(answers)) + 1);

for (const int answer : answers)

++counts[answer];

int total = 0;

for (int x = 0; x < counts.size(); ++x)

total += (counts[x] + x) / (x + 1) * (x + 1);

return total;

}

};

Python3

# Author: Huahua, running time: 36 ms / 6.5 MB

class Solution:

def numRabbits(self, answers: 'List[int]') -> 'int':

counts = collections.Counter(answers)

return sum([(n + x) // (x + 1) * (x + 1) for x, n in counts.items()])

花花酱 LeetCode 987. Vertical Order Traversal of a Binary Tree

By zxi on February 2, 2019

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.

Solution: Ordered Map+ Ordered Set

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

C++

// Author: Huahua, running time: 0 ms, 921.6 KB

class Solution {

public:

vector<vector<int>> verticalTraversal(TreeNode* root) {

if (!root) return {};

int min_x = INT_MAX;

int max_x = INT_MIN;

map<pair<int, int>, multiset<int>> h; // {y, x} -> {vals}

traverse(root, 0, 0, h, min_x, max_x);

vector<vector<int>> ans(max_x - min_x + 1);

for (const auto& m : h) {

int x = m.first.second - min_x;

ans[x].insert(end(ans[x]), begin(m.second), end(m.second));

}

return ans;

}

private:

void traverse(TreeNode* root, int x, int y,

map<pair<int, int>, multiset<int>>& h,

int& min_x,

int& max_x) {

if (!root) return;

min_x = min(min_x, x);

max_x = max(max_x, x);

h[{y, x}].insert(root->val);

traverse(root->left, x - 1, y + 1, h, min_x, max_x);

traverse(root->right, x + 1, y + 1, h, min_x, max_x);

}

};

Python3

# Author: Huahua, 36 ms, 6.8 MB

class Solution:

def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':

if not root: return []

vals = []

def preorder(root, x, y):

if not root: return

vals.append((x, y, root.val))

preorder(root.left, x - 1, y + 1)

preorder(root.right, x + 1, y + 1)

preorder(root, 0, 0)

ans = []

last_x = -1000

for x, y, val in sorted(vals):

if x != last_x:

ans.append([])

last_x = x

ans[-1].append(val)

return ans

花花酱 LeetCode 986. Interval List Intersections

By zxi on February 2, 2019

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution: Two pointers

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

C++

// Author: Huahua, running time: 36 ms, 925.7 KB

class Solution {

public:

vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {

size_t i = 0;

size_t j = 0;

vector<Interval> ans;

while (i < A.size() && j < B.size()) {

const int s = max(A[i].start, B[j].start);

const int e = min(A[i].end, B[j].end);

if (s <= e) ans.emplace_back(s, e);

if (A[i].end < B[j].end)

++i;

else

++j;

}

return ans;

}

};

Python3

# Author: Huahua, running time: 96 ms, 7.6 MB

class Solution:

def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':

i, j, ans = 0, 0, []

while i < len(A) and j < len(B):

s = max(A[i].start, B[j].start)

e = min(A[i].end, B[j].end)

if s <= e:

ans.append(Interval(s, e))

if A[i].end < B[j].end:

i += 1

else:

j += 1

return ans