Huahua’s Tech Road

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

}

};

花花酱 LeetCode Weekly Contest 122

By zxi on February 3, 2019

花花酱 LeetCode 988. Smallest String Starting From Leaf

By zxi on February 2, 2019

Given the root of a binary tree, each node has a value from 0 to 25representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

Note:

The number of nodes in the given tree will be between 1 and 1000.
Each node in the tree will have a value between 0 and 25.

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

string smallestFromLeaf(TreeNode* root) {

if (!root) return "|"; // '|' > 'z'

const char v = static_cast<char>('a' + root->val);

if (!root->left && !root->right) return string(1, v);

string l = smallestFromLeaf(root->left);

string r = smallestFromLeaf(root->right);

return min(l, r) + v;

}

};

Python3

class Solution:

def smallestFromLeaf(self, root: 'TreeNode') -> 'str':

if not root: return '~'

c = chr(root.val + ord('a'))

if not root.left and not root.right: return c

return min(self.smallestFromLeaf(root.left),

self.smallestFromLeaf(root.right)) + c

Huahua's Tech Road

花花酱 LeetCode 989. Add to Array-Form of Integer

Solution: Simulation

C++

花花酱 LeetCode 781. Rabbits in Forest

Solution: Math

C++

Python3

花花酱 LeetCode 73. Set Matrix Zeroes

Solution 1

C++

Solution 2

C++

花花酱 LeetCode Weekly Contest 122

花花酱 LeetCode 988. Smallest String Starting From Leaf

Solution: Recursion

C++

Python3