Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1215.html
1215. Stepping Numbers
Level
Medium
Description
A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1
. For example, 321
is a Stepping Number while 421
is not.
Given two integers low
and high
, find and return a sorted list of all the Stepping Numbers in the range [low, high]
inclusive.
Example 1:
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Constraints:
0 <= low <= high <= 2 * 10^9
Solution
First find all the Stepping Numbers from 0 to 10^d where d is the length of high
. Obviously, all 1-digit numbers from 0 to 9 are Stepping Numbers. Starting from 1-digit numbers 1 to 9 (0 is not included here since any other number cannot have leading zeros), obtain the Stepping Numbers that have one greater length. For example, for the number 20, the next Stepping Number is 201. For the number 25, the next Stepping Numbers are 254 and 256. For the number 29, the next Stepping Number is 298. Since the numbers may be very large, use data type Long
to represent the numbers. It is guaranteed that all the Stepping Numbers that are obtained are sorted.
After all the Stepping Numbers are obtained, use binary search to find the start index startIndex
and the end index endIndex
in the list of Stepping Numbers, where the number at ``startIndex is the minimum Stepping Number that is greater than or equal to
low, and the number at
endIndex is the maximum Stepping Number that is less than or equal to
high. Use a list of type
Integer to store all the Stepping Numbers in the indices range
[startIndex, endIndex]` of all the Stepping Numbers, and return the final list.
-
class Solution { public List<Integer> countSteppingNumbers(int low, int high) { int maxLength = String.valueOf(high).length(); List<Long> allSteppingNumbers = new ArrayList<Long>(); Queue<Long> queue = new LinkedList<Long>(); allSteppingNumbers.add(0L); for (long i = 1; i <= 9; i++) { allSteppingNumbers.add(i); queue.offer(i); } int length = 1; while (length < maxLength) { length++; int size = queue.size(); for (int i = 0; i < size; i++) { long num = queue.poll(); long lastDigit = num % 10; if (lastDigit > 0) { long newNum = num * 10 + lastDigit - 1; allSteppingNumbers.add(newNum); queue.offer(newNum); } if (lastDigit < 9) { long newNum = num * 10 + lastDigit + 1; allSteppingNumbers.add(newNum); queue.offer(newNum); } } } int startIndex = binarySearch(allSteppingNumbers, low); int endIndex = binarySearch(allSteppingNumbers, high); if (startIndex < 0) startIndex = -startIndex - 1; if (endIndex < 0) endIndex = -endIndex - 2; List<Integer> steppingNumbers = new ArrayList<Integer>(); for (int i = startIndex; i <= endIndex; i++) { long numLong = allSteppingNumbers.get(i); steppingNumbers.add((int) numLong); } return steppingNumbers; } public int binarySearch(List<Long> list, int key) { int low = 0, high = list.size() - 1; while (low <= high) { int mid = (high - low) / 2 + low; long num = list.get(mid); if (num == key) return mid; else if (num > key) high = mid - 1; else low = mid + 1; } return -low - 1; } }
-
class Solution: def countSteppingNumbers(self, low: int, high: int) -> List[int]: ans = [] if low == 0: ans.append(0) q = deque(range(1, 10)) while q: v = q.popleft() if v > high: break if v >= low: ans.append(v) x = v % 10 if x: q.append(v * 10 + x - 1) if x < 9: q.append(v * 10 + x + 1) return ans
-
class Solution { public: vector<int> countSteppingNumbers(int low, int high) { vector<int> ans; if (low == 0) ans.push_back(0); queue<long long> q; for (int i = 1; i < 10; ++i) q.push(i); while (!q.empty()) { int v = q.front(); q.pop(); if (v > high) break; if (v >= low) ans.push_back(v); int x = v % 10; if (x) q.push(1ll * v * 10 + x - 1); if (x < 9) q.push(1ll * v * 10 + x + 1); } return ans; } };
-
func countSteppingNumbers(low int, high int) []int { ans := []int{} if low == 0 { ans = append(ans, 0) } q := []int{1, 2, 3, 4, 5, 6, 7, 8, 9} for len(q) > 0 { v := q[0] q = q[1:] if v > high { break } if v >= low { ans = append(ans, v) } x := v % 10 if x > 0 { q = append(q, v*10+x-1) } if x < 9 { q = append(q, v*10+x+1) } } return ans }