Python: 每日一题 55

马上要放假了，今日再来一题。Sixpy说题目越来越简单，那就出个难点的(4kyu)。

有一个数列u，使得u符合以下规则：
1、u的第一个数字是1.
2、对于u中的每一个x，都有y=2*x+1 和z=3*x+1，且y和z都在u中。
3、u中没有其他数字。

例如:

u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

复制代码

1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13
....

要求：给出函数dbl_linear(n)，  返回按顺序排列的u[n]。
例如： dlb_linear(10) 返回  22.
注意：请考虑效率问题（1<n<100000）

jerry已经把答案做出来了，我就先把答案放出来吧。我自己写的答案在6楼，这里提供的是一个网络上面比较高效的答案。

from collections import deque
def dbl_linear1(n):
h = 1
cnt = 0
q2, q3 = deque([]), deque([])
while True:
if (cnt >= n):
return h
q2.append(2 * h + 1)
q3.append(3 * h + 1)
h = min(q2[0], q3[0])
if h == q2[0]: h = q2.popleft()
if h == q3[0]: h = q3.popleft()
cnt += 1