Groupon面经

haoxuango 发表于 2015-12-29 13:03
楼主， 海投多久有反应的？

记不太清了。。。大约等了3周？

mumu007 发表于 2015-11-10 06:04
这个题如果用DP的话，复杂度是O（total）吗？greedy是不是复杂度是O(number of available changes)， 是不 ...

请问一下，greedy的复杂度为什么是O(4)呀？还有这题要求的是最少零钱的总数量还是要求出怎么组合呀？

vivyao 发表于 2015-12-31 08:36
请问一下，greedy的复杂度为什么是O(4)呀？还有这题要求的是最少零钱的总数量还是要求出怎么组合呀？

我之前想的是先换大面额的，比如用106换｛25，10，5，1｝，就先换4张25，再换1张5，最后换1张1.但是如果提供的零钱面值不是这样有规律的话，这样换可能换不开，比如用106换｛20，5，3，2｝，先换5张20，再换一张5块，这样导致换不开（虽然是可以用5张20，两张3换开）。还是用DP吧，现在leetcode上已经有这道题了322. Coin Change
（https://leetcode.com/problems/coin-change/）

贴下我的DP答案， C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int numCoin = coins.size();
        if(amount == 0) return 0;
        vector<int> count(amount+1, -1);
        for(int i = 0; i < numCoin; i++) {
            if(coins[i] <= amount) count[coins[i]] = 1;
        }
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < numCoin; j++) {
                if(i-coins[j] < 0 || count[i - coins[j]] < 0) continue;
                else { // i - coints[j] >= 0 && count[i - coins[j]] > 0
                    if(count[i] < 0) count[i] = count[i - coins[j]] + 1;
                    else count[i] = min(count[i], count[i - coins[j]] + 1);
                }
            }
        }
        return count[amount];
    }
};

mumu007 发表于 2015-12-31 12:36
我之前想的是先换大面额的，比如用106换｛25，10，5，1｝，就先换4张25，再换1张5，最后换1张1.但是如果 ...

谢谢！！原来leetcode已经有啦，还没做到哇