Huahua’s Tech Road

花花酱 LeetCode 997. Find the Town Judge

By zxi on February 23, 2019

In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

Example 1:

Input: N = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

1 <= N <= 1000
trust.length <= 10000
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

Solution: Degree

node with degree (in_degree – out_degree) N – 1 is the judge.

Time complexity: O(N+T)
Space complexity: O(N)

C++

class Solution {

public:

int findJudge(int N, vector<vector<int>>& trusts) {

vector<int> degrees(N + 1);

for (const auto& trust : trusts) {

--degrees[trust[0]];

++degrees[trust[1]];

}

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

if (degrees[i] == N - 1) return i;

return -1;

}

};

LeetCode Weekly Contest 124

By zxi on February 17, 2019

Solutions

花花酱 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 995. Minimum Number of K Consecutive Bit Flips

By zxi on February 17, 2019

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1 <= A.length <= 30000
1 <= K <= A.length

Solution: Greedy

From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.

Time complexity: O(nk) -> O(k)
Space complexity: O(1)

C++ / O(nk)

// Author: Huahua, running time: 5172 ms, 16.4 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

int ans = 0;

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

if (A[i] == 1) continue;

++ans;

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

A[i + j] ^= 1;

}

for (int i = A.size() - K + 1; i < A.size(); ++i)

if (A[i] == 0) return -1;

return ans;

}

};

C++ / O(n)

// Author: Huahua, running time: 100 ms, 19.6 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

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

int ans = 0;

int flip = 0;

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

if (i >= K) flip ^= flipped[i - K];

if ((A[i] ^ flip) == 0) {

if (i + K > A.size()) return -1;

++ans;

flip ^= 1;

flipped[i] = 1;

}

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;

}

};

Huahua's Tech Road

花花酱 LeetCode 997. Find the Town Judge

Solution: Degree

C++

LeetCode Weekly Contest 124

Solutions

花花酱 LeetCode 996. Number of Squareful Arrays

Solution1: DFS

C++

Solution 2: DP Hamiltonian Path

C++

Related Problems

花花酱 LeetCode 995. Minimum Number of K Consecutive Bit Flips

Solution: Greedy

C++ / O(nk)

C++ / O(n)

花花酱 LeetCode 994. Rotting Oranges

Solution: BFS

C++