题解 | #牛牛凑数字#

题意整理

给定1-9共9个数字，a数组记录了每个数字的价格。
牛牛手上有n元钱，为了凑出最大的数字带回家，问牛牛应该怎么买，并返回最大的数字。

方法一（贪心）

1.解题思路

首先计算最便宜的数字是多少。
然后根据最便宜的数字，得到最多买多少个数字，以及买了之后，剩余多少钱。因为要凑出最大的数字，所以数字个数应尽可能多。
先假设买的全是最便宜的数字，如果某个数字比最便宜数字大，并且可以用剩余的钱来补，则将当前数字替换为这个较大的数字。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型一维数组 1-9这九个数字的价格数组
     * @return string字符串
     */
    public String buyNumber (int n, int[] a) {
        //求最便宜的数字是多少
        int num=1;
        for(int i=2;i<=9;i++){
            if(a[i-1]<a[num-1]){
                num=i;
            }
        }

        //如果最便宜的都买不起，直接返回-1
        if(n<a[num-1]) return "-1";
        //cnt带回的数字的最大个数，remain是剩余的钱
        int cnt=n/a[num-1];
        int remain=n%a[num-1];
        //初始化可变字符串
        StringBuilder sb=new StringBuilder();

        for(int i=9;i>=num;i--){
            //如果剩余的钱可以换更大的数字，则换取更大的数字
            while(remain>=a[i-1]-a[num-1]&&cnt>0){
                sb.append(i);
                cnt--;
                remain-=a[i-1]-a[num-1];
            }
        }

       return sb.toString();
    }
}

3.复杂度分析

时间复杂度：假设最小的数字是num，最多添加 $n/a[num-1]$ 个数字到可变字符串，所以时间复杂度为 $O(n/a[num-1])$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（贪心+排序）

1.解题思路

首先计算最便宜的数字是多少。
然后只要剩余的钱大于最便宜的数字，说明可以继续买。先确定当前最长长度，只要大于等于最长长度，则可以选更大的数字，将最后确定的数字添加到可变字符串，并扣掉对应的花费。
将得到的字符串转化为字符数组，并排序，反转之后即是最大的组合。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型一维数组 1-9这九个数字的价格数组
     * @return string字符串
     */
    public String buyNumber (int n, int[] a) {
        //求最便宜的数字是多少
        int num=1;
        for(int i=2;i<=9;i++){
            if(a[i-1]<a[num-1]){
                num=i;
            }
        }

        //如果最便宜的都买不起，直接返回-1
        if(n<a[num-1]) return "-1";

        StringBuilder sb=new StringBuilder();

        while(n>=a[num-1]){
            int maxLen=0;
            int curNum=-1;
            //寻找满足当前长度最大，并且当前数字最大对应的curNum
            for(int i=1;i<=9;i++){
                if(n/a[i-1]>=maxLen){
                    maxLen=n/a[i-1];
                    curNum=i;
                }
            }
            //添加到sb
            sb.append(curNum);
            n-=a[curNum-1];
        }

        //转化为字符数组，并排序
        char[] arr=sb.toString().toCharArray();
        Arrays.sort(arr);

        //再转化为可变字符串，并反转，得到最大的数字
        StringBuilder res=new StringBuilder();
        res.append(arr);
        return res.reverse().toString();
    }
}

3.复杂度分析

时间复杂度：假设最小的数字是num，最多添加 $n/a[num-1]$ 个数字到可变字符串，对应排序的时间复杂度为 $O((n/a[num-1])log_2(n/a[num-1]))$ ，所以最终的时间复杂度为 $O((n/a[num-1])log_2(n/a[num-1]))$ 。
空间复杂度：不需要额外长度为 $n/a[num-1]$ 的arr字符数组，所以空间复杂度为 $n/a[num-1]$ 。