我在做Google Foobar挑战，但在接下来的挑战中时间不够，我想看看我做错了什么。
挑战
作为lambda指挥官的私人助理，您被分配了配置lambchop末日装置轴向齿轮的任务。这应该很简单-只需添加齿轮，以创建适当的旋转比。但问题是，由于羊羔的布局和支撑羊羔的梁和管的复杂系统，支撑齿轮的销子固定到位。
兰姆夏普的工程师已经给了你一份清单，列出了沿着各种支撑梁的一组木桩的位置。您需要在每个销子上放置一个齿轮（否则齿轮会与未占用的销子碰撞）。工程师们储备了大量不同尺寸的齿轮，所以你可以选择任何尺寸的齿轮，从半径1开始。你的目标是建立一个系统，在这个系统中，不管方向如何，最后一个齿轮的转速是第一个齿轮的两倍（以每分钟转数或每分钟转数表示）。每个齿轮（最后一个除外）接触并将下一个销轴上的齿轮向右转动。
给定一个不同的正整数列表，名为peg s，代表沿着支撑梁的每个peg的位置，写一个函数应答（pegs），如果有解，返回两个正整数a和b的列表，表示i中第一个齿轮半径的分子和分母。它是实现上述目标的最简单形式，即半径=A/B。比值A/B应大于或等于1。并非所有的支持配置都必须能够创建适当的旋转比率，因此如果任务不可能完成，函数应答（PEGS）应该返回列表[-1，-1]。
例如，如果销子放置在[4，30，50]处，则第一个齿轮的半径为12，第二个齿轮的半径为14，最后一个齿轮的半径为6。因此，最后一个齿轮的旋转速度是第一个齿轮的两倍。在这种情况下，pegs将是[4，30，50]，而answer（pegs）将返回[12，1]。
列表标桩将按升序排序，包含至少2个且不超过20个不同的正整数，均在1和10000之间（含1和10000）。
测试用例
Inputs:
(int list) pegs = [4, 30, 50]
Output:
(int list) [12, 1]
Inputs:
(int list) pegs = [4, 17, 50]
Output:
(int list) [-1, -1]
我目前的解决方案如下
def answer(pegs):
n = len(pegs)
g = range(n)
k = pegs[1] - pegs[0]
for i in range(0,k,2):
g[0] = i
for j in range(1,n):
g[j] = (pegs[j] - pegs[j-1]) - g[j-1]
if any(b < 1 for b in g):
continue
if 1.0*g[0]/g[-1] == 2.0:
return [g[0],1]
return [-1, -1]
我只能通过6个测试用例，现在已经没有时间了，但我很好奇正确的解决方案是什么。
最佳答案
下面是python 2.7中的工作代码，所有测试用例都是由Google传递的。这是我在写了一段时间的论文之后提出的最佳解决方案：
from fractions import Fraction
def answer(pegs):
arrLength = len(pegs)
if ((not pegs) or arrLength == 1):
return [-1,-1]
even = True if (arrLength % 2 == 0) else False
sum = (- pegs[0] + pegs[arrLength - 1]) if even else (- pegs[0] - pegs[arrLength -1])
if (arrLength > 2):
for index in xrange(1, arrLength-1):
sum += 2 * (-1)**(index+1) * pegs[index]
FirstGearRadius = Fraction(2 * (float(sum)/3 if even else sum)).limit_denominator()
#now that we have the radius of the first gear, we should again check the input array of pegs to verify that
#the pegs radius' is atleast 1.
currentRadius = FirstGearRadius
for index in xrange(0, arrLength-2):
CenterDistance = pegs[index+1] - pegs[index]
NextRadius = CenterDistance - currentRadius
if (currentRadius < 1 or NextRadius < 1):
return [-1,-1]
else:
currentRadius = NextRadius
return [FirstGearRadius.numerator, FirstGearRadius.denominator]
查看此图片了解我如何得出此代码：