Title source

• leetcode

Title Description

title

Train of thought

class Solution {
    
    /* *  Calculation [1,n] Internal to cur Root ( start ) Number of nodes  */
    long getNodes(long prefix, long n){
      //prefix Is prefix ,n Is the upper limit 
        long curr = prefix;
        long next = prefix + 1; // Next prefix 
        long totalNodes = 0;   //  Count the number of qualified nodes 
        while (curr <= n){
        // Of course, the current prefix cannot be greater than the upper limit 
            //totalNodes += (std::min(next, n + 1) - curr); // Subtract the starting point of the current prefix from the starting point of the next prefix 
            totalNodes += std::min(next - curr, n + 1 - curr);
            curr *= 10;  // Go down 
            next *= 10;  // Go down 
        }
        return totalNodes;  // Return the child nodes under the current prefix .
    }
public:
    int findKthNumber(int n, int k) {
    
        long cur = 1; //  First traverse to 1 Big numbers at the beginning 
        --k;  //  because 1 Ergodic , therefore k--
        while (k > 0){
    
            int nodes = getNodes(cur, n);     //  To get to cur The child nodes at the beginning are qualified (<=n) number nodes
            if(nodes <= k){
       //  if nodes<=k It means that this nodes All nodes haven't arrived yet k
                cur++; // cur turn right 
                k -= nodes;   //  Offset nodes Nodes 
            } else{
      //  if nodes>k It means that nodes One node is enough 
                cur *= 10;  // cur Go down 
                --k;    //  take cur Calculate into k
            }
        }
        return (int)cur;   //  Last cur Will stay in the second k On a small number 
    }

};

Train of thought two

The question is leetcode：386. Dictionary order number Extension of , Let's print the array in dictionary order before , And this question allows us to quickly locate a certain position , Then we can't be the same as the previous question , One by one , You can't pass OJ, This is also the reason why the question is set as Hard Why . Then we have to find a way to locate quickly .

Look carefully at the array of dictionary order , We can find out , In fact, this is a 10 Fork tree , That is, the child node of each node can have , Such as digital 1 The child node of is 10 To 19, Numbers 10 The child nodes of can be 100 To 109, But because of n Size limit , It's not a full cross tree . By analyzing the examples given in the title, we can know , Numbers 1 The child nodes of are 4 individual (10,11,12,13), And the last number 2 To 9 No child nodes , So this problem actually becomes a problem of traversing a cross tree in advance , Then the difficulty becomes how to calculate the number of child nodes of each node , Such as digital 1 And number 2, We ask to start from... In dictionary traversal order 1 To 2 How many numbers to go through , Realize the 1 Add the number itself to step in . Then we expand the scope ten times , The scope becomes 10 To 20 Between , But because we have to consider n Size , First n by 13, So only 4 Child node , So we know from the numbers 1 Traverse to the number 2 To pass 5 A digital , Then let's see step Less than or equal to k, If it is , We cur Self increasing 1,k subtract step; If not , Indicate that the required number is in the child node , We are now cur multiply 10,k Self reduction 1, And so on , until k by 0 Launch cycle , here cur It's what you want ：

class Solution {
    
public:
    int findKthNumber(int n, int k) {
    
        int cur = 1;
        --k;
        while (k > 0) {
    
            long long step = 0, first = cur, last = cur + 1;
            while (first <= n) {
    
                step += min((long long)n + 1, last) - first;
                first *= 10;
                last *= 10;
            }
            if (step <= k) {
    
                ++cur;
                k -= step;
            } else {
    
                cur *= 10;
                --k; 
            }
        }
        return cur;
    }
};

---

---

---

This is a dictionary tree

Every node has 10 Child node , And each child node will have 10 Child node ……. You can find , The whole dictionary order arrangement is the pre order traversal of the cross tree ：1, 10, 100, 101, … 11, 110 …

According to the meaning of the topic , We need to find it in the k The number of bits , Find this row , There are three things you need to know ：

• How to determine the number of all child nodes under a prefix
• If the first k The number is under the current prefix , How to continue to look for the child nodes below ？
• If the first k The number is not in the current prefix , That is, the current prefix is relatively small , How to expand the prefix , Increase the scope of the search .

Determines the number of all child nodes under the specified prefix

Now what we have to do is , Give a prefix , Returns the total number of child nodes below .

The train of thought is ： Subtract the starting point of the current prefix from the starting point of the next prefix , Then it is the sum of the number of all child nodes under the current prefix .

