这道题LeetCode 3348是难度极高的贪心/构造题。核心思路如下1. 质因子分析数位 1\sim9 的乘积只含质因子 2,3,5,7。若 t 分解后含有其他质因子直接返回 -1。2. 预处理 0若 num 中出现 0从第一个 0 开始把后面全部变成 1因为答案必须是无零数字。3. 从后往前贪心修改维护还需要的质因子个数 diff。先假设整个 num 不变从末尾开始逐位恢复该位的贡献然后尝试把当前位增大 1\sim9再用贪心优先用 8,9,4,6 等“单位位数贡献质因子最多”的数字判断剩余后缀能否在剩余位数内凑齐所需质因子。若能则从低位到高位填入大数、中间补 1得到最小合法答案。4. 增加位数若修改失败则答案长度必为 n1。构造满足 t 的最短数字串前面补 1 至长度 n1 即可。参考了力扣中文站的高赞 C 解法思路下面是可直接提交的 Rust 实现rustimpl Solution {pub fn smallest_number(num: String, t: i64) - String {let primes: [i64; 4] [2, 3, 5, 7];// 优先使用“效率”高的数字单位位数贡献的质因子多以最小化所需位数let ord: [usize; 8] [8, 9, 4, 6, 2, 3, 5, 7];// pf[d][i] 表示数字 d 包含第 i 个质因子2,3,5,7的个数let pf: [[i32; 4]; 10] [[0, 0, 0, 0],[0, 0, 0, 0],[1, 0, 0, 0],[0, 1, 0, 0],[2, 0, 0, 0],[0, 0, 1, 0],[1, 1, 0, 0],[0, 0, 0, 1],[3, 0, 0, 0],[0, 2, 0, 0],];let n num.len();let mut num_chars: Vecchar num.chars().collect();// 1. 处理 num 中的 0第一个 0 及之后全部变成 1for i in 0..n {if num_chars[i] 0 {continue;}for j in i..n {num_chars[j] 1;}break;}// 2. 分解 t只保留质因子 2,3,5,7let mut diff [0i32; 4];let mut tt t;for i in 0..4 {while tt % primes[i] 0 {tt / primes[i];diff[i] 1;}}if tt 1 {return -1.to_string();}// 3. 用 num 的各位抵消所需的质因子for c in num_chars {let d (*c as u8 - b0) as usize;for i in 0..4 {diff[i] - pf[d][i];}}if diff.iter().all(|d| d 0) {return num_chars.into_iter().collect();}// 4. 从后往前尝试修改某一位for i in (0..n).rev() {// 恢复下一位 num[i1] 的贡献后缀可自由填充if i 1 n {let d (num_chars[i 1] as u8 - b0) as usize;for j in 0..4 {diff[j] pf[d][j];}}let cur (num_chars[i] as u8 - b0) as usize;for d in (cur 1)..9 {let mut buf diff;// 恢复当前位原数字的贡献再减去新数字 d 的贡献for j in 0..4 {buf[j] pf[cur][j];buf[j] - pf[d][j];}// 贪心用 ord 中的数字尽可能多地填充减少所需位数let mut cnt [0i32; 10];for x in ord {let mut res i32::MAX;let mut ok true;for j in 0..4 {if pf[x][j] 0 {continue;}if buf[j] 0 {ok false;break;}res res.min(buf[j] / pf[x][j]);}if !ok {continue;}let c if res i32::MAX { 0 } else { res };cnt[x] c;for j in 0..4 {buf[j] - pf[x][j] * c;}}let total: i32 cnt.iter().sum();if total (n - i - 1) as i32 {continue;}// 构造答案从低位到高位填入大数字中间补 1let mut k n - 1;for x in (2..9).rev() {for _ in 0..cnt[x] {num_chars[k] (b0 x as u8) as char;k - 1;}}while k i {num_chars[k] 1;k - 1;}num_chars[i] (b0 d as u8) as char;return num_chars.into_iter().collect();}}// 5. 必须增加位数构造最短合法串前面补 1 至长度 n1let d0 (num_chars[0] as u8 - b0) as usize;for j in 0..4 {diff[j] pf[d0][j];}let mut cnt [0i32; 10];for x in (2..9).rev() {let mut res i32::MAX;let mut ok true;for j in 0..4 {if pf[x][j] 0 {continue;}if diff[j] 0 {ok false;break;}res res.min(diff[j] / pf[x][j]);}if !ok {continue;}let c if res i32::MAX { 0 } else { res };cnt[x] c;for j in 0..4 {diff[j] - pf[x][j] * c;}}let mut res_chars Vec::new();for x in (2..9).rev() {for _ in 0..cnt[x] {res_chars.push((b0 x as u8) as char);}}if res_chars.len() n {let ones n 1 - res_chars.len();for _ in 0..ones {res_chars.push(1);}}res_chars.reverse();res_chars.into_iter().collect()}}复杂度O(n \cdot 9 \cdot 8)其中 n \le 2\times10^5实际运行近似线性空间 O(n)。