首页 > 其他分享 >2024-08-31:用go语言,给定一个数组apple,包含n个元素,每个元素表示一个包裹中的苹果数量; 另一个数组capacity包含m个元素,表示m个不同箱子的容量。 有n个包裹,每个包裹内装有

2024-08-31:用go语言,给定一个数组apple,包含n个元素,每个元素表示一个包裹中的苹果数量; 另一个数组capacity包含m个元素,表示m个不同箱子的容量。 有n个包裹,每个包裹内装有

时间:2024-08-31 19:23:33浏览次数:15  
标签:箱子 capacity apple 容量 复杂度 元素 包裹 苹果 数组

2024-08-31:用go语言,给定一个数组apple,包含n个元素,每个元素表示一个包裹中的苹果数量;

另一个数组capacity包含m个元素,表示m个不同箱子的容量。

有n个包裹,每个包裹内装有指定数量的苹果,以及m个箱子,每个箱子的容量不同。

任务是将这n个包裹中的所有苹果重新分配到箱子中,最小化所需的箱子数量。

需要注意的是,可以将同一个包裹中的苹果分装到不同的箱子中。

需要计算并返回实现这一目标所需的最小箱子数量。

输入:apple = [1,3,2], capacity = [4,3,1,5,2]。

输出:2。

解释:使用容量为 4 和 5 的箱子。

总容量大于或等于苹果的总数,所以可以完成重新分装。

答案2024-08-31:

chatgpt

题目来自leetcode3074。

大体步骤如下:

1.首先,计算所有苹果的总数,用变量 s 表示。

2.将箱子的容量按照降序排列,通过调用 slices 包里的 SortFunc 函数,将 capacity 数组按照从大到小排序。

3.遍历排序后的容量数组,从大到小依次尝试将苹果放入箱子中。

4.在每个循环中,尝试将当前箱子的容量 c 与苹果总数 s 比较:

  • 如果 s 小于等于 0,表示所有苹果都已经装箱了,返回当前箱子的索引 + 1,即已经使用的箱子数目。
  • 如果 s 大于 0,继续尝试将苹果放入下一个箱子,更新 s 为剩余苹果的数量。

5.如果循环结束时仍未返回箱子数量,说明无法将所有苹果重新分装到箱子中,返回 -1。

总的时间复杂度:

  • 计算苹果总数的时间复杂度为 O(n),n 为苹果数量。
  • 对箱子容量进行排序的时间复杂度为 O(m log m),m 为箱子数量。
  • 遍历箱子容量的时间复杂度为 O(m),m 为箱子数量。

综合起来,总的时间复杂度大致在 O((n + m) log m) 的数量级。

总的额外空间复杂度:

  • 只使用了常数级别的额外空间,因此额外空间复杂度为 O(1)。

Go完整代码如下:

package main

import (
	"fmt"
	"slices"
)

func minimumBoxes(apple, capacity []int) int {
	s := 0
	for _, x := range apple {
		s += x
	}
	slices.SortFunc(capacity, func(a, b int) int { return b - a })
	for i, c := range capacity {
		s -= c
		if s <= 0 { // 所有苹果都装入了箱子
			return i + 1 // 0 到 i 有 i+1 个箱子
		}
	}
	return -1
}

func main() {

	apple := []int{1, 3, 2}
	capacity := []int{4, 3, 1, 5, 2}
	fmt.Println(minimumBoxes(apple, capacity))
}

2024-08-31:用go语言,给定一个数组apple,包含n个元素,每个元素表示一个包裹中的苹果数量; 另一个数组capacity包含m个元素,表示m个不同箱子的容量。 有n个包裹,每个包裹内装有_ci

Rust完整代码如下:

fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
    let mut s: i32 = apple.iter().sum();
    capacity.sort_by(|a, b| b.cmp(a));
    for (i, &c) in capacity.iter().enumerate() {
        s -= c;
        if s <= 0 {
            return (i + 1) as i32;
        }
    }
    -1
}

fn main() {
    let apple = vec![1, 3, 2];
    let capacity = vec![4, 3, 1, 5, 2];
    println!("{}", minimum_boxes(apple, capacity));
}

