Huahua’s Tech Road

花花酱 LeetCode 257. Binary Tree Paths

By zxi on January 29, 2020

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n) / output can be O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> ans;

string s;

function<void(TreeNode*, int)> preorder = [&](TreeNode* node, int l) {

if (!node) return;

s += (l > 0 ? "->" : "") + to_string(node->val);

if (!node->left && !node->right)

ans.push_back(s);

preorder(node->left, s.size());

preorder(node->right, s.size());

while (s.size() != l) s.pop_back();

};

preorder(root, 0);

return ans;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 257. Binary Tree Paths

Solution: Recursion

C++

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