Posts tagged as “DFS”

花花酱 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 set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution: Graph Coloring

Color a node with one color, and color all it’s disliked nodes with another color, if can not finish return false.

Time complexity: O(V+E)

Space complexity: O(V+E)

C++ / DFS

// Author: Huahua

// Running time: 96 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

C++ / BFS

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

vector<vector<int>> g(N);

for (const auto& d : dislikes) {

g[d[0] - 1].push_back(d[1] - 1);

g[d[1] - 1].push_back(d[0] - 1);

}

queue<int> q;

vector<int> colors(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors[i] != 0) continue;

q.push(i);

colors[i] = 1;

while (!q.empty()) {

int cur = q.front(); q.pop();

for (int nxt : g[cur]) {

if (colors[nxt] == colors[cur]) return false;

if (colors[nxt] != 0) continue;

colors[nxt] = -colors[cur];

q.push(nxt);

}

return true;

}

};

Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Solution: Search

Try all combinations.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {

int with_offer = INT_MAX;

for (const auto& offer : special) {

vector<int> new_needs(needs);

bool valid_offer = true;

for (int i = 0; i < price.size(); ++i)

if (!(valid_offer &= ((new_needs[i] -= offer[i]) >= 0)))

break;

if (!valid_offer) continue;

with_offer = min(with_offer, shoppingOffers(price, special, new_needs) + offer.back());

}

int without_offer = inner_product(begin(price), end(price), begin(needs), 0);

return min(with_offer, without_offer);

}

};

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

By zxi on July 26, 2018

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1 <= S.length <= 200
S contains only digits.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<int> splitIntoFibonacci(string s) {

const int n = s.length();

vector<int> nums;

function<bool(int)> dfs = [&](int pos) {

if (pos == n) return nums.size() >= 3;

int max_len = s[pos] == '0' ? 1 : 10;

long num = 0;

for (int i = pos; i < min(pos + max_len, n); ++i) {

num = num * 10 + (s[i] - '0');

if (num > INT_MAX) break;

if (nums.size() >= 2) {

long sum = nums.rbegin()[0];

sum += nums.rbegin()[1];

if (num > sum) break;

else if (num < sum) continue;

// num must equaals to sum.

}

nums.push_back(num);

if (dfs(i + 1)) return true;

nums.pop_back();

}

return false;

};

dfs(0);

return nums;

}

};

花花酱 LeetCode 47. Permutations II

By zxi on July 26, 2018

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

Solution

Time complexity: O(n!)

Space complexity: O(n + k)

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

vector<vector<int>> permuteUnique(vector<int>& nums) {

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> used(nums.size());

vector<int> cur;

dfs(nums, cur, used, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, vector<int>& cur, vector<int>& used, vector<vector<int>>& ans) {

if (cur.size() == nums.size()) {

ans.push_back(cur);

return;

}

for (int i = 0; i < nums.size(); ++i) {

if (used[i]) continue;

// Same number can be only used once at each depth.

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

used[i] = 1;

cur.push_back(nums[i]);

dfs(nums, cur, used, ans);

cur.pop_back();

used[i] = 0;

}

};

Posts tagged as “DFS”

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem

花花酱 LeetCode 638. Shopping Offers

Problem

Solution: Search

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Solution: DFS

花花酱 LeetCode 47. Permutations II

Problem

Solution

Related Problems