远征队即将开启未知的冒险之旅，不过在此之前，将对补给车队进行最后的检查。supplies[i] 表示编号为 i 的补给马车装载的物资数量。
考虑到车队过长容易被野兽偷袭，他们决定将车队的长度变为原来的一半（向下取整），计划为： - 找出车队中 物资之和最小 两辆 相邻
马车，将它们车辆的物资整合为一辆。若存在多组物资之和相同的马车，则取编号最小的两辆马车进行整合； - 重复上述操作直到车队长度符合要求。
请返回车队长度符合要求后，物资的分布情况。 示例 1： >输入：supplies = [7,3,6,1,8] > >输出：[10,15] >
解释： > 第 1 次合并，符合条件的两辆马车为 6,1，合并后的车队为 [7,3,7,8]； > 第 2 次合并，符合条件的两辆马车为 (7,3) 和
(3,7)，取编号最小的 (7,3)，合并后的车队为 [10,7,8]； > 第 3 次合并，符合条件的两辆马车为 7,8，合并后的车队为 [10,15]；
返回 [10,15] 示例 2： >输入：supplies = [1,3,1,5] > >输出：[5,5] 解释： - 2 <= supplies.length <= 1000 - 1 <= supplies[i] <= 1000
本题视频讲解
见【力扣杯2023春·个人赛】 。
思路
为方便描述，下文简称 supplies 为 a。
不断循环，每次找到相邻和最小的 a[i-1] 和 a[i]，然后把 a[i-1] 增加 a[i]，并去掉 a[i]。
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def supplyWagon(self, a: List[int]) -> List[int]:
m = len(a) // 2
while len(a) > m:
idx = 1
for i in range(1, len(a)):
if a[i - 1] + a[i] < a[idx - 1] + a[idx]:
idx = i
a[idx - 1] += a[idx]
a.pop(idx)
return a
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] supplyWagon(int[] a) {
int m = a.length / 2;
for (int n = a.length; n > m; --n) {
int j = 1;
for (int i = 1; i < n; ++i)
if (a[i] + a[i - 1] < a[j] + a[j - 1])
j = i;
a[j - 1] += a[j];
System.arraycopy(a, j + 1, a, j, n - 1 - j);
}
return Arrays.copyOf(a, m);
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> supplyWagon(vector<int> &a) {
int m = a.size() / 2;
while (a.size() > m) {
int j = 1;
for (int i = 1; i < a.size(); ++i)
if (a[i] + a[i - 1] < a[j] + a[j - 1])
j = i;
a[j - 1] += a[j];
a.erase(a.begin() + j);
}
return a;
}
};
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func supplyWagon(a []int) []int {
m := len(a) / 2
for len(a) > m {
j := 1
for i := 1; i < len(a); i++ {
if a[i]+a[i-1] < a[j]+a[j-1] {
j = i
}
}
a[j-1] += a[j]
a = append(a[:j], a[j+1:]...)
}
return a
}
|
复杂度分析
- 时间复杂度：\mathcal{O}(n^2)，其中 n 为 a 的长度。
- 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。
