牛客NC334 字典序第K小【困难 10叉树 Java/Go/PHP/C++】,力扣 440. 字典序的第K小数字

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/670c2bda374241d7ae06ade60de33e8b
https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/

本答案核心

10叉树,  数学规律

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return int整型*/public int findKth (int n, int k) {//10叉树//https://blog.csdn.net/a1439775520/article/details/104913782int cur = 1;k--;while (k > 0) {long step = 0, first = cur, last = cur + 1;while (first <= n) {step += Math.min(last, (long)(n + 1)) - first;first *= 10;last *= 10;}if (step > k) { //在树里k--;cur *= 10;}if (step <= k) {//不在树里k -= step;cur++;}}return cur;}
}

Go代码

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return int整型*/
func findKth(n int, k int) int {//10叉树//https://blog.csdn.net/a1439775520/article/details/104913782cur := 1k--for k > 0 {step := 0first := curlast := cur + 1for first <= n {num := n + 1if num > last {num = last}step += num - firstfirst *= 10last *= 10}if step > k { //在树里k--cur *= 10}if step <= k { //不在树里k -= stepcur += 1}}return cur
}

PHP代码

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param k int整型 * @return int整型*/
function findKth( $n ,  $k )
{//10叉树//https://blog.csdn.net/a1439775520/article/details/104913782$cur =1;$k--;while ($k >0) {$step =0;$first =$cur;$last =$cur+1;while ($first<=$n){$num = $n+1;if($num >$last){$num=$last;}$step+= $num-$first;$first*=10;$last*=10;}if($step > $k){//在树里$k--;$cur*=10;}if($step<=$k){ //不在树里$k-=$step;$cur+=1;}}return $cur;
}

C++代码

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @param k int整型* @return int整型*/int findKth(int n, int k) {//10叉树//https://blog.csdn.net/a1439775520/article/details/104913782int cur = 1;k--;while (k > 0) {long step = 0;long first = cur;long last = cur + 1;while (first <= n) {step += min(last, (long)(n + 1)) - first;first *= 10;last *= 10;}if (step > k) { //在树里k--;cur *= 10;}if (step <= k) { //不在树里k -= step;cur += 1;}}return cur;}
};