Posts published in “Search”

花花酱 LeetCode 994. Rotting Oranges

By zxi on February 16, 2019

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1instead.

Example 1:

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

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

Solution: BFS

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, Running time: 12 ms, 10.8 MB

class Solution {

public:

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

const int m = grid.size();

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

queue<pair<int,int>> q;

int fresh = 0;

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

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

if (grid[i][j] == 1) ++fresh;

else if (grid[i][j] == 2) q.emplace(j, i);

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

int days = 0;

while (!q.empty() && fresh) {

int 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 dx = x + dirs[i];

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

if (dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dy][dx] != 1) continue;

--fresh;

grid[dy][dx] = 2;

q.emplace(dx, dy);

}

++days;

}

return fresh ? -1 : days;

}

};

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

花花酱 LeetCode 943. Find the Shortest Superstring

By zxi on November 18, 2018

Problem

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

1 <= A.length <= 12
1 <= A[i].length <= 20

Solution 1: Search + Pruning

Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].

Time complexity: O(n!)

Space complexity: O(n)

C++

// Author: Huahua, running time: 692 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

g_ = vector<vector<int>>(n, vector<int>(n));

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

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

g_[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g_[i][j] = A[j].length() - k;

}

vector<int> path(n);

best_len_ = INT_MAX;

dfs(A, 0, 0, 0, path);

string ans = A[best_path_[0]];

for (int k = 1; k < best_path_.size(); ++k) {

int i = best_path_[k - 1];

int j = best_path_[k];

ans += A[j].substr(A[j].length() - g_[i][j]);

}

return ans;

}

private:

vector<vector<int>> g_;

vector<int> best_path_;

int best_len_;

void dfs(const vector<string>& A, int d, int used, int cur_len, vector<int>& path) {

if (cur_len >= best_len_) return;

if (d == A.size()) {

best_len_ = cur_len;

best_path_ = path;

return;

}

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

if (used & (1 << i)) continue;

path[d] = i;

dfs(A,

d + 1,

used | (1 << i),

d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],

path);

}

};

Java

// Author: Huahua, 439 ms, 35.8MB

class Solution {

private int n;

private int[][] g;

private String[] a;

private int best_len;

private int[] path;

private int[] best_path;

private void dfs(int d, int used, int cur_len) {

if (cur_len >= best_len) return;

if (d == n) {

best_len = cur_len;

best_path = path.clone();

return;

}

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

if ((used & (1 << i)) != 0) continue;

path[d] = i;

dfs(d + 1,

used | (1 << i),

d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);

}

public String shortestSuperstring(String[] A) {

n = A.length;

g = new int[n][n];

a = A;

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

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

g[i][j] = A[j].length();

for (int k = 1; k <= Math.min(A[i].length(), A[j].length()); ++k)

if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))

g[i][j] = A[j].length() - k;

}

path = new int[n];

best_len = Integer.MAX_VALUE;

dfs(0, 0, 0);

String ans = A[best_path[0]];

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

int i = best_path[k - 1];

int j = best_path[k];

ans += A[j].substring(A[j].length() - g[i][j]);

}

return ans;

}

Solution 2: DP

g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].

We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.

We can solve it with DP that uses exponential time.

dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.

e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).

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

Space complexity: O(n * 2^n)

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

vector<vector<int>> g(n, vector<int>(n));

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

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

g[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g[i][j] = A[j].length() - k;

}

vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));

vector<vector<int>> parent(1 << n, vector<int>(n, -1));

for (int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();

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

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

if (!(s & (1 << j))) continue;

int ps = s & ~(1 << j);

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

if (dp[ps][i] + g[i][j] < dp[s][j]) {

dp[s][j] = dp[ps][i] + g[i][j];

parent[s][j] = i;

}

auto it = min_element(begin(dp.back()), end(dp.back()));

int j = it - begin(dp.back());

int s = (1 << n) - 1;

string ans;

while (s) {

int i = parent[s][j];

if (i < 0) ans = A[j] + ans;

else ans = A[j].substr(A[j].length() - g[i][j]) + ans;

s &= ~(1 << j);

j = i;

}

return ans;

}

};