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

pakolagij 發布于2019-08-21 16:53 / 2767人閱讀

摘要：原題目題目有一個隊列，排到的人，再次排到隊尾，并將自己變成雙倍。個人也覺得減法更一點

原題目

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 一點 ?

GPU云服務器云服務器 kyu cola who dr who

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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