要考虑完结《稀碎从零》系列了哈哈哈
这道题和【LC.42 接雨水】,我愿称之为【笔试界的颜良&文丑】
题型:字典树、前缀获取、数组、树的先序遍历
链接:440. 字典序的第K小数字 - 力扣(LeetCode)
来源:LeetCode
题目描述(红字为笔者添加)
这道题说实话,看不懂是其hard的很大一个原因
给定整数 n
和 k
,返回 [1, n]
中字典序第 k
小的数字。
这边笔者解释下什么是字典序
440. 字典序的第K小数字 - 力扣(LeetCode)https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1358635/zi-dian-xu-de-di-kxiao-shu-zi-by-leetcod-bfy0/
笔者的理解是:【字典序】重点在序上,那么作为一个【排序方式】,它的法则即使”按照数字的前缀的大小、长度进行排序“(例子:1,10,100,101,102,11,2……11在101前面,因为11的前缀是”1“,而101前缀是”10“,因此101在11前面;2前缀(虽然没有前缀吧)是2,比1大,因此凡是2打头的,都排在1打头的后面)
题目样例
示例 1:
输入: n = 13, k = 2 输出: 10 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1 输出: 1
提示:
1 <= k <= n <= 109
题目思路
笔者的思路来自LC宫水三叶(他的题解有点难看懂,但好在最后还是看懂了,需要有不错的code经验和思路)
LC宫水三叶题解https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1360662/by-ac_oier-m3zl/
这道题第一个难点,就是知道他是怎么排序的
配合题目描述那里的”十叉树“ ,不难可以看出,遍历方式是”十叉树的先序遍历“,那么本题就是【返回十叉树的先序遍历的第K个数】——>通关了(bushi)
这种方法固然可行,但本题只给了k和n(右边界),创一个不熟悉的数据结构(二叉树笔者都不是很熟悉)不为明智之举。
但这个思路还是很重要的突破口,这时候可以转换一个这个遍历方式:起点是1,1遍历的方向只有【下】和【左】,且以后的节点也是如此。”1向左走“需要满足1这个树下面,没有其他的分支,连10都不能有,这就要求n是小于10的。而”1向下走“,就需要1有”孩子节点“,即以1为前缀的一众节点。
那么问题,就可以转化为”看看第k个数是以谁为前缀的?“这个问题。而这个问题,难点就是”求出以各个数为前缀的数的个数“,然后看看k是否在这个范围内:①k在的话,那么k-1,i*10(k-1是跳过i这个数,i*10是i后面的第一个数,即使 i0 )。②k不在,即k>num的话,说明以 i 为前缀的所有数都不满足条件,那么i+1(相当于从1走向2),k-num。③如果k = num,说明第k个数就是最后一个以 i 为前缀的数(这种情况可以归于情况①)
然后就是”求满足条件的数的个数“:举个例子比较直观——比如说n是12345,要求以122为前缀的数的个数。那么截取12345的前3位【123】。以122为前缀的数中,1220—1229是一定<12345的,因此ans+=10。而122又是小于123的,那么说明,所有122为前缀的数都满足条件,即ans+=pow(10,2).。
以上例子是122<123的情况,假如是125>123,那么满足条件的只能是125X系列,即10个
假如是 123 == 123,那么满足条件的除了123X系列,还有【12300,12345】这个区间内的
C++代码
参考三叶思路的CPP coding
class Solution {
public:
int findKthNumber(int n, int k) {
//题目需求:返回第K小的数字,排序是按照:前缀越小,越靠前
// 三叶的题解
int ans = 1;
while(k > 1)
{
int num = getNum(ans,n);//num是以ans为前缀的数字的个数
if(num >= k)//第K个数在以ans为前缀的数字中
{
ans *=10;
k--;
}
else
{
ans ++ ;//以ans为前缀的这一大堆都不行,得换一个前缀
k-=num;//相当于抛弃了以ans为前缀的那一大堆,从ans+1开始数
}
}
// k == 1,说明1就是答案
return ans;
}
// 获取合法前缀的数字个数
int getNum(int ans,int n)
{
string temp1 = to_string(ans),temp2 = to_string(n);
int len1 = temp1.length(),len2=temp2.length(),div = len2 - len1;//div表示n比ans多了多少位
string temp3 = temp2.substr(0,len1);
int answer = 0;//接收前缀的个数
int int3 = stoi(temp3);
// 把位数短的数字的个数先获取出来
for(int i=0;i<div;i++)
answer += (int)pow(10,i);//n比ans长的部分
if(ans < int3)
{
answer += (int)pow(10,div);//pow返回double类型
}
if(ans == int3)//前缀相等
answer += n - ans * (int)pow(10,div) + 1;//以1024和10为例子,那么10为前缀的个数是[00-24],工24+1 = 25 个数字;
return answer;
}
};
结算页面
还需要努力!
你好,四月