Java DFS Solution


  • 0
    public int findKthNumber(int n, int k) {
    	Deque<Integer> stack = new ArrayDeque<>();
    	int count=0;
    	for(int i=1;i<10;i++) {
    		stack.push(i);
    		while(!stack.isEmpty()) {
    			int current = stack.pop();
    			if(k==++count) return current;
    			int countInSubtree = count(n,current);
    			if(countInSubtree+count<k) {
    				count=countInSubtree+count-1;
    			} else {
    				for(int j=9;j>=0;j--) {
    					int nextVal = Integer.parseInt(""+current+j);
    					if(nextVal<=n) {
    						stack.push(nextVal);
    					}
    				}
    			}
    		}
    	}
    	return -1;
    }
    
    public int count(int n, long val) {
    	int ans = 0;
    	int number = 1;
    	while(val<=n) {
    		ans += number;
    		val *= 10;
    		number *= 10;
    	}
    	if(n<(val/10+number/10-1)) ans -= val/10+number/10-1-n;
    	return ans;
    }
    

  • 0
    D

    Same here. But I didn't use the count method so I got TLE. I tried my best to learn the count method but I failed. Could you explain a bit more on the count method? Thanks.


  • 0
    F

    Nice solution. But you need to consider the Integer overflow problem. change following block of your code

    for(int j=9;j>=0;j--) {
    	int nextVal = Integer.parseInt(""+current+j);
    	if(nextVal<=n) {
    		stack.push(nextVal);
    	}
    }
    

    to

    for(int j=9;j>=0;j--) {
         if (Long.parseLong(""+current+j) <= (long)n) {
    	  int nextVal = Integer.parseInt(""+current+j);
        	 stack.push(nextVal);
         }
    }
    

    could pass the case
    681692778
    351251360


Log in to reply
 

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