Posts tagged as “easy”

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

}

};

花花酱 LeetCode 985. Sum of Even Numbers After Queries

By zxi on February 2, 2019

Problem

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

Solution: Simulation

Time complexity: O(n + |Q|)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 100 ms / 6.5 MB

class Solution {

public:

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {

int sum = 0;

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

if (A[i] % 2 == 0)

sum += A[i];

vector<int> ans;

for (const auto& query : queries) {

int& a = A[query[1]];

if (a % 2 == 0)

sum -= a;

a += query[0];

if (a % 2 == 0)

sum += a;

ans.push_back(sum);

}

return ans;

}

};

Python3

# Author: Huahua, running time: 188 ms / 16.4MB

class Solution:

def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]':

s = sum(x for x in A if x % 2 == 0)

ans = []

for val, index in queries:

if A[index] % 2 == 0: s -= A[index]

A[index] += val

if A[index] % 2 == 0: s += A[index]

ans.append(s)

return ans

花花酱 LeetCode 973. K Closest Points to Origin

By zxi on January 13, 2019

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 
Output: [[-2,2]] 
Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 
Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Solution: Sort

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

C++

// Author: Huahua, Running time: 180 ms

class Solution {

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {

vector<long> s(points.size());

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

s[i] = (static_cast<long>(points[i][0] * points[i][0] +

points[i][1] * points[i][1]) << 32) | i;

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

vector<vector<int>> ans(K);

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

ans[i] = points[static_cast<int>(s[i])];

return ans;

}

};

Python3

# Author: Huahua, running time: 528 ms

class Solution:

def kClosest(self, points, K):

return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]