Posts published in “Difficulty”

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

By zxi on December 12, 2017

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:

root = [1, 3, 2], k = 1

Diagram of binary tree:

/ \

3 2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the closest leaf node to the target of 1.

Example 2:

Input:

root = [1], k = 1

Output: 1

Explanation: The closest leaf node is the root node itself.

Example 3:

Input:

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Diagram of binary tree:

/ \

2 3

Output: 3

Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int findClosestLeaf(TreeNode* root, int k) {

graph_.clear();

start_ = nullptr;

buildGraph(root, nullptr, k);

queue<TreeNode*> q;

q.push(start_);

unordered_set<TreeNode*> seen;

while (!q.empty()) {

int size = q.size();

while (size-->0) {

TreeNode* curr = q.front();

q.pop();

seen.insert(curr);

if (!curr->left && !curr->right) return curr->val;

for (TreeNode* node : graph_[curr])

if (!seen.count(node)) q.push(node);

}

return 0;

}

private:

void buildGraph(TreeNode* node, TreeNode* parent, int k) {

if (!node) return;

if (node->val == k) start_ = node;

if (parent) {

graph_[node].push_back(parent);

graph_[parent].push_back(node);

}

buildGraph(node->left, node, k);

buildGraph(node->right, node, k);

}

unordered_map<TreeNode*, vector<TreeNode*>> graph_;

TreeNode* start_;

};

花花酱 LeetCode 743. Network Delay Time

By zxi on December 12, 2017

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Idea:

Construct the graph and do a shortest path from K to all other nodes.

Solution 2:

C++ / Bellman-Ford

Time complexity: O(ne)

Space complexity: O(n)

// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

constexpr int MAX_TIME = 101 * 100;

vector<int> dist(N, MAX_TIME);

dist[K - 1] = 0;

for (int i = 1; i < N; ++i)

for (const auto& time : times) {

int u = time[0] - 1, v = time[1] - 1, w = time[2];

dist[v] = min(dist[v], dist[u] + w);

}

int max_dist = *max_element(dist.begin(), dist.end());

return max_dist == MAX_TIME ? -1 : max_dist;

}

};

Solution3:

C++ / Floyd-Warshall

Time complexity: O(n^3)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

vector<vector<int>> d(N, vector<int>(N, -1));

for (auto time : times)

d[time[0] - 1][time[1] - 1] = time[2];

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

d[i][i] = 0;

for (int k = 0; k < N; ++k)

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

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

if (d[i][k] >= 0 && d[k][j] >= 0)

if (d[i][j] < 0 || d[i][j] > d[i][k] + d[k][j])

d[i][j] = d[i][k] + d[k][j];

int ans = INT_MIN;

for (int i = 0; i < N; ++i) {

if (d[K - 1][i] < 0) return -1;

ans = max(ans, d[K - 1][i]);

}

return ans;

}

};

// Author: Huahua

// Runtime: 89 ms

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int N, int K) {

constexpr int MAX_TIME = 101 * 100;

vector<vector<int>> d(N, vector<int>(N, MAX_TIME));

for (auto time : times)

d[time[0] - 1][time[1] - 1] = time[2];

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

d[i][i] = 0;

for (int k = 0; k < N; ++k)

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

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

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int max_time = *max_element(d[K - 1].begin(), d[K - 1].end());

return max_time >= MAX_TIME ? - 1 : max_time;

}

};

花花酱 LeetCode 164. Maximum Gap

By zxi on December 10, 2017

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后，相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input: [5, 0, 4, 2, 12, 10]

Output: 5

Explanation:

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶，只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶（如果有）必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maximumGap(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return 0;

const auto mm = minmax_element(nums.begin(), nums.end());

const int range = *mm.second - *mm.first;

const int bin_size = range / n + 1;

vector<int> min_vals(n, INT_MAX);

vector<int> max_vals(n, INT_MIN);

for (const int num : nums) {

const int index = (num - *mm.first) / bin_size;

min_vals[index] = min(min_vals[index], num);

max_vals[index] = max(max_vals[index], num);

}

int max_gap = 0;

int prev_max = max_vals[0];

for (int i = 1; i < n; ++i) {

if (min_vals[i] != INT_MAX) {

max_gap = max(max_gap, min_vals[i] - prev_max);

prev_max = max_vals[i];

}

return max_gap;

}

};

花花酱 LeetCode 530. Minimum Absolute Difference in BST

By zxi on December 9, 2017

Link

Problem:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

Output:

Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

Idea:

Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).

Solution:

C++ O(n) space

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

std::vector<int> sorted;

inorder(root, sorted);

int min_diff = sorted.back();

for (int i = 1; i < sorted.size(); ++i)

min_diff = min(min_diff, sorted[i] - sorted[i - 1]);

return min_diff;

}

private:

void inorder(TreeNode* root, std::vector<int>& sorted) {

if (!root) return;

inorder(root->left, sorted);

sorted.push_back(root->val);

inorder(root->right, sorted);

}

};

C++ O(h) space

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

min_diff_ = INT_MAX;

prev_ = nullptr;

inorder(root);

