algorithm - 步数程序

Question

我有以下问题:

The stepping number:

A number is called a stepping number if every adjacent digits, separated by commas, differ by 1. A stepping number can't be a 1-digit number, it must be at least a 2-digit number. For example, 45 and 8,343,545 are stepping numbers. But, 890,098 is not. The difference between ‘9’ and ‘0’ should not be considered as 1.

Given start number s and an end number e your function should list out all the stepping numbers in the range including both the numbers 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. 生成值为[000,999]的3位步数列表
2. 通过将 1 到 9 添加到新列表中然后添加列表 1 中的所有元素来创建另一个列表(逗号之前的最左边部分)
3. 找到大于或等于 s 的最小步进数并检查步进数是否在[s,e]
4. 生成步进数(通过使用列表 1 和列表 2)直到值大于 e

---

备注

列表 1 包含 010 和 012，但排除以 0 开头的值，而不是 01，例如 045(即使 45 本身也是有效值)

s和/或e小于或等于2位数可能需要特殊处理。