c

codeye

V1

2022/11/08阅读:17主题:默认主题

波浪排序

任务概述

一串n个不等式符号;即:>或< n+1个不同的整数。 你的目标是将所有的n+1个整数放在由给定的n个不等式符号所产生的可用位置上,以便整个表达式为真。

为了清楚起见,如果你有n个不等式符号,那么在字符串的 "内部 "有n-1个位置,你可以放置n-1个不同的整数,然后在字符串的 "外部 "还有2个位置--一个在开头,另一个在结尾,你可以再放置2个整数。这就是为什么你总是被赋予n个不等式符号和n+1个不同的整数。

_ < _ > _ > _ < _ < _ > _ < _ > _

因此,在上面的插图中,我们有n=8个不等式符号,和n+1=9个空位,用_表示,可以放置n+1=9个整数。

输入

ineqs = 一串没有空格的n个不等式符号,例如:'<<<<'

ints = 一个由n+1个不同的整数组成的元组/向量(取决于语言) 例如 (12, 9, 31, 47, 15, 11, 22, 8, 4)

性能要求。在随机测试中,将使用高达n=10000的值。

输出

你将返回一个由n+1个整数组成的数组,按照你想把它们插入n+1个不平等位置的顺序。

然后,测试将把你的解决方案的元素插入不等式中,并检查所产生的表达式是否被评估为真。

测试还将检查你是否已经使用了输入的所有整数。

例如,n=8个不等式和n+1=9个整数的情况下

ineqs = '<<<<<')

ints = (12, 9, 31, 47, 15, 11, 22, 8, 4)

对于这些输入,你要返回的有效解决方案是--例如--数组。


[8, 31, 4, 9, 47, 12, 22, 11, 15]

因为由此产生的布尔表达式。

8 < 31 > 4 < 9 < 47 > 12 < 22 > 11 < 15 确实会评估为真。

基础知识算法

排名第一的写法令人惊讶,严格讲可以精简到一行!

def interweave(ineqs, ints):
    arr = sorted(ints)
    return  [arr.pop([-1, 0][a == '<']) for a in ineqs] + arr

思路

是遇到 < 小于,就取低到高排序的最左边的数; 遇到 > 大于,就取排序好的数列最右端的数; 这样做确实机巧,Respect

大喵很少采用 pop(),用在此处,颇有找到用武之地的感慨!

分类:

后端

标签:

后端

作者介绍

c
codeye
V1