LEETCODE 1449. Form Largest Integer With Digits That Add up to Target 解题思路分析

题目大意:

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

给你一个整数数组 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 。 "997" 也是满足要求的数字,但 "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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1449

解题思路分析:

这道题实际上有些类似于背包问题。target相当于背包容量,数字1-9相当于9个不同的物品,而每个数字的cost则相当于物品的体积。对于这类问题,是标准的动态规划思路,对于动态规划DP问题,我习惯使用递归加记忆数组的形式来解题。

首先我们定义一个递归函数,参数是当前的target。递归返回值为当前target下能够组成的最大数字。先看一下递归函数的终止条件:当target等于0时,说明我们已经消耗完了所有target,此时返回空字符串即可。另外如果target大于0,并且数字1-9的cost都大于target时,说明当前递归路径下无论如何我们也无法凑够总cost等于target的方法,此时返回字符串”0″。

递归函数中,我们从数字1循环到9,如果当前数字的cost小于target,说明我们可以选择当前数字,选择后,我们将target减去当前cost,并继续向下层递归。如果下层递归函数的返回值是”0″,说明当前选择方式无法得到合理解,跳过当前循环。反之递归函数的返回值加上当前数字即是当前循环的一个结果。循环完9个数字后,最大的一个结果即是当前递归的返回值。

另外需要注意一点,比较String形式数字的大小时,不能单纯的使用字典顺序来比较,而是要先比较字符串长度,较长的一方数字更大,如果两个字符串长度相同时再去比较字典顺序即可。

最后再考虑记忆数组。记忆数组的维数取决于递归函数中可变参数的数量。本题中可变的参数只有target一个,因此我们定义一个一维记忆数组即可,记忆数组的值为对应递归函数的返回结果。

实现代码:

String[] memo; // 记忆数组
public String largestNumber(int[] cost, int target) {
    memo=new String[target+1]; // 初始化记忆数组
    return help(cost,target); // 递归求解
}
String help(int[] cost, int target){
    if(target==0) return ""; // target为0,返回空
    // 如果记忆数组中存在当前解,返回记忆数组中的值
    if(memo[target]!=null) return memo[target];
    // 返回结果
    String max="";
    // 循环数字1-9(下标0-8)
    for(int i=0;i<cost.length;i++){
        // 如果当前数字的下标小于target
        if(cost[i]<=target){
            // 利用target减去当前cost后,递归至子问题
            String temp = help(cost,target-cost[i]);
            // 如果子问题结果是"0",代表当前选择为不合理解,跳过
            if("0".equals(temp)) continue;
            // 将子问题解加上当前选择的数字
            temp+=(i+1);
             // 如果当前解大于max,更新max值
            if(temp.length()>max.length()
               ||temp.length()==max.length()&&temp.compareTo(max)>=0){
                max=temp;
            }
        }
    }
    // 如果当前max为空,说明不存在合理解,设置max为"0"
    if("".equals(max)) max="0";
    // 将当前解存入记忆数组
    memo[target]=max;
    return max;
}

本题解法执行时间为282ms。

Runtime: 282 ms, faster than 19.68% of Java online submissions for Form Largest Integer With Digits That Add up to Target.

Memory Usage: 123.6 MB, less than 100.00% of Java online submissions for Form Largest Integer With Digits That Add up to Target.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1449-form-largest-integer-with-digits-that-add-up-to-target-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。