一道有趣的GG面试题

给定n种面值a1, a2, ..., an，和一个整数m。
让你决定每一枚面值的硬币的使用数量，使得总硬币数最

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

m=9
则面值1的使用4枚，面值5的使用1枚

kunge12345 发表于 2017-1-29 05:33
没明白你的问题。。。这两题本质上不是一样的吗。。。
上代码
public static Map minNumCoin(Set coins ...

我觉得你的算法应该不太对，比如我有1，2，21，25美分的硬币，target number是63。正确答案应该是21+21+21，3个硬币。你的算法应该是会从1开始找起。leetcode 330的贪心算法保证了［1，n］的所有面值，这个题只需要保证n最优就可以了。

李口德330 patching array一样的思路，greedy

补充内容 (2017-2-2 07:33):
”并且对于1...m中每一种面值，都可以用你选出的硬币拼出。“
难道我跟诸位的打开方式不一样？


补充内容 (2017-2-5 22:04):
请先看清题目！！！！！
请先看清题目！！！！！
请先看清题目！！！！！
请先看清题目！！！！！
还有人说greedy不对要用DP的，我不会再回复了

xixiaoxi 发表于 2017-2-2 05:56
我觉得你的算法应该不太对，比如我有1，2，21，25美分的硬币，target number是63。正确答案应该是21+21+2 ...

你没看到lz写的大大的
“并且对于1...m中每一种面值，都可以用你选出的硬币拼出。”
？？？

背包问题的变种吧，dp可解

人气这么少？为楼主挽尊

这题还可以加点难度，要求返回选择结果，in descending order，如果有多解，选择lexicographic order最大的。比如硬币2,3,4，要凑出6，返回4,2而不是3,3

kunge12345 发表于 2017-1-28 21:47
李口德330 patching array一样的思路，greedy

LC330每个index只能出现一次，这个可以无限重复，还是不一样的吧？ 还是有什么其他的思路？

leetcode 换个方式问罢了

kunge12345 发表于 2017-1-28 21:47
李口德330 patching array一样的思路，greedy

同意 字数字数字数

shufezq 发表于 2017-1-29 03:54
LC330每个index只能出现一次，这个可以无限重复，还是不一样的吧？ 还是有什么其他的思路？

没明白你的问题。。。这两题本质上不是一样的吗。。。
上代码
public static Map<Integer, Integer> minNumCoin(Set<Integer> coins, int m){
    int miss = 1;
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int coin : coins){
        map.putIfAbsent(coin, 0);
    }

    int next = 0;
    while (miss <= m){
        for(int coin : coins){
            if(coin > next && coin <= miss){
                next = coin;
            }
        }
        if (next == 0){
            return null; // not possible
        }
        miss += next;
        map.put(next, map.get(next) + 1);
    }

    return map;
}