Posts published in February 2019

花花酱 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 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

Solution: Simulation

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

C++

// Author: Huahua, running time: 136 ms, 10.1 MB

class Solution {

public:

vector<int> addToArrayForm(vector<int>& A, int K) {

vector<int> ans;

ans.reserve(A.size() + 1);

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

K += (i >= 0 ? A[i] : 0);

ans.push_back(K % 10);

K /= 10;

}

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 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 73. Set Matrix Zeroes

By zxi on February 9, 2019

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

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

Example 2:

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

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution 1

Use two arrays to track whether the i-th row / j-th column need to be zeroed.

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

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

vector<int> rows(m);

vector<int> cols(n);

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

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

rows[i] |= (matrix[i][j] == 0);

cols[j] |= (matrix[i][j] == 0);

}

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

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

if (rows[i] || cols[j]) matrix[i][j] = 0;

}

};

Solution 2

Use the first row / first col to indicate whether the i-th row / j-th column need be zeroed.

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

bool col0 = false;

bool row0 = false;

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

col0 |= (matrix[i][0] == 0);

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

row0 |= (matrix[0][j] == 0);

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

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

if (matrix[i][j] == 0)

matrix[0][j] = matrix[i][0] = 0;

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

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

if (matrix[i][0] == 0 || matrix[0][j] == 0)

matrix[i][j] = 0;

if (row0)

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

matrix[0][j] = 0;

if (col0)

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

matrix[i][0] = 0;

}

};