Posts tagged as “medium”

花花酱 LeetCode 1314. Matrix Block Sum

By zxi on January 11, 2020

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Solution: 2D range query

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

C++

// Author: Huahua, 20 ms

class Solution {

public:

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {

const int n = mat.size();

const int m = mat[0].size();

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

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x)

dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1];

auto ans = mat;

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x) {

int x1 = max(1, x - K);

int x2 = min(m, x + K);

int y1 = max(1, y - K);

int y2 = min(n, y + K);

ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];

}

return ans;

}

};

花花酱 LeetCode 1315. Sum of Nodes with Even-Valued Grandparent

By zxi on January 11, 2020

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) {

if (!root) return 0;

return sumEvenGrandparent(root->left, root->val, p)

+ sumEvenGrandparent(root->right, root->val, p)

+ (gp & 1 ? 0 : root->val);

}

};

花花酱 LeetCode 1310. XOR Queries of a Subarray

By zxi on January 5, 2020

Given the array arr of positive integers and the array queries where queries[i] = [L_i,R_i], for each query i compute the XOR of elements from L_i to Ri (that is, arr[L_i] xor arr[L_i+1] xor ... xor arr[R_i] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {

// xors[i + 1] = arr[0] ^ arr[1] ^ ... ^ arr[i]

vector<int> xors(arr.size() + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

}

vector<int> ans;

for (const auto& q : queries) {

const int l = q[0];

const int r = q[1];

ans.push_back(xors[r + 1] ^ xors[l]);

}

return ans;

}

};

tby

花花酱 LeetCode 2. Add Two Numbers

By zxi on December 30, 2019

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Time complexity: O(max(n,m))
Space complexity: O(max(n,m))

C++

// Author: Huahua

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode tail = new ListNode(0);

ListNode dummy = tail;

int sum = 0;

while (l1 != null || l2 != null || sum > 0) {

sum += (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);

tail.next = new ListNode(sum % 10);

tail = tail.next;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

sum /= 10;

}

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

dummy = tail = ListNode(0)

s = 0

while l1 or l2 or s:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

tail.next = ListNode(s % 10)

tail = tail.next

s //= 10

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

return dummy.next

花花酱 LeetCode 1306. Jump Game III

By zxi on December 29, 2019

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

Solution: BFS / DFS

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

C++

// Author: Huahua

class Solution {

public:

bool canReach(vector<int>& arr, int start) {

const int n = arr.size();

vector<int> seen(n);

seen[start] = 1;

queue<int> q;

q.push(start);

while (q.size()) {

int cur = q.front();

q.pop();

if (arr[cur] == 0) return true;

for (int i : {-1, 1}) {

int t = cur + i * arr[cur];

if (t < 0 || t >= n || seen[t]) continue;

q.push(t);

seen[t] = 1;

}

return false;

}

};