LeetCode 2735. 收集巧克力【枚举】2043

2023-12-29 08:36

本文主要是介绍LeetCode 2735. 收集巧克力【枚举】2043,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文属于「征服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 <= 1000
  • 1 <= nums[i] <= 10^9
  • 1 <= x <= 10^9

解法

提示1

这道题有两个成本,一个是收集每种巧克力的成本数组 nums ;另一种是执行巧克力数组 rotate 的成本 x

不难想到,由于成本数组长度最多为 1000 1000 1000 ,则巧克力数组长度也不会超过 1000 1000 1000 ,最多 rotate 1000 1000 1000 次,就会回到原样。所以可以尝试所有可能——**枚举操作次数,从操作 0 0 0 次到操作 n − 1 n−1 n1 次。

提示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}[(i+1)\bmod n]) min(nums[i],nums[(i+1)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}[(i+1)\bmod n], \textit{nums}[(i+2) \bmod n]) min(nums[i],nums[(i+1)modn],nums[(i+2)modn]) 。例如示例 1,我们可以操作两次,这样每块巧克力都只需要 1 1 1 的花费,总成本为 2 x + 1 + 1 + 1 = 13 2x+1+1+1=13 2x+1+1+1=13

依此类推。

提示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) 的时间和空间。

但其实不需要预处理,还有更简单的做法:

  1. 用一个长为 n n n 的数组 s s s 统计不同操作次数下的总成本, s [ i ] s[i] s[i] 统计操作 i i i 次下的总成本
  2. 写一个二重循环,枚举子数组的左端点 i i i 和右端点 j j j
  3. 在枚举右端点的同时,维护从 nums [ i ] \textit{nums}[i] nums[i] nums [ j ] \textit{nums}[j] nums[j] 的最小值 mn \textit{mn} mn
  4. mn \textit{mn} mn 加到 s [ j − i ] s[j−i] s[ji] 中,这是因为长为 j − i + 1 j-i+1 ji+1 的子数组恰好对应着操作 j − i j-i ji 次时要计算的子数组,或者说区间 [ i , j ] [i,j] [i,j] 的最小值对应操作 j − i j-i ji 次取巧克力的成本。
    1. 对每个区间 [ i , i ] [i,i] [i,i] ,最小值就是 n u m s [ i ] nums[i] nums[i] ,也就是操作 0 0 0 次取每个巧克力的成本;
    2. 对每个区间 [ i , i + 1 ] [i,i+1] [i,i+1] ,最小值是 min ⁡ ( n u m s [ i ] , n u m s [ i + 1 ] ) \min(nums[i], nums[i+1]) min(nums[i],nums[i+1]) ,也就是操作 1 1 1 次时取每个巧克力的成本。
    3. ……
  5. 最后输出 min ⁡ ( s ) \min(s) min(s)
// cpp
class Solution {
public:long long minCost(vector<int>& nums, int x) {int n = nums.size();vector<long 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: Vec<i32>, x: i32) -> i64 {let n = nums.len();let mut s: Vec<i64> = (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)

这篇关于LeetCode 2735. 收集巧克力【枚举】2043的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/548949

相关文章

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举

Rust中的Option枚举快速入门教程

《Rust中的Option枚举快速入门教程》Rust中的Option枚举用于表示可能不存在的值,提供了多种方法来处理这些值,避免了空指针异常,文章介绍了Option的定义、常见方法、使用场景以及注意事... 目录引言Option介绍Option的常见方法Option使用场景场景一:函数返回可能不存在的值场景

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件,方便以后开发的时候查找!!! 函数工具: Lodash 页面固定: stickUp、jQuery.Pin 轮播: unslider、swiper 开关: switch 复选框: icheck 气泡: grumble 隐藏元素: Headroom

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists