Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/02/02 12:28)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串644/719 (看更多)

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