You've decided to make a road trip across the country in a straight line. You have chosen the direction you'd like to travel and made a list of cities in that direction that have gas stations to stop at and fill up your tank. To make sure that this route is viable, you need to know the distances between the adjacent cities in order to be able to travel this distance on a single tank of gasoline. (No one likes running out of gas.) but you only know distances to each city from your starting point. Input: Your program should read lines from standard input. Each line contains the list of cities and distances to them, comma-delimited, from the starting point of your trip. You start your trip at point 0. The cities with their distances are separated by semicolon. Output: Print out the distance from the starting point to the nearest city, and the distances between two nearest cities separated by comma, in order they appear on the route.
Example 1
Input:
input = "Rkbs, 5453; Wdqiz, 1245; Rwds, 3890; Ujma, 5589; Tbzmo, 1303;"Output:
"1245, 58, 2587, 1563, 136"Explanation: Will add once find reference :P
解法
解析格式 City, dist; City, dist; ...，把 (name, dist) 收集；按 dist 升序排序；输出最小 dist + 相邻差。复杂度 O(n log n)。
import re
def calculate_distance(input_str: str) -> str:
parts = [p.strip() for p in input_str.strip().rstrip(";").split(";") if p.strip()]
cities = []
for p in parts:
name, dist = p.split(",")
cities.append(int(dist.strip()))
cities.sort()
out = [str(cities[0])]
for i in range(1, len(cities)):
out.append(str(cities[i] - cities[i - 1]))
return ", ".join(out)import java.util.*;
class Solution {
String calculateDistance(String input) {
String[] entries = input.trim().replaceAll(";\\s*$", "").split(";");
List<Integer> dists = new ArrayList<>();
for (String e : entries) {
String[] kv = e.trim().split(",");
dists.add(Integer.parseInt(kv[1].trim()));
}
Collections.sort(dists);
StringBuilder sb = new StringBuilder(dists.get(0).toString());
for (int i = 1; i < dists.size(); i++) sb.append(", ").append(dists.get(i) - dists.get(i - 1));
return sb.toString();
}
}class Solution {
public:
string calculateDistance(string input) {
vector<int> dists;
string cur;
for (char c : input + ";") {
if (c == ';') {
if (!cur.empty()) {
auto comma = cur.find(',');
if (comma != string::npos) {
string d = cur.substr(comma + 1);
string trim;
for (char x : d) if (x != ' ') trim += x;
if (!trim.empty()) dists.push_back(stoi(trim));
}
cur.clear();
}
} else cur += c;
}
sort(dists.begin(), dists.end());
string out = to_string(dists[0]);
for (size_t i = 1; i < dists.size(); ++i) out += ", " + to_string(dists[i] - dists[i - 1]);
return out;
}
};A company wants to track change in their organization by knowing how many levels exist between any two employees. This number will help them know who is being promoted and who is not. For example: If Susan reports to John and John reports to Amy. Then, there are 2 level between Susan and Amy. Write a program that will count how many levels exist between any two names in a hierarchy of employees. The program must read a list of name pairs that represent an employee and their manager. HINT: The two names to compare may be in different parts of the organizational tree and not have a direct managerial line. Input: The first line of input will be a pair of names to compare. All subsequent lines will be employee/manager pairs. The company's complete hierarchy will be included so no incomplete trees will exist.
Constraints
N/A
Example 1
Input:
pairOfNamesToCompare = ["Susan", "Amy"]
employeePairs = [["Susan", "John"], ["John", "Amy"]]Output:
2Explanation: The number of levels between the pairs requested, including the top manager's level. In the example above, the Output should be 2. P.S. I am not 100% sure about the input of the example. If you find anythign wrong, pls feel free to lmk! Manyyy thanks in advance!!
Example 2
Input:
pairOfNamesToCompare = ["Scott", "David"]
employeePairs = [["Terry", "David"], ["Kyle", "David"], ["Ben", "Kyle"], ["Scott", "Jon"], ["Chris", "Scott"], ["Jon", "Kenny"], ["Kenny", "David"], ["David", "Mike"]]Output:
3Explanation: N/A for now
Example 3
Input:
pairOfNamesToCompare = ["Ben", "Jon"]
employeePairs = [["Terry", "David"], ["Kyle", "David"], ["Ben", "Kyle"], ["Scott", "Jon"], ["Chris", "Scott"], ["Jon", "Kenny"], ["Kenny", "David"]]Output:
0Explanation: N/A for now
Example 4
Input:
pairOfNamesToCompare = ["Christy", "Susan"]
employeePairs = [["Aimee", "Melissa"], ["Melissa", "Susan"], ["Stacy", "Corinne"], ["Gabrielle", "Melissa"], ["Corinne", "Melissa"], ["Christy", "Stacy"], ["Pat", "Christy"]]Output:
4Explanation: N/A for now
解法
建 child -> parent 映射；分别从两人沿 manager 链走到根，记录访问的所有祖先及距离。LCA = 第一个公共祖先。结果 = depth1[lca] + depth2[lca]。若没有公共祖先返回 0。复杂度 O(n)。
from typing import List
def corporate_ladder(pair: List[str], pairs: List[List[str]]) -> int:
parent = {a: b for a, b in pairs}
def chain(x):
d = {x: 0}
cur, depth = x, 0
while cur in parent:
cur = parent[cur]
depth += 1
d[cur] = depth
return d
c1 = chain(pair[0])
c2 = chain(pair[1])
best = -1
for node, d in c1.items():
if node in c2:
total = d + c2[node]
if best == -1 or total < best:
best = total
return best if best != -1 else 0import java.util.*;
class Solution {
int corporateLadder(String[] pair, String[][] pairs) {
Map<String, String> parent = new HashMap<>();
for (String[] p : pairs) parent.put(p[0], p[1]);
Map<String, Integer> c1 = chain(pair[0], parent);
Map<String, Integer> c2 = chain(pair[1], parent);
int best = -1;
for (var e : c1.entrySet()) {
if (c2.containsKey(e.getKey())) {
int total = e.getValue() + c2.get(e.getKey());
if (best == -1 || total < best) best = total;
}
}
return best == -1 ? 0 : best;
}
private Map<String, Integer> chain(String x, Map<String, String> parent) {
Map<String, Integer> d = new HashMap<>();
d.put(x, 0);
String cur = x; int depth = 0;
while (parent.containsKey(cur)) {
cur = parent.get(cur);
depth++;
d.put(cur, depth);
}
return d;
}
}class Solution {
public:
int corporateLadder(vector<string>& pair_, vector<vector<string>>& pairs) {
unordered_map<string, string> parent;
for (auto& p : pairs) parent[p[0]] = p[1];
auto chain = [&](const string& x) {
unordered_map<string, int> d;
d[x] = 0;
string cur = x;
int depth = 0;
while (parent.count(cur)) {
cur = parent[cur];
depth++;
d[cur] = depth;
}
return d;
};
auto c1 = chain(pair_[0]);
auto c2 = chain(pair_[1]);
int best = -1;
for (auto& [k, d] : c1) {
auto it = c2.find(k);
if (it != c2.end()) {
int total = d + it->second;
if (best == -1 || total < best) best = total;
}
}
return best == -1 ? 0 : best;
}
};A company wants to track change in their organization by knowing how many levels exist between any two employees. This number will help them know who is being promoted and who is not. For example: If Susan reports to John and John reports to Amy. Then, there are 2 levels between Susan and Amy. Write a program that will count how many levels exist between any two names in a hierarchy of employees. The program must read a list of name pairs that represent an employee and their manager. HINT: The two names to compare may be in different parts of the organizational tree and not have a direct managerial line. Input: The first line of input will be a pair of names to compare. All subsequent lines will be employee/manager pairs. The company's complete hierarchy will be included so no incomplete trees will exist.
Constraints
N/A
Example 1
Input:
employeePairs = [['Susan', 'John'], ['John', 'Amy']]
employee1 = "Susan"
employee2 = "Amy"Output:
2Explanation: If Susan reports to John and John reports to Amy. Then, there are 2 levels between Susan and Amy.
Example 2
Input:
employeePairs = [['Scott', 'David'], ['Terry', 'David'], ['Kyle', 'David'], ['Ben', 'Kyle'], ['Scott', 'Jon'], ['Chris', 'Scott'], ['Jon', 'Kenny'], ['Kenny', 'David'], ['David', 'Mike']]
employee1 = "Scott"
employee2 = "David"Output:
3Explanation: To find the levels between Scott and David, we can trace the hierarchy as follows: Scott reports to Jon, Jon reports to Kenny, and Kenny reports to David. Therefore, there are 3 levels between Scott and David.
解法
与上题相同：建 child -> parent，分别走链，求 LCA 并返回两端深度和。复杂度 O(n)。
from typing import List
def count_levels(employeePairs: List[List[str]], employee1: str, employee2: str) -> int:
parent = {a: b for a, b in employeePairs}
def chain(x):
d = {x: 0}; cur = x; depth = 0
while cur in parent:
cur = parent[cur]; depth += 1
d[cur] = depth
return d
c1 = chain(employee1); c2 = chain(employee2)
best = -1
for node, dep in c1.items():
if node in c2:
total = dep + c2[node]
if best == -1 or total < best: best = total
return best if best != -1 else 0import java.util.*;
class Solution {
int countLevels(String[][] employeePairs, String e1, String e2) {
Map<String, String> parent = new HashMap<>();
for (String[] p : employeePairs) parent.put(p[0], p[1]);
return distance(e1, e2, parent);
}
private int distance(String a, String b, Map<String, String> parent) {
Map<String, Integer> c1 = chain(a, parent);
Map<String, Integer> c2 = chain(b, parent);
int best = -1;
for (var e : c1.entrySet()) {
if (c2.containsKey(e.getKey())) {
int total = e.getValue() + c2.get(e.getKey());
if (best == -1 || total < best) best = total;
}
}
return best == -1 ? 0 : best;
}
private Map<String, Integer> chain(String x, Map<String, String> parent) {
Map<String, Integer> d = new HashMap<>(); d.put(x, 0);
String cur = x; int depth = 0;
while (parent.containsKey(cur)) { cur = parent.get(cur); depth++; d.put(cur, depth); }
return d;
}
}class Solution {
public:
int countLevels(vector<vector<string>>& employeePairs, string e1, string e2) {
unordered_map<string, string> parent;
for (auto& p : employeePairs) parent[p[0]] = p[1];
auto chain = [&](const string& x) {
unordered_map<string, int> d;
d[x] = 0;
string cur = x; int depth = 0;
while (parent.count(cur)) { cur = parent[cur]; depth++; d[cur] = depth; }
return d;
};
auto c1 = chain(e1), c2 = chain(e2);
int best = -1;
for (auto& [k, dep] : c1) {
auto it = c2.find(k);
if (it != c2.end()) {
int total = dep + it->second;
if (best == -1 || total < best) best = total;
}
}
return best == -1 ? 0 : best;
}
};