我要招人

去企业版

首页 > 试题广场 >

找零

[编程题]找零

热度指数：1722 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N(0<N≤1024)的商品，请问最少他会收到多少硬币

示例1

输入

输出

说明

12个64元硬币，3个16元硬币，2个4元硬币

算法知识视频讲解

一包薯条呸呸

package main

/**
 * 
 * @param N int整型 
 * @return int整型
*/
func GetCoinCount( N int ) int {
    // write code here
    dp := make([]int, 1025)
    coins := []int{1, 4, 16, 64}
    for i := 1; i < 1025; i++ {
        for _, c := range coins {
            if c <= i {
                dp[i] = 1 + dp[i - c]
            }
        }
    }

    return dp[1024-N]
}

编辑于 2021-05-03 23:09:49 回复(0)

Java

湛蓝之吻

public class Solution {
    /**
     *
     * @param N int整型
     * @return int整型
     */
    public int GetCoinCount (int N) {
        int money = 1024 - N;
        int count = money / 64 + (money % 64) / 16 + (money % 16) / 4 + money % 4;
        return count;
    }
}

发表于 2021-05-25 02:02:20 回复(2)

HTU-风起

import java.util.*;

public class Solution {
/**
*
* @param N int整型
* @return int整型
*/
public int GetCoinCount (int N) {
// write code here
int money = 1024-N;
int a = money/64;
int b = (money%64)/16;
int c = (money%16)/4;
int d = money%4;
return a+b+c+d;
}
}

发表于 2022-09-01 14:22:02 回复(0)

Java

hencejacki

import java.util.*;


public class Solution {
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
    public int GetCoinCount (int N) {
        // write code here
        int[] coins = new int[]{1, 4, 16, 64};
        int ans = 0;
        int i = coins.length - 1;
        N = 1024 - N;
        while (N > 0) {
            while (N >= coins[i]) {
                N -= coins[i];
                ans++;
            }
            i--;
        }
        return ans;
    }
}

贪心法

发表于 2023-04-02 14:33:22 回复(0)

wevo50

class Solution {
public:
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
    int GetCoinCount(int N) {
        // write code here
        int nums[1025]={0};
        int coins[4]={1,4,16,64};
        for(int i=0;i<1024;i++){
            for(int j=0;j<4;j++){
                if(coins[j]<=i){
                    nums[i]=1+nums[i-coins[j]];
                }
            }
        }
        return nums[1024-N];
    }
};

发表于 2023-01-12 09:04:54 回复(0)

輝长六加1

import java.util.*;
public class Solution {
  /**
   * 
   * @param N int整型 
   * @return int整型
   */
public int GetCoinCount (int N) {
      // write code here
      int[] coins = new int[]{1, 4, 16, 64};
      int diff = 1024 - N;

      int[] dp = new int[diff + 1];

      for (int i = 1;i <= diff;i++) {
          int min = Integer.MAX_VALUE;
          for (int coin : coins) {
              if (i >= coin) {
                  min = Math.min(min, dp[i - coin] + 1);
              }
          }

          dp[i] = min;
      }

      return dp[diff];
  }
}

发表于 2022-09-01 13:59:30 回复(0)

元气森林打气水

class Solution:
    def GetCoinCount(self , N ):
        # write code here
        num64 = (1024-N)//64
        num16 = (1024 - N - num64*64) // 16
        num4 = (1024 - N  - num64*64 - num16*16) // 4
        num1 = 1024- N  - num64*64 - num16*16 - num4*4
        return num64 + num16 + num4 + num1

发表于 2021-06-28 20:35:11 回复(0)

Angel20181107233280

import java.util.*;


public class Solution {
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
    public int GetCoinCount (int N) {
        // write code here
        int sum = 1024 - N;
        int count = 0 ;
        while(sum != 0) {
            if(sum >= 64) {
                count += sum / 64;
                sum -= sum / 64 * 64;
            }else if(sum >= 16) {
                count += sum / 16;
                sum -= sum / 16 * 16;
            }else if(sum >= 4) {
                count += sum / 4;
                sum -= sum / 4 * 4;
            }else if(sum >= 1) {
                count += sum;
                sum -= sum ;
            }
        }
        return count;
    }
}

发表于 2021-04-21 15:23:18 回复(0)

湮灭丶星空

暴力算法

import java.util.*;


public class Solution {
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
    public int GetCoinCount (int N) {
        N=1024-N;
        int a64=N/64;
        N=N%64;
        a64+=N/16;
        N=N%16;
        a64+=N/4;
        N=N%4;
        a64+=N;
        return a64;
    }
}

发表于 2021-04-17 16:25:48 回复(0)

yongkangm

提交时间：2021-04-16 语言：Java 运行时间： 12 ms 占用内存：11148K 状态：答案正确

import java.util.*;
public class Solution {
    public int GetCoinCount (int N) {
        if (N==1024){return 0;}
        int[] nums = {64,16,4,1};//找零次数最少，优先给大额的面值
        int counts = 0;
        int money = 1024 - N;//需要找零的钱数目
        while(money != 0){//待找零为零跳出循环
            for(int i = 0;i < nums.length;i++){
                if(money >= nums[i]){//待找零金额大于当前面额就给当前面额
                    counts+=money/nums[i];//整除，记录当前面额的硬币给与的次数
                    money = money % nums[i];//取模，记录余数，既是还没有找零的数目
                }
            }
        }
        return counts;
    }
}

发表于 2021-04-16 18:00:16 回复(0)

@fly

import java.util.*;

public class Solution {
/**
*
* @param N int整型
* @return int整型
*/
public int GetCoinCount (int N) {
// write code here
int lef = 1024 -N;
if(lef < 4){
return lef;
}
int []coine = {64,16,4,1};
int index = 0;
int sum = 0;
while (lef >= 4){
int count = lef /coine[index];
lef = lef % coine[index];
sum = sum + count;
index ++;
}
return sum + lef;
}
}

编辑于 2021-04-14 22:19:00 回复(0)

Cactus_tt

class Solution {
public:
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
      int GetCoinCount(int N) {
    	N=1024-N;
        int a,b,c,d,t;
        a=b=c=d=t=0;
        a=N/64;
        t=N%64;
        b=t/16;
        t=t%16;
        c=t/4;
		d=t%4; 
        return a+b+c+d;
    }
};

发表于 2021-04-14 21:52:59 回复(0)

宜乐

import java.util.*;
import java.math.*;


public class Solution {
    /**
     * 
     * @param N int整型 
     * @return int整型
     */
    public int GetCoinCount (int N) {
        // write code here
        int sum = 1024-N;
        if(sum<4){
            return sum;
        }
        int[] f = new int[sum+1];
        f[0] = 0;
        f[1] = 1;
        for(int i=2;i<sum+1;i++){
            int t1 = f[i-1];
            int t2 = i-4>=0?f[i-4]:1025;
            int t3 = i-16>=0?f[i-16]:1025;
            int t4 = i-64>=0?f[i-64]:1025;
            int m1 = Math.min(t1,t2);
            int m2 = Math.min(t3,t4);
            f[i] = Math.min(m1,m2)+1;
        }
        return f[sum];
    }
}

发表于 2021-04-13 18:28:55 回复(0)