给定一个整数序列作为数组,通过从数组中删除不超过一个元素来确定是否可能获得严格递增的序列。
示例
对于序列[1, 3, 2, 1]
,输出应该是:
almostIncreasingSequence(sequence) = false;
这个数组中没有一个元素可以删除以获得严格递增的序列。
对于序列[1, 3, 2]
,输出应该是:
almostIncreasingSequence(sequence) = true.
您可以从数组中删除3以获得严格递增的序列[1,2]。或者,可以删除2以获得严格递增序列[1,3]。
我的代码:
def almostIncreasingSequence(sequence):
c= 0
for i in range(len(sequence)-1):
if sequence[i]>=sequence[i+1]:
c +=1
return c<1
但它不能通过所有的测试。
input: [1, 3, 2]
Output:false
Expected Output:true
Input: [10, 1, 2, 3, 4, 5]
Output: false
Expected Output: true
Input: [0, -2, 5, 6]
Output: false
Expected Output: true
input: [1, 1]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 3, 6]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 99, 5, 6]
Output: false
Expected Output: true
您的适度算法在这里失败的原因(除了缺少的“=”作为回报)是,它只是计算大于下一个的元素,如果该计数大于1,则返回结果。
其中重要的是在每次从列表中删除一个元素后查看列表,并确认它仍然是一个排序的列表。
我在这方面的尝试非常短暂,适用于所有场景。它不满足练习中单独设置的最后一个隐藏测试集的时间限制。
正如问题名称所暗示的,我直接想将列表与其排序版本进行比较,并在稍后处理“几乎”的情况—从而拥有almostIncreasingSequence。i、 e.:
但正如问题所说:
在迭代过程中,我一次删除一个元素,开始可视化列表,并检查列表的其余部分是否是其自身的排序版本。因此我想到:
在这里,我可以看到,如果这个条件对完整的列表是真的,那么我们有什么是必需的-一个almostIncreasingSequence!所以我用这种方式完成了我的代码:
这个解决方案在[1,1,1,2,3]这样的列表中仍然失败。 正如@rory daulton在他的评论中指出的,在这个问题中,我们需要区分“排序”和“递增序列”。当测试[1,1,1,2,3]被排序时,它按照问题中的要求处于递增序列上。为了处理这个问题,下面是最后一个代码,添加了一行条件来检查连续的相同数字:
由于这仍然没有通过最后一个测试的执行时间限制(列表必须很大),我仍然在寻找是否有办法优化我的解决方案。
这是我的。希望你觉得这有帮助:
你的算法太简单了。您有一个正确的想法,检查前一个元素小于后一个元素但需要更多元素的连续元素对。
制作一个例程
first_bad_pair(sequence)
,它检查所有元素对的顺序列表。如果是,则返回值-1
。否则,返回前面元素的索引:这将是一个从0
到n-2
的值。然后一个可行的算法就是检查原始列表。如果可以的话,可以,但是如果不能的话,试着删除前面或者后面的有问题的元素。如果其中任何一个工作,好,否则就不好。我可以想到其他算法,但这一个似乎是最直接的。如果您不喜欢通过组合原始列表的两个片段而生成的最多两个临时列表,则可以使用更多的
if
语句在原始列表中进行比较来完成等效的操作。下面是通过您显示的所有测试的Python代码。
如果您确实想避免这些临时列表,这里还有其他代码有一个更复杂的对检查例程。
这是我做的测试。
相关问题 更多 >
编程相关推荐