阿里春招模拟笔试题-Android-火柴拼出最大的数字

题目描述

使用火柴组成一个最大的数字, 规定:
可组成的数字  1   2   3   4   5   6   7   8   9
所需火柴数量  2   5   5   4   5   6   3   7   6
给定火柴总数m, 组成n位数字, 输出可以组成的最大值. 如果不能组成最大的数字, 输出0

题目要求组成最大值，可知所需火柴数量相同的数字中只需要最大的即可，所以真正需要的是：

所需数字：9   8   7   5   4   1
火柴数量：6   7   3   5   4   2

解题思路

采用贪心法从低位逐一确认最优解(数字最大)。
该位的最优解要满足剩下的火柴数量恰好足够n-i位使用(i为已确定的位数)。
那什么情况没有恰好满足剩下的n-i位使用呢？

1. m < 2*n, n位火柴使用数量最小的数，火柴不够用。
2. m > 7*n, n位火柴使用数量最大的数，火柴太多。

Code

import java.util.Scanner;

public class Main {
    
    static String maxSum(int m, int n) {
        final StringBuilder sb = new StringBuilder();

        //二维数组，表示数字和火柴数量
        int[][] a = new int[][]{{9, 8, 7, 5, 4, 1},{6, 7, 3, 5, 4, 2}};
        // 从低位构建每一位
        while (n > 0) {
            int i = -1;
            for (int j = 0; j < a[0].length; j++) {
                //可构成每位最优解的条件
                if (m - a[1][j] >= (n - 1) * 2 && m - a[1][j] <= (n - 1) * 7) {
                    //记录最优解位置
                    i = j;
                    //更改剩余火柴数
                    m -= a[1][j];
                    n--;
                    break;
                }
            }
            //i == -1说明最优解条件不成立
            if (i == -1) return "0";
            sb.append(a[0][i]);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        
        System.out.println(maxSum(m, n));
    }
}

样例

输入：

20
7

输出：

9771111

欢迎提出更多的解法