return min_diff_;

}

private:

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev_) min_diff_ = min(min_diff_, root->val - *prev_);

prev_ = &root->val;

inorder(root->right);

}

int* prev_;

int min_diff_;

};

Java

// Author: Huahua

// Runtime: 16 ms

class Solution {

public int getMinimumDifference(TreeNode root) {

prev_ = null;

min_diff_ = Integer.MAX_VALUE;

inorder(root);

return min_diff_;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_);

prev_ = root.val;

inorder(root.right);

}

private Integer prev_;

private int min_diff_;

}

Python

"""

Author: Huahua

Runtime: 92 ms

"""

class Solution(object):

def getMinimumDifference(self, root):

def inorder(root):

if not root: return

inorder(root.left)

if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev)

self.prev = root.val

inorder(root.right)

self.prev = None

self.min_diff = float('inf')

inorder(root)

return self.min_diff

Related Problems:

[解题报告] LeetCode 98. Validate Binary Search Tree

花花酱 LeetCode 732. My Calendar III

By zxi on December 6, 2017

Problem:

link: https://leetcode.com/problems/my-calendar-iii/description/

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

The number of calls to MyCalendarThree.book per test case will be at most 400.
In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

Similar to LeetCode 731 My Calendar II Use an ordered / tree map to track the number of event at current time.

For a new book event, increase the number of events at start, decrease the number of events at end.

Scan the timeline to find the maximum number of events.

Solution 1: Count Boundaries

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 116 ms

class MyCalendarThree {

public:

MyCalendarThree() {}

int book(int start, int end) {

++deltas_[start];

--deltas_[end];

int ans = 0;

int curr = 0;

for (const auto& kv : deltas_)

ans = max(ans, curr += kv.second);

return ans;

}

private:

map<int, int> deltas_;

};

Solution 2

C++

// Author: Huahua

// Runtime: 66 ms

class MyCalendarThree {

public:

MyCalendarThree() {

counts_[INT_MIN] = 0;

counts_[INT_MAX] = 0;

max_count_ = 0;

}

int book(int start, int end) {

auto l = prev(counts_.upper_bound(start)); // l->first < start

auto r = counts_.lower_bound(end); // r->first >= end

for (auto curr = l, next = curr; curr != r; curr = next) {

++next;

if (next->first > end)

counts_[end] = curr->second;

if (curr->first <= start && next->first > start)

max_count_ = max(max_count_, counts_[start] = curr->second + 1);

else

max_count_ = max(max_count_, ++curr->second);

}

return max_count_;

}

private:

map<int, int> counts_;

int max_count_;

};

Solution 3: Segment Tree

C++

// Author: Huahua

// Runtime: 63 ms (<95.65%)

class MyCalendarThree {

public:

MyCalendarThree(): max_count_(0) {

root_.reset(new Node(0, 100000000, 0));

}

int book(int start, int end) {

Add(start, end, root_.get());

return max_count_;

}

private:

struct Node {

Node(int l, int r, int count):l(l), m(-1), r(r), count(count){}

int l;

int m;

int r;

int count;

std::unique_ptr<Node> left;

std::unique_ptr<Node> right;

};

void Add(int start, int end, Node* root) {

if (root->m != -1) {

if (end <= root->m)

Add(start, end, root->left.get());

else if(start >= root->m)

Add(start, end, root->right.get());

else {

Add(start, root->m, root->left.get());

Add(root->m, end, root->right.get());

}

return;

}

if (start == root->l && end == root->r)

max_count_ = max(max_count_, ++root->count);

else if (start == root->l) {

root->m = end;

root->left.reset(new Node(start, root->m, root->count + 1));

root->right.reset(new Node(root->m, root->r, root->count));

max_count_ = max(max_count_, root->count + 1);

} else if(end == root->r) {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count + 1));

max_count_ = max(max_count_, root->count + 1);

} else {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count));

Add(start, end, root->right.get());

}

std::unique_ptr<Node> root_;

int max_count_;

};

Python3

"""

Author: Huahua

Runtime: 436 ms (<88.88%)

"""

class Node:

def __init__(self, l, r, count):

self.l = l

self.m = -1

self.r = r

self.count = count

self.left = None

self.right = None

class MyCalendarThree:

def __init__(self):

self.root = Node(0, 10**9, 0)

self.max = 0

def book(self, start, end):

self.add(start, end, self.root)

return self.max

def add(self, start, end, root):

if root.m != -1:

if end <= root.m: self.add(start, end, root.left)

elif start >= root.m: self.add(start, end, root.right)

else:

self.add(start, root.m, root.left)

self.add(root.m, end, root.right)

return

if start == root.l and end == root.r:

root.count += 1

self.max = max(self.max, root.count)

elif start == root.l:

root.m = end

root.left = Node(start, root.m, root.count + 1)

root.right = Node(root.m, root.r, root.count)

self.max = max(self.max, root.count + 1)

elif end == root.r:

root.m = start;

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count + 1)

self.max = max(self.max, root.count + 1)

else:

root.m = start

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count)

self.add(start, end, root.right)

Related Problems: