NC602 题解 | #牛牛凑数字#

题意分析

• 给出固定的花费n，同时给出1-9每个数字的花费，我们需要用n购买数字使得最后拼凑的数字尽可能大。返回一个字符串。

思路分析

• 我们发现，对于给定的花费，想要拼凑出尽可能大的数字，我们首先需要满足的是位数尽可能大。很显然，这个位数我们可以通过将这个花费购买某一个数字，寻找购买哪个数字可以得到最多的数字的个数即可。对于可以得到相同个数的数字，我们尽可能让这个数字尽可能大。

• 证明：我们可以发现其实这是一个完全背包的模型，这里给出的固定的花费就是背包的容量，然后每个数字的价值就是题目给出的，容量都是1，利用背包的方法可以发现其实就是找到花费最小的那个数字，将所有的钱都买这个数字，就是我们可以得到最多的位数。

• 但是，这并不是最后的答案，我们发现，假如给定的钱是5，其中数字1的单价是2，数字2的单价是3，其余的花费都是10，那么很显然，我们将所有的钱都买1得到的数字的个数最多，但是这并不是最优解，我们发现，都买1的话最后的钱会剩余1。其实我们可以利用一个买1的钱买一个2，最后得到的最优解就是21。

• 所以，得到了最多的位数，我们需要从高位进行替换这个数字，将数字替换尽可能大，当然，不能比当前的数字小。利用一个while不断寻找即可。

• 下面举个例子进行分析

• 复杂度分析
  • 题目中对1-9进行了一次遍历找到最小值，但是在替换的时候可能会达到$n-1n-1$次，例如将22222...2222,替换成3333.33332所以总的时间复杂度为$O(n)O(n)$
  • 过程中只用来少数几个变量，空间复杂度为$O(1)O(1)$

C++写法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型vector 1-9这九个数字的价格数组
     * @return string字符串
     */
    string buyNumber(int n, vector<int>& a) {
        // write code here
        string ans="";
        int mx=0,key=-1;  // key记录相同位数填的最大的数字
        // 找到可以在相同的位数下填充最大的数字
        for(int i=8;i>=0;i--){
            int tmp=n/a[i];
            if(tmp>mx){
                mx=tmp;
                key=i;
            }
        }
        
        
        n=n-a[key]*mx;
        
        // 如果一个都买不起，那么直接返回-1即可
        if(key==-1){
            return "-1";
        }
        
       // 先填充mx位
        while(mx--){
            ans+=(key+'1');
        }
        
        // id记录下当前替换的位置
        int id=0;
        // 从高位开始进行替换，优先替换大的数字，所以是反向遍历
        for(int i=8;i>=0;i--){
            // 如果可以进行替换
            while(n+a[key]>=a[i]&&key<i){
                ans[id]=(i+'1');
                id++;
                n-=(a[i]-a[key]);
            }
        }
        return ans;
    }
};

Go写法

package main

import ( 
    "strconv"
    "strings"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 得到牛牛能够凑到的最大的数字
 * @param n int整型 牛牛能够承受的价格
 * @param a int整型一维数组 1-9这九个数字的价格数组
 * @return string字符串
*/
func buyNumber( n int ,  a []int ) string {
    // write code here
    mx := 0
    key := -1
    // 先找出最多可以填充的位数，同时维护填充的数字尽可能大
    for i := 8; i >= 0; i-- {
        tmp := n/a[i]
        if(tmp>mx){
            mx=tmp
            key=i
        }
    }
    
    // 如果一个数字都没有，直接返回-1
    if(key==-1) {
        return string("-1")
    }
    
    n -= mx*a[key]
    
    ans := ""
    for {
        if(mx==0) {
            break
        }
        
        ans += strconv.Itoa(key+1)
        mx--
    }
    
    // 从高位开始选择进行替换
    for i := 8; i >= 0; i-- {
        for{
            // 循环判断是否可以进行替换，需要满足花费和数字要比当前填充的数字大
            if(n+a[key]>=a[i]&&i>key){
                ans = strings.Replace(ans, strconv.Itoa(key+1), strconv.Itoa(i+1),1)
                n-=(a[i]-a[key])
            }else{
                break
            }
        }
    }
    return ans;
}