JAVA Solution with a map to record the uncomplete subtree then DFS


  • 0
    T
       /**
         * for each subtree if it is complete tree
         * then the num of child is 11111....
         * so first find the root of each layer which is uncomplete and record the numbers of child
         */
        public int findKthNumber(int n, int k) {
            int cur = 1;
            k = k - 1;
            int layer = (int)Math.log10(n);
            int seg = 0;
            for (int i = 0 ; i <= layer; i ++) {
                seg += Math.pow(10, i);
            }
            Map<Integer, Integer> map = new HashMap<>();
            map.put(n, 1);
            int cu = n / 10;
            int va = n % 10;
            map.put(cu, va + map.get(n)+1);
            gettheUncompletelyWay(cu , map);
            //calculate the D_value of root cur and cur + 1;
            while (k > 0) {
                int Dvalue;
                if (map.containsKey(cur)) {
                    Dvalue = map.get(cur);
                    if (k >= Dvalue) {
                        cur += 1;
                        k -= Dvalue;
                    }else {
                        cur *= 10;
                        k -= 1;
                    }
                    seg = (seg - 1)/10;
                }else {
                    Dvalue = seg;
                    if (k >= Dvalue) {
                        cur += 1;
                        k -= Dvalue;
                    }else {
                        cur *= 10;
                        k -= 1;
                        seg = (seg - 1)/10;
                    }
                }
            }
            return cur;
        }
    
        //get the way that is consist of each root of uncomplete tree and the number of child
        //using map dp solution
        private void gettheUncompletelyWay(int n, Map<Integer, Integer> map) {
            int t = 11;
            int pre = 1;
            while (n >= 10) {
                int cu = n / 10;
                int va = n % 10;
                map.put(cu, va * t + map.get(n)+ (10 - va - 1) * pre + 1);
                pre = t;
                t = t * 10 + 1;
                n = cu;
            }
        }
    

Log in to reply
 

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