php成品网站超市,三个字的洋气商标名字,下载软件网站,网站后端模板要考虑完结《稀碎从零》系列了哈哈哈
这道题和【LC.42 接雨水】#xff0c;我愿称之为【笔试界的颜良文丑】
题型#xff1a;字典树、前缀获取、数组、树的先序遍历
链接#xff1a;440. 字典序的第K小数字 - 力扣#xff08;LeetCode#xff09;
来源#xff1…要考虑完结《稀碎从零》系列了哈哈哈
这道题和【LC.42 接雨水】我愿称之为【笔试界的颜良文丑】
题型字典树、前缀获取、数组、树的先序遍历
链接440. 字典序的第K小数字 - 力扣LeetCode
来源LeetCode
题目描述红字为笔者添加
这道题说实话看不懂是其hard的很大一个原因
给定整数 n 和 k返回 [1, n] 中字典序第 k 小的数字。
这边笔者解释下什么是字典序
440. 字典序的第K小数字 - 力扣LeetCodehttps://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1358635/zi-dian-xu-de-di-kxiao-shu-zi-by-leetcod-bfy0/
笔者的理解是【字典序】重点在序上那么作为一个【排序方式】它的法则即使”按照数字的前缀的大小、长度进行排序“例子110100101102112……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右边界创一个不熟悉的数据结构二叉树笔者都不是很熟悉不为明智之举。
但这个思路还是很重要的突破口这时候可以转换一个这个遍历方式起点是11遍历的方向只有【下】和【左】且以后的节点也是如此。”1向左走“需要满足1这个树下面没有其他的分支连10都不能有这就要求n是小于10的。而”1向下走“就需要1有”孩子节点“即以1为前缀的一众节点。
那么问题就可以转化为”看看第k个数是以谁为前缀的“这个问题。而这个问题难点就是”求出以各个数为前缀的数的个数“然后看看k是否在这个范围内①k在的话那么k-1i*10k-1是跳过i这个数i*10是i后面的第一个数即使 i0 。②k不在即knum的话说明以 i 为前缀的所有数都不满足条件那么i1相当于从1走向2k-num。③如果k num说明第k个数就是最后一个以 i 为前缀的数这种情况可以归于情况①
然后就是”求满足条件的数的个数“举个例子比较直观——比如说n是12345要求以122为前缀的数的个数。那么截取12345的前3位【123】。以122为前缀的数中1220—1229是一定12345的因此ans10。而122又是小于123的那么说明所有122为前缀的数都满足条件即anspow(10,2).。 以上例子是122123的情况假如是125123那么满足条件的只能是125X系列即10个 假如是 123 123那么满足条件的除了123X系列还有【1230012345】这个区间内的
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为前缀的那一大堆从ans1开始数}}// k 1说明1就是答案return ans;}// 获取合法前缀的数字个数int getNum(int ans,int n){string temp1 to_string(ans),temp2 to_string(n);int len1 temp1.length(),len2temp2.length(),div len2 - len1;//div表示n比ans多了多少位string temp3 temp2.substr(0,len1);int answer 0;//接收前缀的个数int int3 stoi(temp3);// 把位数短的数字的个数先获取出来for(int i0;idiv;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],工241 25 个数字;return answer;}
};
结算页面 还需要努力
你好四月
