Pure C recursive solution, 4ms, beats 100%.


  • 0
    F
    void qs(int *nums, int len) {
        if (len < 2) return;
        int key = nums[len - 1];
        int i;
        for (i = 0; i < len - 1 && nums[i] > key; i++);
        if (i == len - 1) {
            qs(nums, len - 1);
            return;
        }
        int j;
        for (j = i + 1; j < len - 1; j++) {
            if (nums[j] > key) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i++] = tmp;
            }
        }
        nums[len - 1] = nums[i];
        nums[i] = key;
        qs(nums, i);
        qs(nums + i + 1, len - i - 1);
    }
    
    void helper(int *coins, int len, int amount, int cur, int *min) {
        if (len < 1) return;
        int n = amount / coins[0]; //coins[0] is the biggest coin.
        //at first, eat as much as possible.
        amount -= n * coins[0];
        cur += n; //current coins number.
        if (!amount) { //one possible solution.
            *min = *min < cur ? *min : cur;
            return;
        }
        //coins[0] is the biggest coin and we already eat as much as we can, 
        //so if the number of current coins are still bigger than *min, no more operations needed.
        if (cur >= *min) return;
        int i;
        for (i = 0; i <= n; i++) {
            helper(coins + 1, len - 1, amount, cur - i, min);
            amount += coins[0];
        }
    }
    
    int coinChange(int* coins, int coinsSize, int amount) {
        // desc sort.
        qs(coins, coinsSize);
        int min = INT_MAX;
        helper(coins, coinsSize, amount, 0, &min);
        return min == INT_MAX ? -1 : min;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.