牛客网算法——名企面试的笔试（2）

 剑指 Offer 15. 二进制中1的个数

package 牛客网名企面试笔试问题2021;

/**
 * @Classname 整数的1的个数
 * @Description TODO
 * @Date 2021/2/26 11:06
 * @Created by xjl
 */
public class 整数的1的个数 {
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

换的钱币是最少的一个的方案

package 牛客网名企面试笔试问题2021;

import java.util.Arrays;

/**
 * @Classname 换钱币最少数量
 * @Description TODO
 * @Date 2021/2/26 12:55
 * @Created by xjl
 */
public class 换钱币最少数量 {
    /**
     * @description TODO 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
     * @param: arr
     * @param: aim
     * @date: 2021/2/26 12:56
     * @return: int
     * @author: xjl
     * 

     * 嘉定的给定的钱币为i 那么他的换币方案是的有两个方案组成： i 表示的是的钱  ——————1是没有办法兑换货币 dp[i]=dp[i] 2 可是换 dp[i]=dp[i-arr[i]]+1
     */
    public int minMoney(int[] arr, int aim) {
        int len = arr.length;
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        //遍历的是全部的钱
        for (int i = 1; i = 0) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        return dp[aim] == Integer.MAX_VALUE - 1 ? -1 : dp[aim];
    }

    public int minMoney2(int[] arr, int aim) {
        int len = arr.length;
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        //表示的可以换的钱的张数量
        dp[0] = 0;
        //遍历的是全部的钱可能出现的钱
        for (int i = 1; i