Posts published in “Search”

花花酱 LeetCode 996. Number of Squareful Arrays

By zxi on February 17, 2019

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

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

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solution1: DFS

Try all permutations with pruning.

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

C++

// Author: Huahua, running time: 4 ms, 8.8 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

std::sort(begin(A), end(A));

vector<int> cur;

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

int ans = 0;

dfs(A, cur, used, ans);

return ans;

}

private:

bool squareful(int x, int y) {

int s = sqrt(x + y);

return s * s == x + y;

}

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

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

++ans;

return;

}

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

if (used[i]) continue;

// Avoid duplications.

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

// Prune invalid solutions.

if (!cur.empty() && !squareful(cur.back(), A[i])) continue;

cur.push_back(A[i]);

used[i] = 1;

dfs(A, cur, used, ans);

used[i] = 0;

cur.pop_back();

}

};

Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

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

C++

// Author: Huahua, running time: 20 ms, 14.9 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

const int n = A.size();

// For deduplication.

std::sort(begin(A), end(A));

// g[i][j] == 1 if A[i], A[j] are squareful.

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

// dp[s][i] := number of ways to reach state s and ends with node i.

vector<vector<int>> dp(1 << n, vector<int>(n));

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

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

if (i == j) continue;

int r = sqrt(A[i] + A[j]);

if (r * r == A[i] + A[j])

g[i][j] = 1;

}

// For the same numbers, only the first one can be the starting point.

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

if (i == 0 || A[i] != A[i - 1])

dp[(1 << i)][i] = 1;

int ans = 0;

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

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

if (!dp[s][i]) continue;

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

if (!g[i][j]) continue;

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

// Only the first one can be used as the dest.

if (j > 0 && !(s & (1 << (j - 1))) && A[j - 1] == A[j]) continue;

dp[s | (1 << j)][j] += dp[s][i];

}

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

ans += dp[(1 << n) - 1][i];

return ans;

}

};

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

Posts published in “Search”

花花酱 LeetCode 996. Number of Squareful Arrays

Solution1: DFS

C++

Solution 2: DP Hamiltonian Path

C++

Related Problems

花花酱 LeetCode 994. Rotting Oranges

Solution: BFS

C++

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