花花酱 LeetCode 934. Shortest Bridge

By zxi on November 4, 2018

Problem

https://leetcode.com/problems/shortest-bridge/description/

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

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

Example 2:

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

Example 3:

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

Note:

1 <= A.length = A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

Solution: DFS + BFS

Use DFS to find one island and color all the nodes as 2 (BLUE).
Use BFS to find the shortest path from any nodes with color 2 (BLUE) to any nodes with color 1 (RED).

Time complexity: O(mn)

Space complexity: O(mn)

C++

class Solution {

public:

int shortestBridge(vector<vector<int>>& A) {

queue<pair<int, int>> q;

bool found = false;

for (int i = 0; i < A.size() && !found; ++i)

for (int j = 0; j < A[0].size() && !found; ++j)

if (A[i][j]) {

dfs(A, j, i, q);

found = true;

}

int steps = 0;

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

while (!q.empty()) {

size_t size = q.size();

while (size--) {

int x = q.front().first;

int y = q.front().second;

q.pop();

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

int tx = x + dirs[i];

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

if (tx < 0 || ty < 0 || tx >= A[0].size() || ty >= A.size() || A[ty][tx] == 2) continue;

if (A[ty][tx] == 1) return steps;

A[ty][tx] = 2;

q.emplace(tx, ty);

}

++steps;

}

return -1;

}

private:

void dfs(vector<vector<int>>& A, int x, int y, queue<pair<int, int>>& q) {

if (x < 0 || y < 0 || x >= A[0].size() || y >= A.size() || A[y][x] != 1) return;

A[y][x] = 2;

q.emplace(x, y);

dfs(A, x - 1, y, q);

dfs(A, x, y - 1, q);

dfs(A, x + 1, y, q);

dfs(A, x, y + 1, q);

}

};

Problem

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

Note:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

Solution: DP

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& A) {

int n = A.size();

int m = A[0].size();

vector<vector<int>> dp(n + 2, vector<int>(m + 2));

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

dp[i][0] = dp[i][m + 1] = INT_MAX;

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

dp[i][j] = *min_element(dp[i - 1].begin() + j - 1,

dp[i - 1].begin() + j + 2) + A[i - 1][j - 1];

}

return *min_element(dp[n].begin() + 1, dp[n].end() - 1);

}

};

C++/in place

// Author: Huahua, 12 ms

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& A) {

int n = A.size();

int m = A[0].size();

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

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

int sum = A[i - 1][j];

if (j > 0) sum = min(sum, A[i - 1][j - 1]);

if (j < m - 1) sum = min(sum, A[i - 1][j + 1]);

A[i][j] += sum;

}

return *min_element(begin(A.back()), end(A.back()));

}

};

花花酱 LeetCode 929. Unique Email Addresses

By zxi on October 28, 2018

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one '@' character.

Solution:

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

C++

// Author: Huahua, 24 ms

class Solution {

public:

int numUniqueEmails(vector<string>& emails) {

unordered_set<string> s;

for (const string& email : emails) {

string e;

bool at = false;

bool plus = false;

for (char c : email) {

if (c == '.') {

if (!at) continue;

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

at = true;

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

if (!at) {

plus = true;

continue;

}

if (!at && plus) continue;

e += c;

}

s.insert(std::move(e));

}

return s.size();

}

};

花花酱 LeetCode 927. Three Equal Parts

By zxi on October 20, 2018

Problem

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part;
A[i+1], A[i+2], ..., A[j-1] is the second part, and
A[j], A[j+1], ..., A[A.length - 1] is the third part.
All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

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

Example 2:

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

Note:

3 <= A.length <= 30000
A[i] == 0 or A[i] == 1

Solution:

each part should have the same number of 1 s.

Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.

Time complexity: O(n^2) in theory but close to O(n) in practice

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> threeEqualParts(vector<int>& A) {

string s(begin(A), end(A));

int ones = accumulate(begin(A), end(A), 0);

if (ones % 3 != 0) return {-1, -1};

if (ones == 0) return {0, A.size() - 1};

ones /= 3;

int right = A.size() - 1;

while (ones) if (A[right--]) --ones;

string suffix(begin(s) + right + 1, end(s));

size_t l = suffix.length();

size_t left = s.find(suffix);

if (left == std::string::npos) return {-1, -1};

size_t mid = s.find(suffix, left + l);

if (mid == std::string::npos

|| mid + 2 * l > s.length()) return {-1, -1};

return {left + l - 1, mid + l};

}

};

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems

花花酱 LeetCode DP Summary 动态规划总结

Category 1.1

Template

花花酱 LeetCode 931. Minimum Falling Path Sum

Problem

Solution: DP

C++

C++/in place

花花酱 LeetCode 929. Unique Email Addresses

Solution:

C++

花花酱 LeetCode 927. Three Equal Parts

Problem

Solution:

C++

Huahua's Tech Road

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems

花花酱 LeetCode DP Summary 动态规划总结

Category 1.1

Template

花花酱 LeetCode 931. Minimum Falling Path Sum

Problem

Solution: DP

C++

C++/in place

花花酱 LeetCode 929. Unique Email Addresses

Solution:

C++

花花酱 LeetCode 927. Three Equal Parts

Problem

Solution:

C++