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 }