Huahua's Tech Road

花花酱 LeetCode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

By zxi on December 8, 2019

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.

Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6

Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Constraints:

m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j] is 0 or 1.

Solution: BFS + bitmask

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

C++

// Author: Huahua

class Solution {

public:

int minFlips(vector<vector<int>>& mat) {

const int m = mat.size();

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

const vector<int> dirs{0, 1, 0, -1, 0, 0};

auto flip = [&](int s, int x, int y) {

for (int i = 0; i < 5; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

s ^= (1 << ty * n + tx);

}

return s;

};

int steps = 0;

queue<int> q;

vector<int> seen(1 << (n * m));

int start = 0;

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

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

start |= (mat[y][x] << (y * n + x));

q.push(start);

seen[start] = 1;

while (!q.empty()) {

int size = q.size();

while (size--) {

int s = q.front();

if (s == 0) return steps;

q.pop();

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

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

int t = flip(s, x, y);

if (seen[t]) continue;

seen[t] = 1;

q.push(t);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold

By zxi on December 8, 2019

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Solution: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int smallestDivisor(vector<int>& nums, int threshold) {

auto sums = [&](int d) {

int s = 0;

for (int n : nums)

s += (n + (d - 1)) / d;

return s;

};

int l = 1;

int r = 1e6;

while (l < r) {

int m = l + (r - l) / 2;

if (sums(m) <= threshold)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1281. Subtract the Product and Sum of Digits of an Integer

By zxi on December 8, 2019

Given an integer number n, return the difference between the product of its digits and the sum of its digits.

Example 1:

Input: n = 234

Output: 15

Explanation:

Product of digits = 2 * 3 * 4 = 24

Sum of digits = 2 + 3 + 4 = 9

Result = 24 - 9 = 15

Example 2:

Input: n = 4421

Output: 21

Explanation:

Product of digits = 4 * 4 * 2 * 1 = 32

Sum of digits = 4 + 4 + 2 + 1 = 11

Result = 32 - 11 = 21

Constraints:

1 <= n <= 10^5

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int subtractProductAndSum(int n) {

int p = 1;

int s = 0;

while (n) {

const int d = n % 10;

p *= d;

s += d;

n /= 10;

}

return p - s;

}

};

花花酱 LeetCode 132. Palindrome Partitioning II

By zxi on December 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

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

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0

vector<vector<int>> valid(n, vector<int>(n, 1));

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

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

if (valid[0][i]) {

dp[i] = 0;

continue;

}

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

if (valid[j + 1][i])

dp[i] = min(dp[i], dp[j] + 1);

}

return dp[n - 1];

}

};

DP v2

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

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

for (int d = 0; d <= 1; ++d)

for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)

dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0));

return dp[n - 1];

}

};

Huahua's Tech Road

花花酱 LeetCode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Solution: BFS + bitmask

C++

花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold

Solution: Binary Search

C++

花花酱 LeetCode 1282. Group the People Given the Group Size They Belong To

Solution: HashMap + Greedy

C++

花花酱 LeetCode 1281. Subtract the Product and Sum of Digits of an Integer

Solution: Simulation

C++

花花酱 LeetCode 132. Palindrome Partitioning II

Solution: DP

C++

C++

Related Problems