Huahua's Tech Road

花花酱 LeetCode 1254. Number of Closed Islands

By zxi on November 9, 2019

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

Input: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Output: 2

Constraints:

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

Solution: DFS/Backtracking

For each connected component, if it can reach the boundary then it’s not a closed island.

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

C++

// Author: Huahua

class Solution {

public:

int closedIsland(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

function<int(int, int)> dfs = [&](int x, int y) {

if (x < 0 || y < 0 || x >= m || y >= n) return 0;

if (grid[y][x]++) return 1;

return dfs(x + 1, y) & dfs(x - 1, y) & dfs(x, y + 1) & dfs(x, y - 1);

};

int ans = 0;

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

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

if (!grid[i][j]) ans += dfs(j, i);

return ans;

}

};

花花酱 LeetCode 1252. Cells with Odd Values in a Matrix

By zxi on November 9, 2019

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m

Solution 1: Simulation

Time complexity: O((n+m)*k + n*m)
Space complexity: O(n*m)

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

vector<vector<int>> a(n, vector<int>(m));

for (const auto& idx : indices) {

for (int x = 0; x < m; ++x) ++a[idx[0]][x];

for (int y = 0; y < n; ++y) ++a[y][idx[1]];

}

int ans = 0;

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

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

ans += a[i][j] & 1;

return ans;

}

};

Solution 2: Counting

For each row and column, compute how many times it will be increased (odd or even).
For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.
Time complexity: O(n*m + k)
Space complexity: O(n+m)

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

vector<int> cols(m);

vector<int> rows(n);

for (const auto& idx : indices) {

rows[idx[0]] ^= 1;

cols[idx[1]] ^= 1;

}

int ans = 0;

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

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

ans += rows[i] ^ cols[j];

return ans;

}

};

花花酱 1249. Minimum Remove to Make Valid Parentheses

By zxi on November 9, 2019

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

Solution: Couting

Count how many “(” are open and how many “)” left.

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

C++

// Author: Huahua

class Solution {

public:

string minRemoveToMakeValid(string s) {

int close = count(begin(s), end(s), ')');

int open = 0;

string ans;

for (char c : s) {

if (c == '(') {

if (open == close) continue;

++open;

} else if (c == ')') {

--close;

if (open == 0) continue;

--open;

}

ans += c;

}

return ans;

}

};

花花酱 LeetCode 1250. Check If It Is a Good Array

By zxi on November 8, 2019

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Solution: Math

Bézout’s lemma: b[1] * A[1] + b[2] * A[2] + …. + b[n] * A[n] = 1 <==> gcd(A[1], A[2], …, A[n]) = 1 <=> at least two numbers are co-prime

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

C++

// Author: Huahua

class Solution {

public:

bool isGoodArray(vector<int>& nums) {

int g = nums[0];

for (int x : nums)

g = gcd(g, x);

return g == 1;

}

};

花花酱 LeetCode 1247. Minimum Swaps to Make Strings Equal

By zxi on November 7, 2019

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

Constraints:

1 <= s1.length, s2.length <= 1000
s1, s2 only contain 'x' or 'y'.

Solution: Math

if s1[i] == s2[i] than no need to swap, so we can only look for
case1. s1[i] = x, s2[i] = y, xy
case2. s1[i] = y, s2[i] = x, yx

If case1 + case2 is odd, then there’s no solution.

Otherwise we can use one swap to fix two xys (or two yxs)
xx, yy => xy, yx

One special case is there an extra xy and and extra yx, which takes two swaps
xy, yx => yy, xx => xy, xy

Finally,
ans = (case1 + 1) / 2 + (case2 + 1) / 2

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

C++

// Author: Huahua

class Solution {

public:

int minimumSwap(string s1, string s2) {

int xy = 0;

int yx = 0;

for (int i = 0; i < s1.length(); ++i) {

if (s1[i] == 'x' && s2[i] == 'y') ++xy;

if (s1[i] == 'y' && s2[i] == 'x') ++yx;

}

if ((xy + yx) % 2) return -1;

return (xy + 1) / 2 + (yx + 1) / 2;

}

};