2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币

2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币,

每一次操作中,你可以从任意一个栈的 顶部 取出 1 个硬币,从栈中移除它,并放入你的钱包里。

给你一个列表 piles ,其中 piles[i] 是一个整数数组,

分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k。

请你返回在 恰好 进行 k 次操作的前提下,你钱包里硬币面值之和 最大为多少?

输入:piles = [[1,100,3],[7,8,9]], k = 2。

输出:101。

答案2024-03-23:

来自左程云

灵捷3.5

大体过程如下:

1.初始化变量:定义一个 dp 数组用于记录计算过程中的最大值,长度为 k+1,初始值全为 0。

2.循环遍历每个栈 stackpiles 中:

2.1.对于每个栈 stack,从最大次数 k 开始递减到 1:

2.1.1.定义变量 sum 用于记录当前栈取出的硬币总和。

2.1.2.遍历从 1 到 min(栈的长度, 次数) 的取数次数 i

2.1.2.1.计算当前次数下取的硬币总和并更新到 sum 中。

2.1.2.2.更新 dp[次数] 为当前 dp[次数] 与取出当前硬币后的最大值(sum + dp[次数-i])的较大者。

3.返回 dp[k],即完成 k 次操作后的最大硬币面值之和。

4.时间复杂度:

  • 遍历每个栈需要 O(n) 的时间,n 为栈的数量。

  • 每个栈内部的计算复杂度为 O(k * m),其中 m 为栈内硬币的数量。

  • 因此,总的时间复杂度为 O(nkm)。

5.空间复杂度:

  • 需要额外的 dp 数组来存储计算所需的值,长度为 k+1,即 O(k) 的额外空间。

  • 因此,总的额外空间复杂度为 O(k)。

Go语言代码如下:

package main

import (
    "fmt"
    "math"
)

func maxValueOfCoins(piles [][]int, k int) int {
    dp := make([]int, k+1)

    for _, stack := range piles {
        for w := k; w > 0; w-- {
            var sum int
            for i := 1; i <= int(math.Min(float64(len(stack)), float64(w))); i++ {
                sum += stack[i-1]
                dp[w] = int(math.Max(float64(dp[w]), float64(sum+dp[w-i])))
            }
        }
    }

    return dp[k]
}

func main() {
    piles := [][]int{{1, 100, 3}, {7, 8, 9}}
    k := 2

    result := maxValueOfCoins(piles, k)
    fmt.Println(result)
}

在这里插入图片描述

Python语言代码如下:

# -*-coding:utf-8-*-

def max_value_of_coins(piles, k):
    dp = [0] * (k+1)

    for stack in piles:
        for w in range(k, 0, -1):
            sum_val = 0
            for i in range(1, min(len(stack), w)+1):
                sum_val += stack[i-1]
                dp[w] = max(dp[w], sum_val + dp[w - i])

    return dp[k]

def main():
    piles = [[1, 100, 3], [7, 8, 9]]
    k = 2
    result = max_value_of_coins(piles, k)
    print(result)

if __name__ == "__main__":
    main()

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
470
粉丝
21
喜欢
37
收藏
22
排名:457
访问:1.9 万
私信
所有博文
社区赞助商