推 JIWP: 大師 02/02 12:31
→ SecondRun: 這什麼怪題目 02/02 12:35
※ 編輯: Rushia (122.100.73.13 臺灣), 02/02/2024 12:36:17
https://leetcode.com/problems/sequential-digits/description
1291. Sequential Digits
一個Sequential Digits是一個數字滿足所有位數都比前面的位數恰好多出一例如：
123 456，給你兩個數字low 和 high，求介於 low~high的所有Sequential Digits
並排序之。
思路：
1.用dfs窮舉所有的可能，不斷的把尾數+1並append到原本的數字直到超出high，
因為測資範圍為 10~10^9 所以可以從12開始窮舉，然後排除掉尾數0的case。
Java Code：
---------------------------------------------------------
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= 8; i++) {
dfs(i * 10 + (i + 1), low, high, res);
}
res.sort(Comparator.naturalOrder());
return res;
}
private void dfs(int num, int low, int high, List<Integer> res) {
if (num > high || (num % 10 == 0)) return;
if (num >= low) {
res.add(num);
}
dfs(num * 10 + (num % 10 + 1), low, high, res);
}
}
---------------------------------------------------------
上面是初版 後面改良一下變迭代
---------------------------------------------------------
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= 8; i++) {
int num = i * 10 + (i + 1);
while (num <= high && (num % 10 != 0)) {
if (num >= low) {
res.add(num);
}
num = (num * 10) + (num % 10 + 1);
}
}
res.sort(Comparator.naturalOrder());
return res;
}
}
---------------------------------------------------------
--
https://i.imgur.com/Df746ya.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706848089.A.1F2.html