Posts tagged as “DFS”

花花酱 LeetCode 980. Unique Paths III

By zxi on January 20, 2019

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Note:

1 <= grid.length * grid[0].length <= 20

count how many empty blocks there are and try all possible paths to end point and check whether we visited every empty blocks or not.

Solution: Brute force / DP

C++/DFS

class Solution {

public:

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

int sx = -1;

int sy = -1;

int n = 1;

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

for (int j = 0; j < grid[0].size(); ++j)

if (grid[i][j] == 0) ++n;

else if (grid[i][j] == 1) { sx = j; sy = i; }

return dfs(grid, sx, sy, n);

}

private:

int dfs(vector<vector<int>>& grid, int x, int y, int n) {

if (x < 0 || x == grid[0].size() ||

y < 0 || y == grid.size() ||

grid[y][x] == -1) return 0;

if (grid[y][x] == 2) return n == 0;

grid[y][x] = -1;

int paths = dfs(grid, x + 1, y, n - 1) +

dfs(grid, x - 1, y, n - 1) +

dfs(grid, x, y + 1, n - 1) +

dfs(grid, x, y - 1, n - 1);

grid[y][x] = 0;

return paths;

};

C++/DP

class Solution {

public:

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

const int n = grid.size();

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

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

vector<vector<vector<short>>> cache(n, vector<vector<short>>(m, vector<short>(1 << n * m, -1)));

int sx = -1;

int sy = -1;

int state = 0;

auto key = [m](int x, int y) { return 1 << (y * m + x); };

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

if (cache[y][x][state] != -1) return cache[y][x][state];

if (grid[y][x] == 2) return static_cast<short>(state == 0);

int paths = 0;

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

const int tx = x + dirs[i];

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

if (tx < 0 || tx == m || ty < 0 || ty == n || grid[ty][tx] == -1) continue;

if (!(state & key(tx, ty))) continue;

paths += dfs(tx, ty, state ^ key(tx, ty));

}

return cache[y][x][state] = paths;

};

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

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

if (grid[y][x] == 0 || grid[y][x] == 2) state |= key(x, y);

else if (grid[y][x] == 1) { sx = x; sy = y; }

return dfs(sx, sy, state);

}

};

花花酱 LeetCode 967. Numbers With Same Consecutive Differences

By zxi on December 30, 2018

Problem

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

Solution: Search

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

C++/DFS

// Author: Huahua, running time: 8ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

vector<int> ans;

if (N == 1) ans.push_back(0);

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

dfs(N - 1, K, i, ans);

return ans;

}

private:

void dfs(int N, int K, int cur, vector<int>& ans) {

if (N == 0) {

ans.push_back(cur);

return;

}

int l = cur % 10;

if (l + K < 10)

dfs(N - 1, K, cur * 10 + l + K, ans);

if (l >= K && K != 0)

dfs(N - 1, K, cur * 10 + l - K, ans);

}

};

C++/BFS

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

deque<int> q{1,2,3,4,5,6,7,8,9};

if (N == 1) q.push_front(0);

while (--N) {

int size = q.size();

while (size--) {

int num = q.front(); q.pop_front();

int r = num % 10;

if (r + K <= 9)

q.push_back(num * 10 + r + K);

if (r - K >= 0 && K != 0)

q.push_back(num * 10 + r - K);

}

return vector<int>(cbegin(q), cend(q));

}

};

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Combination

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

Implemention 1: DFS

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

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

vector<vector<int>> ans;

vector<int> cur;

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

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

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

ans.push_back(cur);

return;

}

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

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

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

const int n = nums.size();

vector<vector<int>> ans;