long getCount(long prefix, long n){
      //prefix Is prefix ,n Is the upper limit 
        long curr = prefix;
        long next = prefix + 1; // Next prefix 
        long count = 0;
        while (curr <= n){
        // Of course, the current prefix cannot be greater than the upper limit 
            count += (next - curr);  // Subtract the starting point of the current prefix from the starting point of the next prefix 
            curr *= 10;
            next *= 10;
            //  If it's just prefix yes 1,next yes 2, So now they are 10 and 20
            // 1 Add... To the children of the prefix 10 individual , Ten forked trees add a layer ,  It's two layers 

            //  If now prefix yes 10,next yes 20, So now they are 100 and 200,
            // 1 Add... To the children of the prefix 100 individual , The ten fork tree has added another layer , It's three layers 
        }
        return count;  // Return the child nodes under the current prefix .
    }

The problem is , When next When the value of is greater than the upper limit , Then the cross tree with this prefix as the root node is not a full cross tree , You should go to the upper limit , There are no more child nodes behind , therefore count+=next−cur There are still some problems . Let's fix this problem ：

 count += (std::min(next, n + 1) - curr);

You may ask : Why ？ How is n+1 , instead of n Well ？ I didn't say that n Is that the upper limit ？

for instance , If now the upper bound n by 12, Work out to 1 Number of subsegments for prefix , First 1 Itself is a node , Next, let's count 10,11,12, Altogether 4 Child node .

If you use std::min(next, n + 1) - curr, At this time, there will be one less ,12 - 10 Add the root node , In the end, it's just 3 individual . So we must write n+1. namely ：

long getCount(long prefix, long n){
      //prefix Is prefix ,n Is the upper limit 
        long curr = prefix;
        long next = prefix + 1; // Next prefix 
        long count = 0;
        while (curr <= n){
        // Of course, the current prefix cannot be greater than the upper limit 
            count += (std::min(next, n + 1) - curr);  // Subtract the starting point of the current prefix from the starting point of the next prefix 
            curr *= 10;
            next *= 10;
            //  If it's just prefix yes 1,next yes 2, So now they are 10 and 20
            // 1 Add... To the children of the prefix 10 individual , Ten forked trees add a layer ,  It's two layers 

            //  If now prefix yes 10,next yes 20, So now they are 100 and 200,
            // 1 Add... To the children of the prefix 100 individual , The ten fork tree has added another layer , It's three layers 
        }
        return count;  // Return the child nodes under the current prefix .
    }

The first k The number is under the current prefix

You need to look inside the subtree , That is to add a layer ：

prefix *= 10

The first k The number is not under the current prefix

To put it bluntly , The current prefix is small , Let's expand the prefix .

prefix ++;

summary

class Solution {
    
    /* *  Calculation [1,n] Internal to cur Root ( start ) Number of nodes  */
    long getNodes(long prefix, long n){
      //prefix Is prefix ,n Is the upper limit 
        long curr = prefix;
        long next = prefix + 1; // Next prefix 
        long totalNodes = 0;   //  Count the number of qualified nodes 
        while (curr <= n){
        // Of course, the current prefix cannot be greater than the upper limit 
            //totalNodes += (std::min(next, n + 1) - curr); // Subtract the starting point of the current prefix from the starting point of the next prefix 
            totalNodes += std::min(next - curr, n + 1 - curr);
            curr *= 10;  // Go down 
            next *= 10;  // Go down 
            //  If it's just prefix yes 1,next yes 2, So now they are 10 and 20
            // 1 Add... To the children of the prefix 10 individual , Ten forked trees add a layer ,  It's two layers 

            //  If now prefix yes 10,next yes 20, So now they are 100 and 200,
            // 1 Add... To the children of the prefix 100 individual , The ten fork tree has added another layer , It's three layers 
        }
        return totalNodes;  // Return the child nodes under the current prefix .
    }
public:
    int findKthNumber(int n, int k) {
    
        long curr = 1; // The first dictionary order is small ( Namely 1)
        long prefix = 1;
        while (curr < k){
      //  Prefix from 1 Start 
            long nodes  = getNodes(prefix, n);  //  With  prefix  Root ,  With  n  The total number of elements of the maximum cross tree 
            if(curr + nodes  > k) {
     // The first k The number is under the current prefix 
                prefix *= 10;  // Go down to the next level 
                curr++; // Point the pointer to the position of the first child node , such as 11 ride 10 Later into 110, Pointer from 11 Yes 110
            }else {
       //  With  prefix  There is no second in a rooted cross tree  k  Elements 
                prefix++;  // Expand the range 
                curr += nodes ;
            }
        }
        return prefix;
    }

};