做婚纱摄影网站,学网页设计软件开发,婚纱照展示网站源码,东莞网约车平台本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个长度为 n 、下标从 0 开始的整数数组 nums 表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型最初位于下标 i 的巧克力就对应第 i 个类型。
在一步操作中你可以用成本 x 执行下述行为
同时修改所有巧克力的类型将巧克力的类型 ith 修改为类型 ((i 1) mod n)th。
假设你可以执行任意次操作请返回收集所有类型巧克力所需的最小成本。
示例 1
输入nums [20,1,15], x 5
输出13
解释最开始巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着我们用成本 5 执行一次操作巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后我们用成本 5 执行一次操作巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此收集所有类型的巧克力需要的总成本是 (1 5 1 5 1) 13 。可以证明这是一种最优方案。示例 2
输入nums [1,2,3], x 4
输出6
解释我们将会按最初的成本收集全部三个类型的巧克力而不需执行任何操作。因此收集所有类型的巧克力需要的总成本是 1 2 3 6 。提示
1 nums.length 10001 nums[i] 10^91 x 10^9 解法
提示1
这道题有两个成本一个是收集每种巧克力的成本数组 nums 另一种是执行巧克力数组 rotate 的成本 x 。
不难想到由于成本数组长度最多为 1000 1000 1000 则巧克力数组长度也不会超过 1000 1000 1000 最多 rotate 1000 1000 1000 次就会回到原样。所以可以尝试所有可能——**枚举操作次数从操作 0 0 0 次到操作 n − 1 n−1 n−1 次。
提示2
考虑简单情况
如果不操作第 i i i 个巧克力必须花费 nums [ i ] \textit{nums}[i] nums[i] 收集总花费为所有 nums [ i ] \textit{nums}[i] nums[i] 之和。例如示例 2 不操作是最优的。如果只操作一次第 i i i 个巧克力可以在操作前购买也可以在操作后购买取最小值即 min ( nums [ i ] , nums [ ( i 1 ) m o d n ] ) \min(\textit{nums}[i], \textit{nums}[(i1)\bmod n]) min(nums[i],nums[(i1)modn]) 。如果操作两次购买第 i i i 个巧克力的花费为 min ( nums [ i ] , nums [ ( i 1 ) m o d n ] , nums [ ( i 2 ) m o d n ] ) \min(\textit{nums}[i], \textit{nums}[(i1)\bmod n], \textit{nums}[(i2) \bmod n]) min(nums[i],nums[(i1)modn],nums[(i2)modn]) 。例如示例 1我们可以操作两次这样每块巧克力都只需要 1 1 1 的花费总成本为 2 x 1 1 1 13 2x11113 2x11113 。
依此类推。
提示3
如果暴力枚举操作次数再枚举每个巧克力再计算购买这个巧克力的最小花费总的时间复杂度是 O ( n 3 ) \mathcal{O}(n^3) O(n3) 。
一个初步的优化是用 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的时间预处理所有子数组的最小值保存到一个二维数组中。这样做需要 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的时间和空间。
但其实不需要预处理还有更简单的做法
用一个长为 n n n 的数组 s s s 统计不同操作次数下的总成本 s [ i ] s[i] s[i] 统计操作 i i i 次下的总成本。写一个二重循环枚举子数组的左端点 i i i 和右端点 j j j 。在枚举右端点的同时维护从 nums [ i ] \textit{nums}[i] nums[i] 到 nums [ j ] \textit{nums}[j] nums[j] 的最小值 mn \textit{mn} mn 。把 mn \textit{mn} mn 加到 s [ j − i ] s[j−i] s[j−i] 中这是因为长为 j − i 1 j-i1 j−i1 的子数组恰好对应着操作 j − i j-i j−i 次时要计算的子数组或者说区间 [ i , j ] [i,j] [i,j] 的最小值对应操作 j − i j-i j−i 次取巧克力的成本。 对每个区间 [ i , i ] [i,i] [i,i] 最小值就是 n u m s [ i ] nums[i] nums[i] 也就是操作 0 0 0 次取每个巧克力的成本对每个区间 [ i , i 1 ] [i,i1] [i,i1] 最小值是 min ( n u m s [ i ] , n u m s [ i 1 ] ) \min(nums[i], nums[i1]) min(nums[i],nums[i1]) 也就是操作 1 1 1 次时取每个巧克力的成本。…… 最后输出 min ( s ) \min(s) min(s) 。
// cpp
class Solution {
public:long long minCost(vectorint nums, int x) {int n nums.size();vectorlong long s(n); // s[k] 统计操作 k 次的总成本for (int i 0; i n; i)s[i] (long long) i * x;for (int i 0; i n; i) { // 子数组左端点int mn nums[i];for (int j i; j n i; j) { // 子数组右端点把数组看做环状mn min(mn, nums[j % n]); // 维护nums[i : j]的最小值s[j - i] mn; // 累加操作 j-i 次时的成本}}return *min_element(s.begin(), s.end());}
};// java
class Solution {public long minCost(int[] nums, int x) {int n nums.length;long[] s new long[n];for (int i 0; i n; i) s[i] (long) i * x;for (int i 0; i n; i) {int mn nums[i];for (int j i; j n i; j) {mn Math.min(mn, nums[j % n]);s[j - i] mn;}}long ans Long.MAX_VALUE;for (long v : s) ans Math.min(ans, v);return ans;}
}// go
func minCost(nums []int, x int) int64 {n : len(nums)s : make([]int64, n)for i : range s {s[i] int64(i) * int64(x)}for i, mn : range nums {for j : i; j n i; j {mn min(mn, nums[j % n]);s[j - i] int64(mn);}}return slices.Min(s)
}// rust
impl Solution {pub fn min_cost(nums: Veci32, x: i32) - i64 {let n nums.len();let mut s: Veci64 (0..n).map(|i| i as i64 * x as i64).collect();for i in 0..n {let mut mn nums[i];for j in i..(n i) {mn mn.min(nums[j % n]);s[j - i] mn as i64;}}*s.iter().min().unwrap()}
}// python
class Solution:def minCost(self, nums: List[int], x: int) - int:n len(nums)s list(range(0, n * x, x))for i, mn in enumerate(nums):for j in range(i, n i):mn min(mn, nums[j % n])s[j - i] mnreturn min(s)复杂度分析
时间复杂度 O ( n 2 ) \mathcal{O}(n^2) O(n2)其中 n n n 为 nums \textit{nums} nums 的长度。空间复杂度 O ( n ) \mathcal{O}(n) O(n) 。