for (int s = 0; s < 1 << n; ++s) {

vector<int> cur;

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

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

Knapsack Problem 背包问题

By zxi on November 10, 2018

Videos

上期节目中我们对动态规划做了一个总结，这期节目我们来聊聊背包问题。

背包问题是一个NP-complete的组合优化问题，Search的方法需要O(2^N)时间才能获得最优解。而使用动态规划，我们可以在伪多项式（pseudo-polynomial time）时间内获得最优解。

0-1 Knapsack Problem 0-1背包问题

Problem

Given N items, w[i] is the weight of the i-th item and v[i] is value of the i-th item. Given a knapsack with capacity W. Maximize the total value. Each item can be use 0 or 1 time.

0-1背包问题的通常定义是：一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够获得的最大价值是多少？每件物品可以使用0次或者1次。

例子：

重量 w = [1, 1, 2, 2]

价值 v = [1, 3, 4, 5]

背包承重 W = 4

最大价值为9，可以选第1,2,4件物品，也可以选第3，4件物品；总重量为4，总价值为9。

动态规划的状态转移方程为：

1	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

Solutions

Search

def knapsack01DFS(w, v, W):

def dfs(s, cur_w, cur_v, ans):

ans[0] = max(ans[0], cur_v)

if s == N: return

for i in range(s, N):

if cur_w + w[i] <= W:

dfs(i + 1, cur_w + w[i], cur_v + v[i], ans)

ans = [0]

dfs(0, 0, 0, ans)

return ans[0]

DP2

def knapsack01(w, v, W):

dp = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N + 1):

dp[i] = dp[i-1].clone()

for j in range(w[i], W + 1):

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])

return max(dp[N])

DP1/tmp

def knapsack01R(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

tmp = list(dp)

for j in range(w[i], W + 1):

tmp[j] = max(tmp[j], dp[j - w[i]] + v[i])

dp = tmp

return max(dp)

DP1/push

def knapsack01R2(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

for j in range(W, w[i] - 1, -1):

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

return max(dp)

DP1/pull

def knapsack01R1(w, v, W):

dp = [0] * (W + 1)

for i in range(0, N):

for j in range(W - w[i], -1, -1):

dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])

return max(dp)

Unbounded Knapsack Problem 完全背包

完全背包、多重背包是常见的变形。和01背包的区别在于，完全背包每件物品可以使用无限多次，而多重背包每件物品最多可以使用n[i]次。两个问题都可以转换成01背包问题进行求解。

但是Naive的转换会大大增加时间复杂度：

完全背包：“复制”第i件物品到一共有 W/w[i] 件

多重背包：“复制”第i件物品到一共有 n[i] 件

然后直接调用01背包进行求解。

时间复杂度：

完全背包 O(Σ(W/w[i])*W)

多重背包 O(Σn[i]*W)

不难看出时间复杂度 = O(物品数量*背包承重)

背包承重是给定的，要降低运行时候，只有减少物品数量。但怎样才能减少总的物品数量呢？

这就涉及到二进制思想：任何一个正整数都可以用 (1, 2, 4, …, 2^K)的组合来表示。例如14 = 2 + 4 + 8。
原本需要放入14件相同的物品，现在只需要放入3件（重量和价值是原物品的2倍，4倍，8倍）。大幅降低了总的物品数量从而降低运行时间。

完全背包：对于第i件物品，我们只需要创建k = log(W/w[i])件虚拟物品即可。

每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^k*(w[i], v[i])。

多重背包：对于第i件物品，我们只需要创建k + 1件虚拟物品即可，其中k = log(n[i])。

每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^(k-1)*(w[i], v[i]), 以及 (n[i] – 2^k – 1) * (w[i], v[i])。

例如：n[i] = 14, k = 3, 虚拟物品的倍数为 1, 2, 4 和 7，这4个数组合可以组成1 ~ 14中的任何一个数，并且不会>14，即不超过n[i]。

二进制转换后直接调用01背包即可

时间复杂度：

完全背包 O(Σlog(W/w[i])*W)

多重背包 O(Σlog(n[i])*W)

空间复杂度 O(W)

其实完全背包和多重背包都可以在 O(NW)时间内完成，前者在视频中有讲到，后者属于超纲内容，以后有机会再和大家深入分享。

Bounded Knapsack Problem 多重背包

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

}

};

Posts tagged as “DFS”

花花酱 LeetCode 980. Unique Paths III

Solution: Brute force / DP

C++/DFS

C++/DP

花花酱 LeetCode 967. Numbers With Same Consecutive Differences

Problem

Solution: Search

C++/DFS

C++/BFS

花花酱 LeetCode 78. Subsets

Solution: Combination

Implemention 1: DFS

C++

Python3

Implementation 2: Binary

C++

Python3

Knapsack Problem 背包问题

Videos

0-1 Knapsack Problem 0-1背包问题

Problem

Solutions

Search

DP2

DP1/tmp

DP1/push

DP1/pull

Unbounded Knapsack Problem 完全背包

Bounded Knapsack Problem 多重背包

花花酱 LeetCode 934. Shortest Bridge

Problem

Solution: DFS + BFS

C++

Related Problems