当前位置: 首页>>趣味编程>>正文


平滑列表

洋葱 趣味编程 , , 去评论

问题描述

您应该编写一个程序或函数,它将non-negative整数k和排序整数列表L作为输入,并输出或返回一个平滑的列表M

M通过插入最多k整数元素,同时保持列表排序,从升序列表L创建。插入的整数应该选择为使M的最大正向差尽可能小。我们称这个最小值为”smoothness”。

列表-1 3 8 11 15的前向差异为4 5 3 4,最大正向差为5

使用2插入,2 10 15的平滑度为4,可能的输出为2 6 10 11 15,具有正向差异4 4 1 4

Input

  • non-negative整数k

  • 具有至少2个元素的上升整数列表L

Output

  • 升序整数列表M

  • 如果存在多个正确的答案,则只输出其中一个(任何一个都足够)。

  • 您的解决方案必须在计算机上解决任何示例测试用例(我将仅测试关闭情况,我有一个below-average PC)。

例子

输入(kL)=>括号中可能的输出和最大正向差(不是输出的一部分)

0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)

这是code-golf所以最短的入场胜出。

最佳解决方案

200新X-45新新200新新新200新新新200新新新200新新200新新200新新200新新200新新200

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

输入如下:

3
[2, 10, 15]

Demonstration. Test harness.

注意:当问到这个问题的时候,Pyth里面有一个小bug,用来在你内部使用rFd,我刚刚修复了。这个错误使得它不可能在你内部使用F,这绝对不是意图。

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

                               Implicit:
                               z is the number of insertions, in string form.
                               Q is the input list.
              C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
           rFd                 d = (a, b) -> range(a, b)
        %hH                    Take every H+1th element of that range
       t                       And throw out the first one.
      m                        Perform this process for each element pair
     s                         And combine the results into one list.

                               The above is a minimal set of additional elements
                               To reduce the maximal difference to H+1.

  u                     hvz    Repeat until the result stops changing, where
                               the prior result is G, H starts at 0 and
                               increases by 1 each repetition, and
                               G is initialized to eval(z)+1.
   ?               >GvzG       If not G[eval(z):], return G. In other words,
                               if the prior result was short enough, stop.
                               Also, this is always false on the initial call.
    smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.

这是一个在询问问题时与口译员合作的版本。它是28字节,工作方式完全相同:

S+Qu?smt%hHr.udC,QtQ>GvzGhvz

Demonstration.

Git commit of the appropriate version, f6b40e62

次佳解决方案

Python 2,104

def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)

尝试不同的最大增量d,从1开始计数。通过每个d在间隙中填充每对(p,x)的连续元素的间隙。如果M比配额允许的长,则转交尝试更高的d。否则,返回已添加和原始元素的列表,进行排序。

这样做在我机器上没有延迟的所有测试用例。

参考文献

注:本文内容整合自google/baidu/bing辅助翻译的英文资料结果。如果您对结果不满意,可以加入我们改善翻译效果:gxnotes#qq.com(#替换为@)。

本文由《共享笔记》整理, 博文地址: https://gxnotes.com/article/192136.html,未经允许,请勿转载。
Go