小编Pet*_*ter的帖子

假设我想在1到N的范围内找到n个不同的数字,因此它们的和等于N.例如

n = 3, N = 10: the numbers will be (2, 3, 5);
n = 4, N = 10: the numbers will be (1, 2, 3, 4).

虽然找出这个问题的所有可能组合将需要指数时间,但我正在寻找"最小"组合,即最大数字是最小的.例如,

在这种情况下n = 4, and N = 12,两者都(6, 3, 2, 1) and (5, 4, 2, 1)可以解决,但我只对此感兴趣(5, 4, 2, 1).

对于这个问题,是否会有一个具有更好时间复杂度的算法？我听说过对数合并,但不知道如何在这里应用.

如果需要指明问题的任何细节,请告诉我.总是,任何帮助将非常感激.

假设我有一串小写字母,例如

'ablccmdnneofffpg'

我的目标是找到这个字符串中连续数字的最长序列,在这种情况下是:

'abcdefg'

直观的尝试是在每个字母周围找到循环并从该字母开始获得最长的序列.一种可能的解决方案是

longest_length = 0
start = None
current_start = 0
while current_start < len(word) - longest_length:
    current_length = 1
    last_in_sequence = ord(word[current_start])
    for i in range(current_start + 1, len(word)):
        if ord(word[i]) - last_in_sequence == 1:
            current_length += 1
            last_in_sequence = ord(word[i])
    if current_length > longest_length:
        longest_length = current_length
        start = current_start
    while (current_start < len(word) - 1 and
           ord(word[current_start + 1]) - ord(word[current_start]) == 1):
        current_start += 1
    current_start += 1

有没有其他方法可以用更少的线来解决问题,甚至使用一些pythonic方法？