A customer has posted several web development projects on a freelancing platform, and various web developers have put in bids for these projects. Given the bid amounts and their corresponding projects, what is the minimum amount the customer can pay to have all the projects completed?
Note: If any project has no bids, return -1.
Example
numProjects = 3
projects = [2, 0, 1, 2]
bid = [8, 7, 6, 9]
projects[i] is aligned with bid[i]
- The first web developer bid 8 currency units for project 2.
- The second web developer bid 7 currency units for project 0.
- The third web developer bid 6 currency units for project 1.
- The fourth web developer bid 9 currency units for project 2.
There is only one choice for projects 0 and 1, with cost 7 and 6 respectively.
For project 2, two bids are available: 8 and 9. Take 8.
Total = 7 + 6 + 8 = 21.解法
按项目 id 分组取最小报价；若有项目无报价返回 -1。一次遍历，复杂度 O(N + numProjects)。
def minCustomerCost(numProjects, projects, bids):
min_bid = [float('inf')] * numProjects
for p, b in zip(projects, bids):
if b < min_bid[p]:
min_bid[p] = b
total = 0
for x in min_bid:
if x == float('inf'):
return -1
total += x
return totalclass Solution {
static long minCustomerCost(int numProjects, int[] projects, int[] bids) {
long[] minBid = new long[numProjects];
Arrays.fill(minBid, Long.MAX_VALUE);
for (int i = 0; i < projects.length; i++)
if (bids[i] < minBid[projects[i]]) minBid[projects[i]] = bids[i];
long total = 0;
for (long x : minBid) {
if (x == Long.MAX_VALUE) return -1;
total += x;
}
return total;
}
}long long minCustomerCost(int numProjects, vector<int>& projects, vector<int>& bids) {
vector<long long> minBid(numProjects, LLONG_MAX);
for (size_t i = 0; i < projects.size(); i++)
if (bids[i] < minBid[projects[i]]) minBid[projects[i]] = bids[i];
long long total = 0;
for (long long x : minBid) {
if (x == LLONG_MAX) return -1;
total += x;
}
return total;
}A group of friends are playing a video game together. During the game, each player earns a number of points. At the end of a round, players who achieve at least a certain rank K (sorted by descending score) are allowed to "level up" their characters to gain increased abilities. Given the scores of the players at the end of a round, how many players will be able to level up?
Note: Players with equal scores will have equal ranks. For example, if there are 4 players, and three of them tied for first place, their ranks would be 1, 1, 1, and 4.
Note: Players with a score of 0 cannot level up regardless of rank.
解法
分数降序排序，分配 dense rank，统计 rank ≤ k 且 score > 0 的数量；rank > k 时提前终止。复杂度 O(n log n)。
def numPlayers(k, scores):
s = sorted(scores, reverse=True)
cnt = 0
rank = 0
prev = None
for i, score in enumerate(s):
if score != prev:
rank = i + 1
prev = score
if rank <= k and score > 0:
cnt += 1
elif rank > k:
break
return cntclass Solution {
static int numPlayers(int k, int[] scores) {
Integer[] s = new Integer[scores.length];
for (int i = 0; i < scores.length; i++) s[i] = scores[i];
Arrays.sort(s, Collections.reverseOrder());
int cnt = 0, rank = 0;
Integer prev = null;
for (int i = 0; i < s.length; i++) {
if (prev == null || !s[i].equals(prev)) { rank = i + 1; prev = s[i]; }
if (rank <= k && s[i] > 0) cnt++; else if (rank > k) break;
}
return cnt;
}
}int numPlayers(int k, vector<int>& scores) {
vector<int> s = scores;
sort(s.begin(), s.end(), greater<int>());
int cnt = 0, rank = 0, prev = INT_MIN;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] != prev) { rank = i + 1; prev = s[i]; }
if (rank <= k && s[i] > 0) cnt++; else if (rank > k) break;
}
return cnt;
}Implement the function get_dict_value that takes two arguments: a dictionary called dict and a string called path. The path string represents the nested keys of the dictionary, separated by dots. The function should return the value at the specified path or None (Python null value, not a string) if the path does not exist.
Example
obj = {
"car": {
"wheels": 2,
"gears": 5
}
}
get_dict_value(obj, "car.gears") # → 5
get_dict_value(obj, "car.color") # → None解法
按 . 切分路径，逐层在 dict 中下钻；若中途缺失或类型不是 dict 则返回 None。复杂度 O(depth)。
def get_dict_value(d: dict, path: str):
cur = d
for key in path.split('.'):
if not isinstance(cur, dict) or key not in cur:
return None
cur = cur[key]
return curclass Solution {
@SuppressWarnings("unchecked")
static Object getDictValue(Map<String, Object> dict, String path) {
Object cur = dict;
for (String key : path.split("\\.")) {
if (!(cur instanceof Map)) return null;
Map<String, Object> m = (Map<String, Object>) cur;
if (!m.containsKey(key)) return null;
cur = m.get(key);
}
return cur;
}
}#include <any>
optional<any> getDictValue(const map<string, any>& d, const string& path) {
any cur = d;
size_t l = 0;
while (l <= path.size()) {
size_t r = path.find('.', l);
string key = path.substr(l, r == string::npos ? string::npos : r - l);
auto* m = any_cast<map<string, any>>(&cur);
if (!m) return nullopt;
auto it = m->find(key);
if (it == m->end()) return nullopt;
cur = it->second;
if (r == string::npos) break;
l = r + 1;
}
return cur;
}