Hard
题目描述
给定一个表示正整数的字符串 num 和一个整数 t。
如果一个数字的所有位数都不为 0，则称这个数字为无零数字。
返回一个字符串，表示大于等于 num 的最小无零数字，使得其各位数字的乘积能被 t 整除。如果不存在这样的数字，返回 “-1”。
示例 1：
输入：num = "1234", t = 256
输出："1488"
解释：大于 1234 的最小无零数字且各位数字乘积能被 256 整除的数是 1488，其各位数字乘积等于 256。
示例 2：
输入：num = "12355", t = 50
输出："12355"
解释：12355 本身就是无零数字，且各位数字乘积能被 50 整除，各位数字乘积等于 150。
示例 3：
输入：num = "11111", t = 26
输出："-1"
解释：没有大于 11111 的数字其各位数字乘积能被 26 整除。
约束条件：
2 <= num.length <= 2 * 10^5num只包含数字字符 ‘0’ 到 ‘9’num不包含前导零1 <= t <= 10^14
提示：
t的质因数只能是 2, 3, 5, 7- 找到必须修改的最短后缀
- 尝试贪心地构造字符串
解题思路
这是一道复杂的数论和贪心题目。核心思路如下：
首先分析约束条件：由于 t 的质因数只能是 2, 3, 5, 7，而数字 1-9 的质因数分解为：
- 1 = 1
- 2 = 2
- 3 = 3
- 4 = 2²
- 5 = 5
- 6 = 2×3
- 7 = 7
- 8 = 2³
- 9 = 3²
我们需要检查 t 是否只包含质因数 2, 3, 5, 7，如果包含其他质因数则无解。
解题步骤：
- 质因数分解：将
t分解为 2^a × 3^b × 5^c × 7^d 的形式 - 检查可行性：如果分解后有余数，说明包含其他质因数，返回 “-1”
- 贪心构造：从右向左扫描字符串，找到第一个可以增大的位置
- 数字选择：对于每一位，选择能满足质因数要求的最小数字
关键在于如何贪心地选择数字。我们需要尽可能使用较小的数字，同时确保剩余的质因数能被后续位置的数字覆盖。这需要动态规划或回溯的思想来验证可行性。
对于无法直接增大当前数字的情况，需要向前回溯到可以增大的位置，然后重新构造后缀。
代码实现
class Solution {
public:
string smallestNumber(string num, long long t) {
// 分解t的质因数
vector<int> factors = {2, 3, 5, 7};
vector<int> need(4, 0);
long long temp = t;
for (int i = 0; i < 4; i++) {
while (temp % factors[i] == 0) {
need[i]++;
temp /= factors[i];
}
}
if (temp != 1) return "-1";
int n = num.length();
// 检查当前数字是否满足条件
auto check = [&](const string& s) -> bool {
vector<int> have(4, 0);
for (char c : s) {
if (c == '0') return false;
int digit = c - '0';
if (digit == 2 || digit == 4 || digit == 8) {
if (digit == 2) have[0]++;
else if (digit == 4) have[0] += 2;
else have[0] += 3;
}
if (digit == 3 || digit == 6 || digit == 9) {
if (digit == 3) have[1]++;
else if (digit == 6) have[1]++;
else have[1] += 2;
}
if (digit == 5) have[2]++;
if (digit == 7) have[3]++;
if (digit == 6) have[0]++;
}
for (int i = 0; i < 4; i++) {
if (have[i] < need[i]) return false;
}
return true;
};
if (check(num)) return num;
// 贪心构造
for (int pos = n - 1; pos >= 0; pos--) {
for (int digit = num[pos] - '0' + 1; digit <= 9; digit++) {
string candidate = num.substr(0, pos) + char('0' + digit);
// 计算前缀已有的质因数
vector<int> have(4, 0);
for (char c : candidate) {
int d = c - '0';
if (d == 2 || d == 4 || d == 8) {
if (d == 2) have[0]++;
else if (d == 4) have[0] += 2;
else have[0] += 3;
}
if (d == 3 || d == 6 || d == 9) {
if (d == 3) have[1]++;
else if (d == 6) have[1]++;
else have[1] += 2;
}
if (d == 5) have[2]++;
if (d == 7) have[3]++;
if (d == 6) have[0]++;
}
// 检查剩余需要的质因数是否可以用后缀填充
vector<int> remaining(4);
bool possible = true;
for (int i = 0; i < 4; i++) {
remaining[i] = max(0, need[i] - have[i]);
}
// 贪心填充后缀
string suffix = "";
int remainingPos = n - pos - 1;
// 优先使用包含多个质因数的数字
while (remainingPos > 0 && (remaining[0] > 0 || remaining[1] > 0 || remaining[2] > 0 || remaining[3] > 0)) {
bool found = false;
// 尝试使用8 (2^3)
if (remaining[0] >= 3 && remainingPos > 0) {
suffix += "8";
remaining[0] -= 3;
remainingPos--;
found = true;
}
// 尝试使用9 (3^2)
else if (remaining[1] >= 2 && remainingPos > 0) {
suffix += "9";
remaining[1] -= 2;
remainingPos--;
found = true;
}
// 尝试使用其他数字
else {
for (int d = 7; d >= 2; d--) {
if (remainingPos > 0) {
if (d == 7 && remaining[3] > 0) {
suffix += "7"; remaining[3]--; remainingPos--; found = true; break;
}
if (d == 6 && (remaining[0] > 0 || remaining[1] > 0)) {
suffix += "6";
if (remaining[0] > 0) remaining[0]--;
if (remaining[1] > 0) remaining[1]--;
remainingPos--; found = true; break;
}
if (d == 5 && remaining[2] > 0) {
suffix += "5"; remaining[2]--; remainingPos--; found = true; break;
}
if (d == 4 && remaining[0] >= 2) {
suffix += "4"; remaining[0] -= 2; remainingPos--; found = true; break;
}
if (d == 3 && remaining[1] > 0) {
suffix += "3"; remaining[1]--; remainingPos--; found = true; break;
}
if (d == 2 && remaining[0] > 0) {
suffix += "2"; remaining[0]--; remainingPos--; found = true; break;
}
}
}
}
if (!found) break;
}
// 检查是否还有未满足的需求
bool satisfied = true;
for (int i = 0; i < 4; i++) {
if (remaining[i] > 0) {
satisfied = false;
break;
}
}
if (satisfied) {
// 用1填充剩余位置
while (remainingPos > 0) {
suffix += "1";
remainingPos--;
}
return candidate + suffix;
}
}
}
return "-1";
}
};
class Solution:
def smallestNumber(self, num: str, t: int) -> str:
# 分解t的质因数
factors = [2, 3, 5, 7]
need = [0] * 4
temp = t
for i in range(4):
while temp % factors[i] == 0:
need[i] += 1
temp //= factors[i]
if temp != 1:
return "-1"
n = len(num)
def get_factors(digit):
result = [0] * 4
if digit in [2, 4, 8]:
if digit == 2:
result[0] = 1
elif digit == 4:
result[0] = 2
else:
result[0] = 3
if digit in [3, 6, 9]:
if digit == 3:
result[1] = 1
elif digit == 6:
result[1] = 1
else:
result[1] = 2
if digit == 5:
result[2] = 1
if digit == 7:
result[3] = 1
if digit == 6:
result[0] += 1
return result
def check(s):
have = [0] * 4
for c in s:
if c == '0':
return False
digit = int(c)
digit_factors = get_factors(digit)
for i in range(4):
have[i] += digit_factors[i]
for i in range(4):
if have[i] < need[i]:
return False
return True
if check(num):
return num
# 贪心构造
for pos in range(n - 1, -1, -1):
for digit in range(int(num[pos]) + 1, 10):
candidate = num[:pos] + str(digit)
# 计算前缀已有的质因数
have = [0] * 4
for c in candidate:
d = int(c)
digit_factors = get_factors(d)
for i in range(4):
have[i] += digit_factors[i]
# 检查剩余需要的质因数
remaining = [max(0, need[i] - have[i]) for i in range(4)]
# 贪心填充后缀
suffix = ""
remaining_pos = n - pos - 1
while remaining_pos > 0 and any(remaining):
found = False
# 优先使用包含多个质因数的数字
if remaining[0] >= 3 and remaining_pos > 0:
suffix += "8"
remaining[0] -= 3
remaining_pos -= 1
found = True
elif remaining[1] >= 2 and remaining_pos > 0:
suffix += "9"
remaining[1] -= 2
remaining_pos -= 1
found = True
else:
for d in [7, 6, 5, 4, 3, 2]:
if remaining_pos > 0:
if d == 7 and remaining[3] > 0:
suffix += "7"
remaining[3] -= 1
remaining_pos -= 1
found = True
break
elif d == 6 and (remaining[0] > 0 or remaining[1] > 0):
suffix += "6"
if remaining[0] > 0:
remaining[0] -= 1
if remaining[1] > 0:
remaining[1] -= 1
remaining_pos -= 1
found = True
break
elif d == 5 and remaining[2] > 0:
suffix += "5"
remaining[2] -= 1
remaining_pos -= 1
found = True
break
elif d == 4 and remaining[0] >= 2:
suffix += "4"
remaining[0] -= 2
remaining_pos -= 1
found = True
break
elif d == 3 and remaining[1] > 0:
suffix += "3"
remaining[1] -= 1
remaining_pos -= 1
found = True
break
elif d == 2 and remaining[0] > 0:
suffix += "2"
remaining[0] -= 1
remaining_pos -= 1
found = True
break
if not found:
break
# 检查是否满足所有需求
if all(r == 0 for r in remaining):
# 用1填充剩余位置
suffix += "1" * remaining_pos
return candidate + suffix
return "-1"
public class Solution {
public string SmallestNumber(string num, long t) {
// 分解t的质因数
int[] factors = {2, 3, 5, 7};
int[] need = new int[4];
long temp = t;
for (int i = 0; i < 4; i++) {
while (temp % factors[i] == 0) {
need[i]++;
temp /= factors[i];
}
}
if (temp != 1) return "-1";
int n = num.Length;
int[] GetFactors(int digit) {
int[] result = new int[4];
if (new[] {2, 4, 8}.Contains(digit)) {
if (digit == 2) result[0] = 1;
else if (digit == 4) result[0] = 2;
else result[0] = 3;
}
if (new[] {3, 6, 9}.Contains(digit)) {
if (digit == 3) result[1] = 1;
else if (digit == 6) result[1] = 1;
else result[1] = 2;
}
if (digit == 5) result[2] = 1;
if (digit == 7) result[3] = 1;
if (digit == 6) result[0]++;
return result;
}
bool Check(string s) {
int[] have = new int[4];
foreach (char c in s) {
if (c == '0') return false;
int digit = c - '0';
int[] digitFactors = GetFactors(digit);
for (int i = 0; i < 4; i++) {
have[i] += digitFactors[i];
}
}
for (int i = 0; i < 4; i++) {
if (have[i] < need[i]) return false;
}
return true;
}
if (Check(num)) return num;
// 贪心构造
for (int pos = n - 1; pos >= 0; pos--) {
for (int digit = num[pos] - '0' + 1; digit <= 9; digit++) {
string candidate = num.Substring(0, pos) + (char)('0' + digit);
// 计算前缀已有的质因数
int[] have = new int[4];
foreach (char c in candidate) {
int d = c - '0';
int[] digitFactors = GetFactors(d);
for (int i = 0; i < 4; i++) {
have[i] += digitFactors[i];
}
}
// 检查剩余需要的质因数
int[] remaining = new int[4];
for (int i = 0; i < 4; i++) {
remaining[i] = Math.Max(0, need[i] - have[i]);
}
// 贪心填充后缀
string suffix = "";
int remainingPos = n - pos - 1;
while (remainingPos > 0 && remaining.Any(x => x > 0)) {
bool found = false;
if (remaining[0] >= 3 && remainingPos > 0) {
suffix += "8";
remaining[0] -= 3;
remainingPos--;
found = true;
}
else if (remaining[1] >= 2 && remainingPos > 0) {
suffix += "9";
remaining[1] -= 2;
remainingPos--;
found = true;
}
else {
int[] candidates = {7, 6, 5, 4, 3, 2};
foreach (int d in candidates) {
if (remainingPos > 0) {
if (d == 7 && remaining[3] > 0) {
suffix += "7";
remaining[3]--;
remainingPos--;
found = true;
break;
}
else if (d == 6 && (remaining[0] > 0 || remaining[1] > 0)) {
suffix += "6";
if (remaining[0] > 0) remaining[0]--;
if (remaining[1] > 0) remaining[1]--;
remainingPos--;
found = true;
break;
}
else if (d == 5 && remaining[2] > 0) {
suffix += "5";
remaining[2]--;
remainingPos--;
found = true;
break;
}
else if (d == 4 && remaining[0] >= 2) {
suffix += "4";
remaining[0] -= 2;
remainingPos--;
found = true;
break;
}
else if (d == 3 && remaining[1] > 0) {
suffix += "3";
remaining[1]--;
remainingPos--;
found = true;
break;
}
else if (d == 2 && remaining[0] > 0) {
suffix += "2";
remaining[0]--;
remainingPos--;
found = true;
break;
}
}
}
}
if (!found) break;
}
if (remaining.All(x => x == 0)) {
suffix += new string('1', remainingPos);
return candidate + suffix;
}
}
}
return "-1";
}
}
/**
* @param {string} num
* @param {number} t
* @return {string}
*/
var smallestNumber = function(num, t) {
// 分解t的质因数
const factors = [2, 3, 5, 7];
const need = [0, 0, 0, 0];
let temp = t;
for (let i = 0; i < 4; i++) {
while (temp % factors[i]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × 10 × k) | n 为字符串长度，需要枚举每个位置和每个数字，k 为构造后缀的时间 |
| 空间复杂度 | O(n) | 主要用于存储结果字符串和中间变量 |