2024-08-31:用go语言,给定一个数组apple,包含n个元素,每个元素表示一个包裹中的苹果数量; 另一个数组capacity包含m个元素,表示m个不同箱子的容量。 有n个包裹,每个包裹内装有_ci_02

标签:箱子,capacity,apple,容量,复杂度,元素,包裹,苹果,数组
From: https://blog.51cto.com/moonfdd/11883605

相关文章

  • 主元素问题(C语言)
    主元素问题(C语言)题目参考代码#include<stdio.h>intmain(){//主元素问题intn,s[400002],num=1,max=0,maxNum=0;scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&s[i]);for(inti=0;......
  • HTML元素的head、title
    <head>Html文档的头部,包含机器可读的文档相关信息,如文档的标题、脚本和样式表。<head> 主要保存供机器处理的信息,而非人类可读信息。对于人类可见的信息,如顶级标题和列出的作者,请参见 <header> 元素。示例1:<!doctypehtml><htmllang="zh-CN"> <head>   <metacharset="UT......
  • shell(第四章数组和函数)
    变量里面有索引比如:name=dufeng调用echo${name:0:1}输出的是du数字形索引是数组123123文字形索引是关联数组qwupdufeng定义数组数组名=(数组数组数组)数组名=(`cat/etc/passwd`)#反`优先执行数组名=(`ls/home*`)#只要数组可以输出结果数组名=(数组"......
  • leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)
    前言:链表部分之前刷过一些题,掌握的还可以,希望可以顺利把这部分题刷完。203.移除链表元素思路:自己创建一个头节点,使新的头节点指向旧的头节点。错误尝试:一开始考虑的比较复杂,设置了指针pre,能够想到直接比较cur.next.val和val的值会使代码更加简洁,但也要注意想清楚如果删除......
  • 后缀数组学习笔记
    后缀数组挺好玩的,于是来写后缀数组学习笔记了。什么是后缀数组?后缀数组主要关系到2个数组:\(sa\)和\(rk\)。\(sa[i]\)表示将所有后缀按照字典序从小到大排序,排名第\(i\)的后缀的开头为第\(sa[i]\)个字符。\(rk[i]\)表示将所有后缀按照字典序从小到大排序,后缀开......
  • 【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)
    【每日一题】LeetCode1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)题目描述给定一个整数数组arr和两个整数k和threshold,要求找出数组中长度为k且平均值大于等于threshold的子数组的数量。输入格式arr:一个整数数组。k:子数组的长度。thres......
  • PHP数组
    数组能够在单个变量中存储多个值数组可以在单个变量中存储多个值,并且您可以根据键访问其中的值。创建数组在PHP中,array()函数用于创建数组:在PHP中,有三种类型的数组:数值数组-带有数字ID键的数组关联数组-带有指定的键的数组,每个键关联一个值多维数组-包含一个......
  • js 数组的常用方法:在头部插入,删除,尾部插入,删除
    arr.push(value),在数组的末尾添加一个或多个元素,并返回数组的新长度。arr.pop()删除索引值最大的元素,即删除数组末尾的元素,并返回被删除的元素。unshift(value)在数组的头部添加一个或多个元素,并返回数组的新长度shift()删除索引为0的元素,并返回删除的元素splice()方法会修......
  • 06.类-数组(array)和string
    6.类-数组(array)和string6.1数组数组是一组连续的内存位置,它们都具有相同的类型。为了指代数组中的特定位置或元素,我们指定数组的名称和特定元素在数组中的位置编号。数组名称遵循与其他变量名相同的约定。下标必须是整数或整数表达式,带下标的数组名是一个左值,它可以在赋值......
  • 用c++以数组的形式实现栈的数据结构
    #include<iostream>usingnamespacestd;//设置数组的最大值#define MaxSize100intA[MaxSize];//栈顶inttop=-1;//入栈voidpush(intx){  //处理溢出的情况  if(top==MaxSize-1){    cout<<"stackoverflow"<<endl;    return; ......