【5 kyu】Who Is Next？（ Double Cola ）

pakolagij 发布于2019-08-21 16:53 / 2650人阅读

摘要：原题目题目有一个队列，排到的人，再次排到队尾，并将自己变成双倍。个人也觉得减法更一点

原题目

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on.
For example, Penny drinks the third can of cola and the queue will look like this:
Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny
Write a program that will return the name of a man who will drink the n-th cola.
Note that in the very beginning the queue looks like that:
Sheldon, Leonard, Penny, Rajesh, Howard

题目：有一个队列Sheldon, Leonard, Penny, Rajesh, Howard，排到的人，再次排到队尾，并将自己变成双倍。若给了一个队列names，排到的第r个人是谁？（题目比较绕，不知道该怎么描述?）

// 初始队列, 第一轮
["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"]

// Sheldon排过队之后，重新到队尾，并将自己复制了一份
["Leonard", "Penny", "Rajesh", "Howard", "Sheldon", "Sheldon"]

// ...
// 第二轮，队列如下
["Sheldon", "Sheldon", "Leonard", "Leonard", "Penny", "Penny", "Rajesh", "Rajesh", "Howard", "Howard"]

// 第三轮，队列如下
["Sheldon", "Sheldon", "Sheldon", "Sheldon", "Leonard", "Leonard", "Leonard", "Leonard", "Penny", "Penny", "Penny", "Penny", "Rajesh", "Rajesh", "Rajesh", "Rajesh", "Howard", "Howard", "Howard", "Howard"]

My Solution

队列每轮过后，队列中的人数将变为原来的二倍。若初始队列的长度为len，第r人位于第m轮

第一轮：n=1，sum = len
第二轮：n=2，sum = len + len * 2
第三轮：n=4，sum = len + len * 2 + len * 4
...
第m轮：n=2^m, sum = len + len * 2 + …… + len * n

则，第r个人在第m轮的排名为：x = r + len * n - sum

则，第r个人的名字在初始队列中排名为t(数组下标为t-1)，则：(t-1) * n < x <= t * n

所以，t = Math.ceil( x / n )

最后，代码整理如下：

function whoIsNext(names, r){
  var len = names.length;
  var sum = names.length;
  var n = 1;
  while(sum < r) {
    n *= 2;
    sum += len * n;
  }
  return names[Math.ceil((r + len * n - sum) / n) - 1]
}

Best Practices / Clever

function whoIsNext(names, r) {
  var l = names.length;
  while (r >= l) { r -= l; l *= 2; }
  return names[Math.ceil(names.length * r / l)-1];
}

对比

两个方法一个用加法，一个用减法，得出最后一轮的人数。个人也觉得减法更 clever 一点 ?

私有云海外云主机 kyu cola who dr who

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88866.html

Java设计模式之装饰模式详解

摘要：装饰者模式是动态地将责任附加到对象上。然后我们在子类计算价格的时候加上父类中计算好的配料的价格。结果可乐加冰可乐加冰加糖在的类库中就有很多实际应用到了装饰模式，比如就可以用来装饰，提供更加强大的功能。装饰者模式是动态地将责任附加到对象上。若要扩展功能，装饰者提供了比继承更有弹性的替代方案。假设我们有一个需求，是给一家饮料店做一个计算各种饮料价格的功能。听起来很简单，我们创建一个抽象...

sewerganger 2019-08-15 15:25 评论0 收藏0
koa-cola：只需一个react组件，同时支持单页应用(SPA)和服务器渲染(SSR)

摘要：是一个基于和的服务器端和浏览器端的的前后端全栈应用框架。是的组件，并且会进行数据初始化不但可以支持的数据初始化，还可以合并和的，使用同一个，和的无缝结合。 koa-cola是一个基于koa和react的服务器端SSR(server side render)和浏览器端的SPA(single page application)的web前后端全栈应用框架。 koa-cola使用typescr...

XGBCCC 2019-08-22 10:54 评论0 收藏0
【5 kyu】Largest 5 digit number in a series

摘要：原题目题目找出一个数值该数值将以字符串的形式传入中最大的五位数。如果数字的位数小于，则直接返回该数值如果数字的位数不小于六位，则依次截取连续的位数，求取最大值对比中使用了递归。原题目 In the following 6 digit number:28391091 is the greatest sequence of 2 digits. In the following 10 di...

impig33 2019-08-21 17:16 评论0 收藏0
【7 kyu】Descending Order

摘要：若提供比较函数返回值返回值不变返回值交换位置升序排列后，再利用反序将字符串转换为可选参数，表示进制。规定使用，但是并不是所有的浏览器都遵循这个规定。因此，永远都要明确给出参数的值。若传入的字符串中含有非数字字符，将返回。原题目 Your task is to make a function that can take any non-negative integer as a ar...

ls0609 2019-08-21 16:49 评论0 收藏0
【7 kyu】Sum of two lowest positive integers

摘要：原题目题目有一个不少于四个元素的数组，计算其中两个最小值的和。对比我写的方法比较常规，中采用了的解构赋值和箭头函数原题目 Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty ...

fjcgreat 2019-08-21 16:49 评论0 收藏0