Untitled
unknown
java
4 years ago
3.1 kB
5
Indexable
public class Test { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); solve2(n); } // non-recursive/simple loop private static void solve(int n) { int curr = 1; do { System.out.println(curr); } while ((curr = next2(curr, n)) != -1); } private static boolean next(LinkedList<Character> curr, int n) { // try appending '0'--this will always be the successor lexicographically but may not be smaller than 'n' curr.addLast('0'); if (toInteger(curr) <= n) { return true; } else { curr.removeLast(); } // try and increment the last digit without going over 'n' while (true) { if (curr.isEmpty()) { return false; } char lastDigit = curr.removeLast(); if (lastDigit == '9') { continue; } else { curr.addLast(++lastDigit); if (toInteger(curr) <= n) { return true; } } } } // TODO: this is too slow to be used in next() private static int toInteger(LinkedList<Character> curr) { String asString = curr.stream() .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append) .toString(); return Integer.parseInt(asString); } // same as next() but does not waste time converting between string and int private static int next2(int curr, int n) { // not necessary because n is bounded to a small int, but whatever) curr = Math.multiplyExact(curr, 10); if (curr <= n) { return curr; } else { curr /= 10; } while (true) { if (curr <= 0) { return -1; } int lastDigit = curr % 10; if (lastDigit == 9) { curr /= 10; continue; } else { curr++; if (curr <= n) { return curr; } } } } // if we visualize the above algorithm, it's basically doing a dfs of a trie where the first level has nodes // '1', '2', ... and then below that, every node has 10 children '0', '1', etc (the 'while' loop where it // ends up chopping off the tail of 'curr' is basically it going back up the tree). So let's just write that dfs private static void solve2(int n) { for (int firstDigit = 1; firstDigit <= 9; firstDigit++) { dfs(firstDigit, n); } } private static void dfs(int curr, int n) { if (curr > n) { // base case return; } else { System.out.println(curr); for (int appendDigit = 0; appendDigit <= 9; appendDigit++) { dfs((curr * 10) + appendDigit, n); } } } }
Editor is loading...