Huahua’s Tech Road

花花酱 LeetCode 999. Available Captures for Rook

By zxi on February 24, 2019

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: 
In this example the rook is able to capture all the pawns.

Example 2:

Input: [[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation: 
Bishops are blocking the rook to capture any pawn.

Example 3:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: 
The rook can capture the pawns at positions b5, d6 and f5.

Note:

board.length == board[i].length == 8
board[i][j] is either 'R', '.', 'B', or 'p'
There is exactly one cell with board[i][j] == 'R'

Solution: Simulation

Time complexity: O(1)
Space complexity: O(1)

C++

class Solution {

public:

int numRookCaptures(vector<vector<char>>& board) {

int ans = 0;

auto check = [&board](int x, int y, int dx, int dy) {

x += dx;

y += dy;

while (x >= 0 && x < 8 && y >= 0 && y < 8) {

if (board[y][x] == 'p') return 1;

if (board[y][x] != '.') break;

x += dx;

y += dy;

}

return 0;

};

array<int, 5> dirs{1, 0, -1, 0, 1};

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

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

if (board[i][j] == 'R')

for (int d = 0; d < 4; ++d)

ans += check(j, i, dirs[d], dirs[d + 1]);

return ans;

}

};

花花酱 LeetCode 998. Maximum Binary Tree II

By zxi on February 24, 2019

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:

If A is empty, return null.
Otherwise, let A[i] be the largest element of A. Create a root node with value A[i].
The left child of root will be Construct([A[0], A[1], ..., A[i-1]])
The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
Return root.

Note that we were not given A directly, only a root node root = Construct(A).

Suppose B is a copy of A with the value val appended to it. It is guaranteed that B has unique values.

Return Construct(B).

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: A = [1,4,2,3], B = [1,4,2,3,5]

Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: A = [2,1,5,4], B = [2,1,5,4,3]

Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: A = [2,1,5,3], B = [2,1,5,3,4]

Note:

1 <= B.length <= 100

Solution: Recursion

Since val is the last element of the array, we compare root->val with val, if root->val > val then val can be inserted into the right subtree recursively, otherwise, root will be the left subtree of val.

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

C++

class Solution {

public:

TreeNode* insertIntoMaxTree(TreeNode* root, int val) {

if (root && root->val > val) {

root->right = insertIntoMaxTree(root->right, val);

return root;

}

auto node = new TreeNode(val);

node->left = root;

return node;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 999. Available Captures for Rook

Solution: Simulation

C++

花花酱 LeetCode 998. Maximum Binary Tree II

Solution: Recursion

C++

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