【Day47】1449. 数位成本和为目标值的最大数字

1449. 数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数:

  • 给当前结果添加一个数位(i + 1)的成本为 cost[i] (cost 数组下标从 0 开始)。
  • 总成本必须恰好等于 target 。
  • 添加的数位中没有数字 0 。

由于答案可能会很大,请你以字符串形式返回。

如果按照上述要求无法得到任何整数,请你返回 “0” 。

示例 1:

输入:cost = [4,3,2,5,6,7,2,5,5], target = 9
输出:"7772"
解释:添加数位 '7' 的成本为 2 ,添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字,但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2:

输入:cost = [7,6,5,5,5,6,8,7,8], target = 12
输出:"85"
解释:添加数位 '8' 的成本是 7 ,添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3:

输入:cost = [2,4,6,2,4,6,4,4,4], target = 5
输出:"0"
解释:总成本是 target 的条件下,无法生成任何整数。

示例 4:

输入:cost = [6,10,15,40,40,40,40,40,40], target = 47
输出:"32211"

提示:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

题解:

class Solution {
public:
    string largestNumber(vector& cost, int target) {
        int len=cost.size();
        vector dp(target+1,"#");
        dp[0]="";
        //因为i遍历的顺序是从小到大,就保证了整数的高位一定大于等于整数的低位,也就保证了整数最大
        for(int i=1;i=cost[i-1]&&dp[j-cost[i-1]]!="#"){
                    dp[j]=CompareString(dp[j],to_string(i)+dp[j-cost[i-1]]);
                }
            }
        return dp[target]=="#"?"0":dp[target];
    }
private:
    string CompareString(const string& s1,const string& s2){
        int m=s1.size(),n=s2.size();
        if(m==n)return max(s1,s2);
        return m>n?s1:s2;
    }
};

   转载规则


《【Day47】1449. 数位成本和为目标值的最大数字》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day48】278. 第一个错误的版本 【Day48】278. 第一个错误的版本
278. 第一个错误的版本你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, …,
2021-06-13
下一篇 
【Day46】279. 完全平方数 【Day46】279. 完全平方数
279. 完全平方数给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整
2021-06-11
  目录