虚拟十叉树建模问题,面试出镜率最高的算法之一

2019年9月26日08:07:42 发表评论 65 views

首先摆上题目:

虚拟十叉树建模问题,面试出镜率最高的算法之一

摘自leetcode,本人最近刚买vip,因此看得到企业的出题频率:)

乍一看这一题貌似毫无头绪,什么是字典序?如何定位这个数?没错,刚接触这个题目的时候,我的脑筋里也是一团乱麻。

但是我觉得作为一个拥有聪明才智的程序员来说,最重要的能力就是迅速抽象问题、拆解问题的能力。经过一段时间的思考,我的脑筋里还是没有答案。

哈哈。

言归正传,我们来分析一下这个问题。

首先,什么是字典序?

什么是字典序?

简而言之,就是根据数字的前缀进行排序,

比如10 < 9,因为10的前缀是1,比9小,

再比如112 < 12,因为112的前缀11小于12。

这样排序下来,会跟平常的升序排序会有非常大的不同。先给你一个直观的感受,一个数乘10,或者加1,哪个大?可能你会吃惊,后者会更大。

但其实掌握它的本质之后,你一点都不会吃惊。

问题建模

画一个图你就懂了。

虚拟十叉树建模问题,面试出镜率最高的算法之一

每一个节点都拥有10个孩子节点,因为作为一个前缀 ,它后面可以接0~9这十个数字。而且你可以非常容易地发现,整个字典序排列也就是对十叉树进行先序遍历。1, 10, 100, 101, ... 11, 110 ...

回到题目的意思,我们需要找到排在第k位的数。找到他的排位,需要搞清楚三件事情:

  1. 怎么确定一个前缀下所有子节点的个数?
  2. 如果第k个数在当前的前缀下,怎么继续往下面的子节点找?
  3. 如果第k个数不在当前的前缀,即当前的前缀比较小,如何扩大前缀,增大寻找的范围?

接下来 ,我们一一拆解这些问题。

理顺思路

1. 确定指定前缀下所有子节点数

现在的任务就是给定一个前缀,返回下面子节点总数。

我们现在的思路就是用下一个前缀的起点减去当前前缀的起点,那么就是当前前缀下的所有子节点数总和啦。

//prefix是前缀,n是上界
var getCount = (prefix, n) => {
    let cur = prefix;
    let next = prefix + 1;//下一个前缀
    let count = 0;
    //当前的前缀当然不能大于上界
    while(cur <= n) {
        count += next - cur;//下一个前缀的起点减去当前前缀的起点
        cur *= 10; 
        next *= 10;
        // 如果说刚刚prefix是1,next是2,那么现在分别变成10和20
        // 1为前缀的子节点增加10个,十叉树增加一层, 变成了两层
        
        // 如果说现在prefix是10,next是20,那么现在分别变成100和200,
        // 1为前缀的子节点增加100个,十叉树又增加了一层,变成了三层
    }
    return count;//把当前前缀下的子节点和返回去。
}
复制代码

当然,不知道大家发现一个问题没有,当next的值大于上界的时候,那以这个前缀为根节点的十叉树就不是满十叉树了啊,应该到上界那里,后面都不再有子节点。因此,count += next - cur还是有些问题的,我们来修正这个问题:

count += Math.min(n+1, next) - cur;
复制代码

你可能会问:咦?怎么是n+1,而不是n呢?不是说好了n是上界吗?

我举个例子,假若现在上界n为12,算出以1为前缀的子节点数,首先1本身是一个节点,接下来要算下面10,11,12,一共有4个子节点。

那么如果用Math.min(n, next) - cur会怎么样?

这时候算出来会少一个,12 - 10加上根节点,最后只有3个。因此我们务必要写n+1。

现在,我们搞定了前缀的子节点数问题。

2. 第k个数在当前前缀下

现在无非就是往子树里面去看。

prefix这样处理就可以了。

prefix *= 10
复制代码

3.第k个数不在当前前缀下

说白了,当前的前缀小了嘛,我们扩大前缀。

prefix ++;
复制代码

框架搭建

整合一下刚刚的思路。

let findKthNumber = function(n, k) {
  let p = 1;//作为一个指针,指向当前所在位置,当p==k时,也就是到了排位第k的数
  let prefix = 1;//前缀
  while(p < k) {
    let count = getCount(prefix, n);//获得当前前缀下所有子节点的个数和
    if(p + count > k) { //第k个数在当前前缀下
      prefix *= 10;
      p++; //把指针指向了第一个子节点的位置,比如11乘10后变成110,指针从11指向了110
    } else if(p + count <= k) { //第k个数不在当前前缀下
      prefix ++;
      p += count;//注意这里的操作,把指针指向了下一前缀的起点
    }
  }
  return prefix;
};
复制代码

完整代码展示

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(n, k) {
  let getCount = (prefix, n) => {
    let count =  0;
    for(let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) 
      count += Math.min(next, n+1) - cur;
    return count;
  }
  let p = 1;
  let prefix = 1;
  while(p < k) {
    let count = getCount(prefix, n);
    if(p + count > k) {
      prefix *= 10;
      p++;
    } else if(p + count <= k) {
      prefix ++;
      p += count;
    }
  }
  return prefix;
};
复制代码

成功AC!

虚拟十叉树建模问题,面试出镜率最高的算法之一

作者:神三元
链接:https://juejin.im/post/5d7fb1e16fb9a06ac76de435
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: