求解仅含2、3、5、7的下一个更大数字：递归代码修复与优化

需要按升序遍历仅由数字2、3、5、7组成的数字，规则如下：

• 初始输入的数字可能包含其他数字
• 首次迭代后，仅处理由2、3、5、7构成的数字

示例 #

输入

3257737
3257777
3257787

预期输出

3257737 => 3257752 
3257777 => 3272222
3257787 => 3272222

注：以上是3个独立测试用例，输出的数字可再次作为输入生成递增序列。

尝试通过替换最后一位数字实现逻辑，编写了如下递归代码但无法编译运行，请问代码存在什么问题？该如何修复？

string generate_next_number(s){
    int len = s.length();
    if (s[len-1] < '2') {
        s[len-1] = '2';
    } else if (s[len-1] == '2') {
        s[len-1] = '3';
    } else if (s[len-1] < '5') {
        s[len-1] = '5';
    } else if (s[len-1] < '7'){
        s[len-1] = '7';
    } else {
        s[len-1] = '2';
        string s2 = generate_next_number(substr(s.length()-1));
        s = s2 + s[len-1];
    }
    return s;
}

还写了时间复杂度为O(4^位数)的暴力代码，但通用性不足，受位数限制。以下是针对10位数字编写的Python代码，若要支持可变位数可能需要使用递归：

def get_next_number(num):
    t1  = 10
    t2  = 10*10
    t3  = 10*t2
    t4  = 10*t3
    t5  = 10*t4
    t6  = 10*t5
    t7  = 10*t6
    t8  = 10*t7
    t9  = 10*t8
    digits = [2,3,5,7]
    for i9 in digits:
        d9=i9*t9
        for i8 in digits:
            d8=i8*t8
            for i7 in digits:
                d7=i7*t7
                for i6 in digits:
                    d6=i6*t6
                    for i5 in digits:
                        d5=i5*t5
                        for i4 in digits:
                            d4=i4*t4
                            for i3 in digits:
                                d3=i3*t3
                                for i2 in digits:
                                    d2=i2*t2
                                    for i1 in digits:
                                        d1=i1*t1
                                        for i0 in digits:
                                            d0=i0
                                            n = d17+d16+d15+d14+d13+d12+d11+d10+d9+d8+d7+d6+d5+d4+d3+d2+d1+d0
                                            if n <= num:
                                                continue
                                            return n
    # 当输入是最大的10位目标数字时，返回最小的11位目标数字
    return 22222222222 

递归代码的问题与修复 #

存在的问题 #

1. C++语法错误：函数参数s未声明类型，C++要求必须指定参数类型，应改为string generate_next_number(string s)。
2. substr调用错误：C++的string::substr方法签名是substr(pos, length)，你写的substr(s.length()-1)会从索引len-1开始取到末尾，而非取前len-1个字符，正确写法是s.substr(0, len-1)。
3. 递归拼接逻辑错误：当最后一位是7时，将最后一位设为2后递归处理前半部分，但拼接时错误地用s2 + s[len-1]——此时s的前半部分未被更新，应直接用递归返回的s2加上新的最后一位（即'2'）。
4. 未处理非法输入：原代码完全没考虑输入包含2、3、5、7以外数字的情况，比如输入3257787时，需要先找到大于该数的最小合法数字，而非直接修改最后一位。

修复后的递归代码 #

#include <string>
#include <algorithm>
using namespace std;

// 判断字符串是否仅由2、3、5、7组成
bool is_valid(const string &s) {
    for (char c : s) {
        if (c != '2' && c != '3' && c != '5' && c != '7') {
            return false;
        }
    }
    return true;
}

// 输入为合法数字时，生成下一个合法数字
string next_valid_number(string s) {
    int len = s.length();
    // 从最后一位向前尝试递增
    for (int i = len - 1; i >= 0; --i) {
        char current = s[i];
        if (current == '2') {
            s[i] = '3';
            fill(s.begin() + i + 1, s.end(), '2');
            return s;
        } else if (current == '3') {
            s[i] = '5';
            fill(s.begin() + i + 1, s.end(), '2');
            return s;
        } else if (current == '5') {
            s[i] = '7';
            fill(s.begin() + i + 1, s.end(), '2');
            return s;
        } else if (current == '7') {
            // 当前位无法递增，设为2后继续向前处理
            s[i] = '2';
        }
    }
    // 所有位都是7，返回长度+1的最小合法数字（全2）
    return string(len + 1, '2');
}

