bigger is greater

题目：

Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria: (1)It must be greater than the original word. (2)It must be the smallest word that meets the first condition.Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer.

附上链接：Bigger is Greater

初步逻辑

这个逻辑很难用语言描述，直接把我的实现代码贴上来

def biggerIsGreater(s):

    i = 1

    j = i + 1

    while j > len(w) or w[-j] >= w[-i]:

        if j > len(w):

            i += 1

            j = i + 1

            if j > len(w):

                return 'no answer'

        else:

            j += 1

    else:

        l = list(s)

        l.insert(-j, s[-i])

        l.pop(-i)

        s = ''.join(l)

        s = ''.join((lambda x, y: x + y)(list(s[-j + 1:]), list(s[:-j + 1])))

        return s

逻辑本身没有问题，但是运行下去会发现，有三个例子是超时的

优质逻辑

发现了这个问题后，我却找不到解决办法，因为以往的超时都是由多重循环嵌套引起的，可这次明明只有一层循环，依然发生了超时的现象

于是，借助网站万能的Discussion，发现了其他人的一个很简洁的代码，如下

def biggerIsGreater(s):

    for i in range(len(s) - 1)[::-1]:

        if s[i] < s[i + 1]:

            for j in range(i + 1, len(s))[::-1]:

                if s[i] < s[j]:

                    lis = list(s)

                    lis[i], lis[j] = lis[j], lis[i]

                    return "".join(lis[:i + 1] + lis[i + 1:][::-1])

    return 'no answer'

可它明明是两层嵌套循环，为什么要比我的运行的快呢。。。

初步感觉是因为我else里面的列表、字符串的操作占用了大量的时间，可是具体原因还是不清楚，有清楚的大佬愿意给我解释一下吗

巴特西

bigger is greater

题目：

初步逻辑

优质逻辑

最新文章

热门文章