Print all Jumping Numbers smaller than or equal to a given value

A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1.
All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Given a positive number x, print all Jumping Numbers smaller than or equal to x. The numbers can be printed in any order.

Example:

Input: x = 20  
Output:  0 1 2 3 4 5 6 7 8 9 10 12

Input: x = 105  
Output:  0 1 2 3 4 5 6 7 8 9 10 12  
         21 23 32 34 43 45 54 56 65
         67 76 78 87 89 98 101

Note: Order of output doesn't matter,  
i.e. numbers can be printed in any order  

思路

找出规律, - 比如给定一个数字5, 它的下一位jump number可以是54, 56. - 比如给定一个数字9, 它的下一位jump number只能是98. - 比如给定一个数字10, 它的下一位jump number只可能是101.

然后如果只有一位的话应该是0到9. 从这些数挨个往上推的话就可以把所有以这些数字为开头的所有< target的jump number 找到。

Swift 题解

func solution(within target: Int) -> Int {  
        var result = [Int]()
        result.append(0)

        for i in 1...9 {
            let intermediate = helper(target: target, starting: i)
            result.append(contentsOf: intermediate)
        }

        return result
    }

    func helper(target: Int, starting: Int) -> [Int] {
        var result = [Int]()

        var q = [Int]()
        q.append(starting)

        while !q.isEmpty {
            let first = q.first!
            q.removeFirst()

            if first < target {
                result.append(first)

                let lastDigit = first % 10
                if lastDigit == 0 {
                    q.append(first * 10 + 1)
                } else if lastDigit == 9 {
                    q.append(first * 10 + 8)
                } else {
                    q.append(first * 10 + lastDigit - 1)
                    q.append(first * 10 + lastDigit + 1)
                }
            }
        }

        return result
    }

https://www.geeksforgeeks.org/print-all-jumping-numbers-smaller-than-or-equal-to-a-given-value/

https://leetcode.com/discuss/interview-question/360770/uber-onsite-jumping-numbers

chenbo

编程爱好者

Singapore