思路
今天的题应该我应该是走了一条很麻烦的岔路，一开始想的简单，后来也只能在这一条路上修修补补了。
大体思路如下：
先把t拆解乘质数2、3、5、7组合，如果还包含其他质数，直接返回-1；
因为要求无零，隐藏如果遇到0，转换为从这位开始后面全部跟1的数值
创建四个常用方法
- 构造符合当前剩余质因数条件的最小值
buildMinNumber(int[])
- 构造符合当前剩余质因数条件的最大值
buildMaxNumber(int[])
- 计算符合当前剩余质因数条件的最小值长度
calculateMinLength(int[])
- 当前剩余质因数条件减去当前位数值后的结果
subtract(int[],int)
开始构造，原数值从左往右遍历，
- 如果构造最大值不小于剩余位的值，那么继续遍历下一位
- 如果构造最大值小于剩余位的值，那么判断当前位的值。如果当前位是9，那么往前进位变1(因为无零)，构造最小值字符串连接并返回；如果不是9，那么从从当前位+1开始遍历，直到能构造满足条件的结果后连接并返回。
PS
额，今天拉了一坨。。。一开始没规划好，后面就光缝缝补补了。中午没午休都没改完，下午下班才完成！
代码
class Solution {
private static final int[] PRIMES = {2, 3, 5, 7};
private static final int[][] DIGIT_FACTORS = {
{0, 0, 0, 0}, // 1
{1, 0, 0, 0}, // 2
{0, 1, 0, 0}, // 3
{2, 0, 0, 0}, // 4
{0, 0, 1, 0}, // 5
{1, 1, 0, 0}, // 6
{0, 0, 0, 1}, // 7
{3, 0, 0, 0}, // 8
{0, 2, 0, 0} // 9
};
public String smallestNumber(String num, long t) {
int[] need = new int[4];
long remaining = t;
for (int i = 0; i < PRIMES.length; i++) {
while (remaining % PRIMES[i] == 0) {
need[i]++;
remaining /= PRIMES[i];
}
}
if (remaining > 1) {
return "-1";
}
int zeroIdx = num.indexOf('0');
if (zeroIdx > 0) {
num = num.substring(0, zeroIdx) + "1".repeat(num.length() - zeroIdx);
}
int n = num.length();
int minLen = calculateMinLength(need);
String minNum = buildMinNumber(need);
if (minLen > n || (minLen == n && minNum.compareTo(num) >= 0)) {
return minNum;
}
if (minLen == n && buildMaxNumber(need).compareTo(num) < 0) {
return "1" + minNum;
}
return buildFromNum(num, need);
}
private String buildFromNum(String num, int[] need) {
int n = num.length();
String maxNum = buildMaxNumber(need);
for (int i = 0; i < n; i++) {
int digit = num.charAt(i) - '0';
int[] temp = subtract(need, digit);
if (isAllZero(temp)) {
return num;
}
if (maxNum.length() < n - i - 1) {
need = temp;
continue;
}
maxNum = buildMaxNumber(temp);
int remainLen = n - i - 1;
if (maxNum.length() < remainLen) {
maxNum = "9".repeat(remainLen - maxNum.length()) + maxNum;
}
if (maxNum.length() == remainLen && maxNum.compareTo(num.substring(i + 1)) >= 0) {
need = temp;
continue;
}
if (digit == 9) {
int carry = i;
char[] chars = num.toCharArray();
while (carry >= 0) {
if (chars[carry] != '9') {
chars[carry]++;
break;
}
chars[carry] = '1';
carry--;
temp[1] += 2;
}
String build = buildMinNumber(temp);
num = new String(chars, 0, i) + "1".repeat(n - build.length() - i) + build;
if (carry < 0) {
num = "1" + num;
}
return num;
}
for (int d = digit + 1; d <= 9; d++) {
temp = subtract(need, d);
String suffix = buildMinNumberWithLength(temp, n - i - 1);
if (suffix != null) {
return num.substring(0, i) + d + suffix;
}
}
}
return num;
}
private String buildMinNumberWithLength(int[] factors, int targetLen) {
if (isAllZero(factors)) {
return "1".repeat(targetLen);
}
int minLen = calculateMinLength(factors);
if (minLen > targetLen) {
return null;
}
if (targetLen == 0) {
return "";
}
if (minLen < targetLen) {
return "1".repeat(targetLen - minLen) + buildMinNumber(factors);
}
return buildMinNumber(factors);
}
private String buildMinNumber(int[] factors) {
if (isAllZero(factors)) {
return "";
}
int len = calculateMinLength(factors);
if (len == 1) {
if (factors[1] == 2) return "9";
if (factors[0] == 3) return "8";
if (factors[3] == 1) return "7";
if (factors[0] == 1 && factors[1] == 1) return "6";
if (factors[2] == 1) return "5";
if (factors[0] == 2) return "4";
if (factors[1] == 1) return "3";
if (factors[0] == 1) return "2";
return "1";
}
for (int d = 2; d <= 9; d++) {
int[] remaining = subtract(factors, d);
if (remaining != null && calculateMinLength(remaining) == len - 1) {
return d + buildMinNumber(remaining);
}
}
return "";
}
private String buildMaxNumber(int[] factors) {
int[] counts = new int[10];
int c0 = Math.max(factors[0], 0), c1 = Math.max(factors[1], 0), c2 = Math.max(factors[2], 0), c3 = Math.max(factors[3], 0);
counts[9] = c1 / 2;
c1 %= 2;
counts[8] = c0 / 3;
c0 %= 3;
counts[7] = c3;
counts[5] = c2;
if (c0 == 2) {
counts[8]++;
} else if (c0 == 1) {
if (c1 == 1) {
counts[6]++;
c1 = 0;
} else {
counts[8]++;
}
}
if (c1 == 1) {
counts[9]++;
}
StringBuilder sb = new StringBuilder();
for (int d = 9; d >= 5; d--) {
sb.repeat(String.valueOf(d), counts[d]);
}
return sb.toString();
}
private int calculateMinLength(int[] factors) {
int len = 0;
int c0 = Math.max(factors[0], 0), c1 = Math.max(factors[1], 0), c2 = Math.max(factors[2], 0), c3 = Math.max(factors[3], 0);
len += c0 / 3 + c2 + c3;
c0 %= 3;
len += c1 / 2;
c1 %= 2;
if (c0 == 2 && c1 == 1) {
len += 2;
} else if (c0 > 0 || c1 > 0) {
len++;
}
return Math.max(len, 1);
}
private int[] subtract(int[] factors, int digit) {
int[] result = factors.clone();
if (digit == 0 || digit == 1) {
return result;
}
int[] required = DIGIT_FACTORS[digit - 1];
for (int i = 0; i < 4; i++) {
result[i] -= required[i];
}
return result;
}
private boolean isAllZero(int[] factors) {
for (int f : factors) {
if (f > 0) return false;
}
return true;
}
}
SomeBottle 08-07 20:081楼