// 主函数：处理任意输入，返回下一个目标数字
string generate_next_number(string input) {
    int len = input.length();
    string candidate = input;
    
    if (!is_valid(input)) {
        // 输入不合法，构造第一个大于输入的同长度合法数字
        bool found = false;
        for (int i = 0; i < len; ++i) {
            char c = candidate[i];
            if (c < '2') {
                candidate[i] = '2';
                fill(candidate.begin() + i + 1, candidate.end(), '2');
                found = true;
                break;
            } else if (c == '2') continue;
            else if (c < '3') {
                candidate[i] = '3';
                fill(candidate.begin() + i + 1, candidate.end(), '2');
                found = true;
                break;
            } else if (c == '3') continue;
            else if (c < '5') {
                candidate[i] = '5';
                fill(candidate.begin() + i + 1, candidate.end(), '2');
                found = true;
                break;
            } else if (c == '5') continue;
            else if (c < '7') {
                candidate[i] = '7';
                fill(candidate.begin() + i + 1, candidate.end(), '2');
                found = true;
                break;
            } else {
                // 当前位大于7，设为2后递归处理前半部分
                candidate = next_valid_number(candidate.substr(0, i+1)) + string(len - i - 1, '2');
                found = true;
                break;
            }
        }
        // 若输入大于同长度最大合法数字，返回更长的全2数字
        if (!found) candidate = string(len + 1, '2');
    } else {
        // 输入合法，直接生成下一个数字
        candidate = next_valid_number(input);
    }
    
    return candidate;
}

暴力代码的优化 #

暴力枚举的时间复杂度为O(4^n)（n为位数），位数较大时效率极低，且代码硬编码位数无法适配任意长度输入。推荐采用进制转换思路：将合法数字看作4进制数，每一位对应2、3、5、7，快速计算下一个数字，时间复杂度为O(n)。

进制转换思路的Python实现 #

def get_next_number(num):
    digits = [2, 3, 5, 7]
    num_str = str(num)
    n_len = len(num_str)
    
    def generate_candidate():
        # 判断输入是否为合法数字，并转换为4进制表示
        base4 = []
        is_valid = True
        for c in num_str:
            digit = int(c)
            if digit not in digits:
                is_valid = False
                break
            base4.append(digits.index(digit))
        
        if is_valid:
            # 4进制数加1，模拟进位
            carry = 1
            for i in range(len(base4)-1, -1, -1):
                base4[i] += carry
                if base4[i] == 4:
                    base4[i] = 0
                    carry = 1
                else:
                    carry = 0
                    break
            if carry == 1:
                # 溢出，返回长度+1的最小合法数字
                return int('2'*(n_len+1))
            # 转换为目标数字
            res = 0
            for d in base4:
                res = res * 10 + digits[d]
            return res
        else:
            # 输入不合法，构造第一个大于输入的合法数字
            candidate = []
            found = False
            for i in range(n_len):
                current = int(num_str[i])
                # 找第一个大于当前位的合法数字
                for d in digits:
                    if d > current:
                        candidate.append(str(d))
                        candidate += ['2']*(n_len - i -1)
                        found = True
                        break
                if found:
                    break
                elif d == current:
                    candidate.append(str(d))
                else:
                    # 所有合法数字都小于当前位，返回更长的全2数字
                    candidate = ['2']*(n_len +1)
                    found = True
                    break
            if not found:
                candidate = ['2']*(n_len +1)
            return int(''.join(candidate))
    
    res = generate_candidate()
    # 确保结果严格大于输入
    if res <= num:
        res = int('2'*(n_len +1))
    return res

# 测试示例
print(f"3257737 => {get_next_number(3257737)}")
print(f"3257777 => {get_next_number(3257777)}")
print(f"3257787 => {get_next_number(3257787)}")

运行结果：

3257737 => 3257752
3257777 => 3272222
3257787 => 3272222

内容的提问来源于stack exchange，提问作者ishandutta2007