花花酱 LeetCode 429. N-ary Tree Level Order Traversal

By zxi on July 14, 2018

Problem

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[
     [1],
     [3,2,4],
     [5,6]
]

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution1: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

vector<vector<int>> ans;

preorder(root, 0, ans);

return ans;

}

private:

void preorder(Node* root, int d, vector<vector<int>>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(root->val);

for (auto child : root->children)

preorder(child, d + 1, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

if (!root) return {};

vector<vector<int>> ans;

queue<Node*> q;

q.push(root);

int depth = 0;

while (!q.empty()) {

int size = q.size();

ans.push_back({});

while (size--) {

Node* n = q.front(); q.pop();

ans[depth].push_back(n->val);

for (auto child : n->children)

q.push(child);

}

++depth;

}

return ans;

}

};

花花酱 LeetCode 350. Intersection of Two Arrays II

By zxi on July 14, 2018

Problem

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution1: Hashtable

Time complexity: O(m + n)

Space complexity: O(m)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

unordered_map<int, int> count;

vector<int> ans;

for (int num : nums1)

++count[num];

for (int num : nums2)

if (count.count(num) &&count[num] > 0) {

--count[num];

ans.push_back(num);

}

return ans;

}

};

花花酱 LeetCode 542. 01 Matrix

By zxi on July 14, 2018

Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Solution 1: DP

Two passes:

down, right
up, left

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 132 ms

class Solution {

public:

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

int m = matrix.size();

int n = matrix[0].size();

vector<vector<int>> ans(m, vector<int>(n, INT_MAX - m * n));

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

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

if (matrix[i][j]) {

if (i > 0) ans[i][j] = min(ans[i][j], ans[i - 1][j] + 1);

if (j > 0) ans[i][j] = min(ans[i][j], ans[i][j - 1] + 1);

} else {

ans[i][j] = 0;

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i < m - 1) ans[i][j] = min(ans[i][j], ans[i + 1][j] + 1);

if (j < n - 1) ans[i][j] = min(ans[i][j], ans[i][j + 1] + 1);

}

return ans;

}

};

Solution 2: BFS

Start from all 0 cells and find shortest paths to rest of the cells.

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 136 ms

class Solution {

public:

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

queue<pair<int, int>> q;

vector<vector<int>> seen(m, vector<int>(n, 0));

vector<vector<int>> ans(m, vector<int>(n, INT_MAX));

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

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

if (matrix[i][j] == 0) {

q.push({i, j});

seen[i][j] = 1;

}

vector<int> dirs{0, -1, 0, 1, 0};

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto pair = q.front(); q.pop();

int i = pair.first;

int j = pair.second;

ans[i][j] = steps;

for (int k = 0; k < 4; ++k) {

int x = j + dirs[k];

int y = i + dirs[k + 1];

if (x < 0 || x >= n || y < 0 || y >= m || seen[y][x]) continue;

seen[y][x] = 1;

q.push({y, x});

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 523. Continuous Subarray Sum

By zxi on July 14, 2018

Problem

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Special case:

nums = [0,0], k = 0, return = True

Solution: Prefix Sum Reminder

Time complexity: O(n)

Space complexity: O(min(n, k))

// Author: Huahua

// Running time: 16 ms (<99.62%)

class Solution {

public:

bool checkSubarraySum(vector<int>& nums, int k) {

unordered_map<int, int> m; // sum % k -> first index

m[0] = -1;

int sum = 0;

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

sum += nums[i];

if (k != 0) sum %= k;

if (m.count(sum)) {

if (i - m.at(sum) > 1) return true;

} else {

m[sum] = i;

}

return false;

}

};

Problem

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maxDepth(Node* root) {

if (root == nullptr) return 0;

int depth = 0;

for (auto child : root->children)

depth = max(depth, maxDepth(child));

return depth + 1;

}

};

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable

花花酱 LeetCode 542. 01 Matrix

Problem

Solution 1: DP

Solution 2: BFS

花花酱 LeetCode 523. Continuous Subarray Sum

Problem

Special case:

Solution: Prefix Sum Reminder

Related Problems

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

Problem

Solution: Recursion

Related Problems

Huahua's Tech Road

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable

花花酱 LeetCode 542. 01 Matrix

Problem

Solution 1: DP

Solution 2: BFS

花花酱 LeetCode 523. Continuous Subarray Sum

Problem

Special case:

Solution: Prefix Sum Reminder

Related Problems

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

Problem

Solution: Recursion

Related Problems