[LeetCode] 1291. Sequential Digits

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:
Input: low = 100, high = 300
Output: [123,234]

Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:
10 <= low <= high <= 10^9

顺次数。

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

思路

题意是给一个下限 low 和一个上限 high，请输出一个有序的 list，list 里面是所有介于 low 和 high 之间的数字，同时数字满足每一位上的数字都比前一位上的数字大 1 。这道题有三种做法。暴力枚举，DFS和BFS。因为数据量的关系，所以这道题我觉得无论是什么做法，时间复杂度都是O(1)，空间复杂度都是O(n)，因为要输出的是一个list。

复杂度

时间O(1) - 因为在 low 和 high 之间的数字个数是有限的
空间O(1) - 因为在 low 和 high 之间的数字个数是有限的

思路一 - 暴力枚举

枚举虽然是暴力，但是由于最后答案本身就不是很多，所以代码也能过。具体的思路是，首先创建一个字符串“123456789”，按位遍历这个字符串，以在指针i上的数字作为开头，并尝试生成后面更大的数字。如果生成的数字大于high了就停止。

代码

Java实现

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        String s = "123456789";
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            for (int j = 0; j < s.length() - i + 1; j++) {
                int num = Integer.parseInt(s.substring(j, j + i));
                if (num > high) {
                    return res;
                }
                if (num >= low) {
                    res.add(num);
                }
            }
        }
        return res;
    }
}

思路二 - DFS

DFS的做法也是从1到9开始确定第一位上的数字。同时需要一个变量target记录已经生成的数字，那么下一个要被生成的数字就是target * 10 + start。举例，假设第一位start = 1，此时的target也是1；当遍历到下一层的时候，start = 2，target = 10 + 2 = 12；再下一层的时候，start = 3，target = 120 + 3 = 123。以此类推。

代码

Java实现

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            dfs(res, i, 0, low, high);
        }
        Collections.sort(res);
        return res;
    }

    private void dfs(List<Integer> res, int start, int target, int low, int high) {
        // base case
        if (target >= low && target <= high) {
            res.add(target);
        }
        if (start > 9 || target > high) {
            return;
        }
        dfs(res, start + 1, target * 10 + start, low, high);
    }
}

思路三 - BFS

BFS的做法跟DFS类似，也是先拿到第一个数字，用queue去筛一遍，如果在范围内就加到结果集。

代码

Java实现

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 9; i++) {
            queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int target = queue.poll();
            if (target >= low && target <= high) {
                res.add(target);
            }
            int tail = target % 10;
            if (tail < 9 && target <= high) {
                queue.offer(target * 10 + tail + 1);
            }
        }
        return res;
    }
}