class Solution {
public:
int minimumCost(vector<int>& nums) {
}
};
100181. 将数组分成最小总代价的子数组 I
给你一个长度为 n 的整数数组 nums 。
一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。
你需要将 nums 分成 3 个 连续且没有交集 的子数组。
请你返回这些子数组的 最小 代价 总和 。
示例 1：
输入：nums = [1,2,3,12] 输出：6 解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。 其他得到 3 个子数组的方案是： - [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。 - [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。
示例 2：
输入：nums = [5,4,3] 输出：12 解释：最佳分割成 3 个子数组的方案是：[5] ，[4] 和 [3] ，总代价为 5 + 4 + 3 = 12 。 12 是所有分割方案里的最小总代价。
示例 3：
输入：nums = [10,3,1,1] 输出：12 解释：最佳分割成 3 个子数组的方案是：[10,3] ，[1] 和 [1] ，总代价为 10 + 1 + 1 = 12 。 12 是所有分割方案里的最小总代价。
提示：
3 <= n <= 501 <= nums[i] <= 50原站题解
golang 解法, 执行用时: 6 ms, 内存消耗: 2.7 MB, 提交时间: 2024-01-21 20:29:11
func minimumCost(nums []int) int {
fi, se := math.MaxInt, math.MaxInt
for _, x := range nums[1:] {
if x < fi {
se = fi
fi = x
} else if x < se {
se = x
}
}
return nums[0] + fi + se
}
func minimumCost2(nums []int) int {
slices.Sort(nums[1:])
return nums[0] + nums[1] + nums[2]
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 28.8 MB, 提交时间: 2024-01-21 20:28:46
class Solution {
public:
int minimumCost(vector<int> &nums) {
sort(nums.begin() + 1, nums.end());
return accumulate(nums.begin(), nums.begin() + 3, 0);
}
int minimumCost2(vector<int> &nums) {
int fi = INT_MAX, se = INT_MAX;
for (int i = 1; i < nums.size(); i++) {
int x = nums[i];
if (x < fi) {
se = fi;
fi = x;
} else if (x < se) {
se = x;
}
}
return nums[0] + fi + se;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 43.1 MB, 提交时间: 2024-01-21 20:28:11
class Solution {
public int minimumCost(int[] nums) {
int fi = Integer.MAX_VALUE, se = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < fi) {
se = fi;
fi = x;
} else if (x < se) {
se = x;
}
}
return nums[0] + fi + se;
}
public int minimumCost2(int[] nums) {
Arrays.sort(nums, 1, nums.length);
return nums[0] + nums[1] + nums[2];
}
}
python3 解法, 执行用时: 37 ms, 内存消耗: 16.3 MB, 提交时间: 2024-01-21 20:27:36
class Solution:
# 第一个必选，剩下的排序，取最小的两个
def minimumCost(self, nums: List[int]) -> int:
return nums[0] + sum(sorted(nums[1:])[:2])
def minimumCost2(self, nums: List[int]) -> int:
return nums[0] + sum(nsmallest(2, nums[1:]))