Huahua's Tech Road

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

By zxi on January 29, 2020

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> levelOrderBottom(TreeNode *root) {

vector<vector<int>> ans;

levelOrderBottom(root, 0, ans);

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

return ans;

}

private:

void levelOrderBottom(TreeNode *root, int depth, vector<vector<int>>& ans) {

if (!root) return;

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

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

levelOrderBottom(root->left, depth + 1, ans);

levelOrderBottom(root->right, depth + 1, ans);

}

};

花花酱 LeetCode 144. Binary Tree Preorder Traversal

By zxi on January 29, 2020

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*)> preorder = [&](TreeNode* n) {

if (!n) return;

ans.push_back(n->val);

preorder(n->left);

preorder(n->right);

};

preorder(root);

return ans;

}

};

Solution 2: Stack

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

stack<TreeNode*> s;

if (root) s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

ans.push_back(n->val);

s.pop();

if (n->right) s.push(n->right);

if (n->left) s.push(n->left);

}

return ans;

}

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

By zxi on January 27, 2020

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

Constraints:

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

Solution: DP

dp[i][k] := min difficulties to schedule jobs 1~i in k days.

Schedule 1 ~ j in k – 1 days and schedule j + 1 ~ i in 1 day.

Init: dp[0][0] = 0
Transition: dp[i][k] := min(dp[j][k -1] + max(jobs[j + 1 ~ i]), k – 1 <= j < i
Answer: dp[n][d]

Time complexity: O(n^2*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minDifficulty(vector<int>& jobs, int d) {

const int n = jobs.size();

if (d > n) return -1;

vector<vector<int>> dp(n + 1, vector<int>(d + 1, INT_MAX / 2));

dp[0][0] = 0;

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

for (int j = i - 1, md = 0; j >= 0; --j) {

md = max(md, jobs[j]);

for (int k = 1; k <= min(i, d); ++k)

dp[i][k] = min(dp[i][k], dp[j][k - 1] + md);

}

return dp[n][d];

}

};

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

By zxi on January 26, 2020

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest numberof cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
All pairs (from_i, to_i) are distinct.

Solution1: Floyd-Warshall

All pair shortest path

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {

vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));

for (const auto& e : edges)

dp[e[0]][e[1]] = dp[e[1]][e[0]] = e[2];

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

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

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

dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);

int ans = -1;

int min_nb = INT_MAX;

for (int u = 0; u < n; ++u) {

int nb = 0;

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

if (v != u && dp[u][v] <= distanceThreshold)

++nb;

if (nb <= min_nb) {

min_nb = nb;

ans = u;

}

return ans;

}

};

Solution 2: Dijkstra’s Algorithm

Time complexity: O(V * ElogV) / worst O(n^3*logn), best O(n^2*logn)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int t) {

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Returns the number of nodes within t from s.

auto dijkstra = [&](int s) {

vector<int> dist(n, INT_MAX / 2);

set<pair<int, int>> q; // <dist, node>

vector<set<pair<int, int>>::const_iterator> its(n);

dist[s] = 0;

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

its[i] = q.emplace(dist[i], i).first;

while (!q.empty()) {

auto it = cbegin(q);

int d = it->first;

int u = it->second;

q.erase(it);

if (d > t) break; // pruning

for (const auto& p : g[u]) {

int v = p.first;

int w = p.second;

if (dist[v] <= d + w) continue;

// Decrease key

q.erase(its[v]);

its[v] = q.emplace(dist[v] = d + w, v).first;

}

return count_if(begin(dist), end(dist), [t](int d) { return d <= t; });

};

int ans = -1;

int min_nb = INT_MAX;

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

int nb = dijkstra(i);

if (nb <= min_nb) {

min_nb = nb;

ans = i;

}

return ans;

}

};

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

By zxi on January 26, 2020

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendly_i and veganFriendly take value 1 when it is true, and 0 when it is false.

Example 1:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

Example 2:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Example 3:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Constraints:

1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Solution

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

C++

// Author: Huahua

class Solution {

public:

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {

vector<pair<int, int>> rs; // <rating, id>

for (auto& r : restaurants)

if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)

rs.emplace_back(r[1], r[0]);

sort(rbegin(rs), rend(rs));

vector<int> ans;

for (const auto& r : rs) ans.push_back(r.second);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 144. Binary Tree Preorder Traversal

Solution 1: Recursion

C++

Solution 2: Stack

C++

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

Solution: DP

C++

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Solution1: Floyd-Warshall

C++

C++

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

Solution

C++