Posts tagged as “easy”

花花酱 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 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 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 993. Cousins in Binary Tree

By zxi on February 16, 2019

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

The number of nodes in the tree will be between 2 and 100.
Each node has a unique integer value from 1 to 100.

Solution: Preorder traversal

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

C++

// Author: Huahua, running time 8 ms, 11.5 MB

class Solution {

public:

bool isCousins(TreeNode* root, int x, int y) {

preorder(root, x, y, nullptr, 0);

return px_ != py_ && dx_ == dy_;

}

private:

TreeNode* px_;

TreeNode* py_;

int dx_;

int dy_;

void preorder(TreeNode* root, int x, int y, TreeNode* p, int d) {

if (!root) return;

if (root->val == x) {

px_ = p;

dx_ = d;

}

if (root->val == y) {

py_ = p;

dy_ = d;

}

preorder(root->left, x, y, root, d + 1);

preorder(root->right, x, y, root, d + 1);

}

};

Python3

# Author: Huahua, running time: 40 ms, 12.4 MB

class Solution:

def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':

self.px, self.dx = None, -1

self.py, self.dy = None, -2

def preorder(root, parent, d):

if not root: return

if root.val == x:

self.px, self.dx = parent, d

if root.val == y:

self.py, self.dy = parent, d

preorder(root.left, root, d + 1)

preorder(root.right, root, d + 1)

preorder(root, None, 0)

return self.dx == self.dy and self.px != self.py

花花酱 LeetCode 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

Solution: Simulation

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

C++

// Author: Huahua, running time: 136 ms, 10.1 MB

class Solution {

public:

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

vector<int> ans;

ans.reserve(A.size() + 1);

for (int i = A.size() - 1; i >= 0 || K > 0; --i) {

K += (i >= 0 ? A[i] : 0);

ans.push_back(K % 10);

K /= 10;

}

reverse(begin(ans), end(ans));

return ans;

}

};