给定一个正整数,请你找到最大的正整数,满足该正整数所有数位之和等于,且每个数位都不相等(每个数位不能是0)。
举个例子,如果,那么答案是421。因为4+2+1=7,且每个数位都不相等。
import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = in.nextInt(); if (n > 45) { System.out.println(-1); return; } else if (n < 3) { System.out.println(n); return; } else { int res = 0; ArrayList<Integer> nums = new ArrayList<>(); int min = 1; int rest = 0; while (n != 0) { nums.add(min); n -= min; min++; if ((n - min) < (min + 1)) { if (n<10 && n>0){ nums.add(n); } else { rest = n - 9; nums.add(9); } break; } } int times = 1; for (int i = nums.size() - 2; i >= 0; i--) { int cur = nums.get(i); if (rest <= 9 - times - cur) { nums.set(i, cur + rest); break; } else { nums.set(i, 9 - times); rest = rest - (9 - times - cur); times++; } } for (int i = 0; i < nums.size(); i++) { res += nums.get(i) * Math.pow(10, i); } System.out.println(res); } } }维护状态,每次找到最小还原次数,然后向后向前遍历直到遇到0(Max_Value)