硬币包含问题(最少找钱问题)
硬币包含问题(最少找钱问题)
golang_yh 发表于2年前
硬币包含问题(最少找钱问题)
  • 发表于 2年前
  • 阅读 110
  • 收藏 1
  • 点赞 1
  • 评论 0

腾讯云 学生专属云服务套餐 10元起购>>>   

摘要: golang刷刷小算法 leetcode Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

package main

import (
	"fmt"
	"sort"
)

func coin_change(arr []int, total int) int {
	sort.Ints(arr)
	tmp := total
	length := len(arr)
	var amount int = 0

	for i := length - 1; i >= 0; i-- {
		if tmp%arr[i] == 0 {
			amount += tmp / arr[i]
			return amount
		} else if tmp >= arr[0] {
			amount += tmp / arr[i]
			tmp = tmp % arr[i]
		} else {
			amount = 0
			tmp = total
		}
	}

	return -1
}

func main() {
	arr := []int{1, 2, 5}
	amount :=11
	fmt.Printf("need coin num:%d\n", coin_change(arr, amount))
}

//输出结果-------------------------------------------------
//arr := []int{1, 2, 5} amount:=11 输出:need coin num:3
//arr := []int{1, 2}  amount:=11 输出:need coin num:6
//arr := []int{2, 5}  amount:=11 输出:need coin num:-1
//arr := []int{2} amount:=3 输出:need coin num:-1


共有 人打赏支持
粉丝 31
博文 86
码字总数 24924
×
golang_yh
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: