步进数字程序

Question

我有以下问题：

步数：

如果每个相邻的数字(用逗号分隔(相差 1，则数字称为步进数。步进数字不能是 1 位数字，它必须至少是 2 位数字。例如，45 和 8,343,545 是步进数字。 但是，890,098不是。"9"和"0"之间的区别应该 不被视为 1。

给定起始编号 s 和结束编号 e，您的函数应列出 排除范围内的所有步进数字，包括两个数字 s &e.

我的尝试：

public void steppingNumber(int s, int e) {
    while(s <= e) {
        String str = Integer.parseInt(s);
        if(isSteppingNumber(str)) System.out.print(str + " ");
        s++;
    }
}
public boolean isSteppingNumber(String str) {
    if(str.length() == 1) return false; // 1-digit number can't be a stepping number
    List<String> numbers = new ArrayList<>();
    while(str.length() >= 3) { // get every 3-digit comma-separated number
        numbers.add(str.substring(str.length()-3));
        str = str.substring(0,str.length()-3);
    }
    numbers.add(str); // Also get the last number left
    for(String num : numbers) { // for every 3-digit comma-separated number, check if it's a stepping number
        for(int i = 1; i < num.length(); i++) {
            int previousDigit = Character.getNumericValue(num.charAt(i-1));
            int currentDigit = Character.getNumericValue(num.charAt(i));
            if(Math.abs(previousDigit - currentDigit) != 1) return false;
        }
    }
    return true;
}

如果问题只是检查一个数字是否是步进数字，我想我的解决方案会很好。但是，如果我应该列出范围内的所有步进数字，比如 1 到 10^15，那么我的解决方案将运行线性时间，更不用说检查部分了。任何人都可以为给定的问题提供更好的解决方案吗？

Answer 1

您可以尝试打印 [s，e] 中的每个步进数字，而不是检查 [s，e] 中的每个数字。

它应该看起来像：

1. 生成一个 3 位步进数字列表，其值在 [000,999] 中
2. 通过将 1 到 9 添加到新列表中来创建另一个列表(逗号前的最左侧部分(，然后将列表 1 中的所有元素添加
3. 找到大于或等于 s 的最小步进数，并检查步进数是否在 [s，e] 中
4. 生成步进数字(通过使用列表 1 和列表 2(，直到值大于 e

---

备注

列表 1 包含 010 和 012，但排除值以 0 开头，但不像 045 那样01(即使 45 本身也是有效值(

小于或等于 2 位数字值的 s 和/或 e 可能需要专门处理。