Java DFS + pruning heuristic


  • 0
    D
    public class Solution {
        private int kthNum;
        private int visited = -1;
    
        public int findKthNumber(int n, int k) {
            int digits = getDigits(n);
            dfs(0, digits, 0, 0, n, k);
            return kthNum;
        }
    
        private void dfs(int curLevel, int maxLevel, int digit, int value, int n, int k) {
            if (curLevel > maxLevel || visited >= k) {
                return;
            }
            int newvalue = value * 10 + digit;
            if (0 < curLevel && curLevel < maxLevel) {
                int leftBottom = getBottomValue(newvalue, curLevel, maxLevel, 0);
                int rightBottom = getBottomValue(newvalue, curLevel, maxLevel, 9);
                int subtreeNodes = getNodes(curLevel, maxLevel - 1) +
                        (leftBottom > n ? 0 : Math.min(n, rightBottom) - leftBottom + 1);
                if (visited + subtreeNodes < k) {
                    visited += subtreeNodes;
                    return;
                }
            }
            if (++visited == k) {
                kthNum = newvalue;
                return;
            }
            for (int i = curLevel == 0 ? 1 : 0; i < 10; i++) {
                dfs(curLevel + 1, maxLevel, i, newvalue, n, k);
            }
        }
    
        private int getBottomValue(int value, int curLevel, int maxLevel, int addup) {
            for (int i = 0; i < maxLevel - curLevel; i++) {
                value = value * 10 + addup;
            }
            return value;
        }
    
        private int getNodes(int curLevel, int maxLevel) {
            int total = 0;
            int here = 1;
            for (int i = curLevel; i <= maxLevel; i++) {
                total += here;
                here *= 10;
            }
            return total;
        }
    
        private int getDigits(int n) {
            int digits = 0;
            while (n > 0) {
                digits++;
                n /= 10;
            }
            return digits;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.