A software development company is creating several shared computing systems throughout an office. Each network requires:
- All computers must be adjacent to one another.
- Each network has a minimum number of computers (
minComps). - Total processing speed of computers in a network (sum of
speed) must be at leastspeedThreshold. - A computer can only belong to one network.
Given speed[n] (order represents adjacency on a line) and minComps, speedThreshold, return the maximum number of networks.
解法
从左到右贪心：扩展当前段直到长度和总和约束都满足，然后封段重开。复杂度 O(N)。
def solve(speed, min_comps, threshold):
nets = length = total = 0
for s in speed:
length += 1; total += s
if length >= min_comps and total >= threshold:
nets += 1; length = total = 0
return netsclass Solution {
public int solve(int[] speed, int minComps, int threshold) {
int nets = 0, len = 0;
long sum = 0;
for (int s : speed) {
len++; sum += s;
if (len >= minComps && sum >= threshold) { nets++; len = 0; sum = 0; }
}
return nets;
}
}int solve(vector<int>& speed, int minComps, int threshold) {
int nets = 0, len = 0;
long long sum = 0;
for (int s : speed) {
++len; sum += s;
if (len >= minComps && sum >= threshold) { ++nets; len = 0; sum = 0; }
}
return nets;
}Given an integer array a, partition it into two disjoint non-empty contiguous subarrays. Return the maximum sum of (max subarray sum of part 1) + (max subarray sum of part 2).
Example: a = [-1, 4, -2, 5, -3, 6] → split after index 1 gives [(-1, 4)] with best 4 and [-2, 5, -3, 6] with best 8; answer 4 + 8 = 12. Try every split point and take the max.
解法
两遍 Kadane：L[i] 为 a[0..i] 内最大子数组和，R[i] 为 a[i..n-1] 内最大子数组和。答案 = max(L[i] + R[i+1])。复杂度 O(N)。
def solve(a):
n = len(a)
L = [0] * n; R = [0] * n
cur = best = a[0]; L[0] = best
for i in range(1, n):
cur = max(a[i], cur + a[i]); best = max(best, cur); L[i] = best
cur = best = a[-1]; R[-1] = best
for i in range(n - 2, -1, -1):
cur = max(a[i], cur + a[i]); best = max(best, cur); R[i] = best
return max(L[i] + R[i + 1] for i in range(n - 1))class Solution {
public long solve(int[] a) {
int n = a.length;
long[] L = new long[n], R = new long[n];
long cur = 0, best = Long.MIN_VALUE;
for (int i = 0; i < n; i++) {
cur = Math.max(a[i], cur + a[i]);
best = Math.max(best, cur);
L[i] = best;
}
cur = 0; best = Long.MIN_VALUE;
for (int i = n - 1; i >= 0; i--) {
cur = Math.max(a[i], cur + a[i]);
best = Math.max(best, cur);
R[i] = best;
}
long ans = Long.MIN_VALUE;
for (int i = 0; i + 1 < n; i++) ans = Math.max(ans, L[i] + R[i + 1]);
return ans;
}
}long long solve(vector<int>& a) {
int n = a.size();
vector<long long> L(n, 0), R(n, 0);
long long cur = 0, best = LLONG_MIN;
for (int i = 0; i < n; ++i) {
cur = max((long long)a[i], cur + a[i]);
best = max(best, cur);
L[i] = best;
}
cur = 0; best = LLONG_MIN;
for (int i = n - 1; i >= 0; --i) {
cur = max((long long)a[i], cur + a[i]);
best = max(best, cur);
R[i] = best;
}
long long ans = LLONG_MIN;
for (int i = 0; i + 1 < n; ++i) ans = max(ans, L[i] + R[i + 1]);
return ans;
}There are n planned updates. Update i can be released on plannedDate[i] or its earlier alternateDate[i]. Updates must be released in the order of their planned release date, but multiple updates can release the same day. Return the minimum total days to release all updates.
解法
按 plannedDate 排序，遍历每次更新：备用日期 ≥ 当前日则用备用日期，否则回退到 plannedDate。复杂度 O(N log N)。
def solve(planned, alternate):
day = 0
for p, a in sorted(zip(planned, alternate)):
day = max(day, a if a >= day else p)
return dayclass Solution {
public int solve(int[] planned, int[] alternate) {
int n = planned.length;
int[][] v = new int[n][2];
for (int i = 0; i < n; i++) { v[i][0] = planned[i]; v[i][1] = alternate[i]; }
Arrays.sort(v, (x, y) -> x[0] - y[0]);
int day = 0;
for (int[] x : v) day = Math.max(day, x[1] >= day ? x[1] : x[0]);
return day;
}
}int solve(vector<int>& planned, vector<int>& alternate) {
int n = planned.size();
vector<pair<int,int>> v;
for (int i = 0; i < n; ++i) v.push_back({planned[i], alternate[i]});
sort(v.begin(), v.end());
int day = 0;
for (auto& [p, a] : v) day = max(day, a >= day ? a : p);
return day;
}