<
ARTS 第十三周
>
上一篇

ARTS 第十二周
下一篇

ARTS 第十四周
Toc
ARTS Week-13

Algorithm

31. 下一个排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
    
    如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
    
    必须原地修改,只允许使用额外常数空间。
    
    以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1

这题目非常常见,放个 GIF 方便理解:

gif

解题代码:

    class Solution:
        def nextPermutation(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            
            length = len(nums)
            if length < 2:
                return
            
            i = length - 2
            
            while i >= 0:
                if nums[i] < nums[i + 1]:
                    break
                i -= 1
            
            start = i
            if start < 0:
                nums.reverse()
                return
            
            i = start + 1
            while i < length:
                if nums[start] >= nums[i]:
                    break
                
                i += 1
            
            end = i - 1
            
            nums[start], nums[end] = nums[end], nums[start]
            tmp = nums[start + 1:]
            tmp.reverse()
            
            nums[start + 1:] = tmp

Review

《97 Things Every Programmer Should Know》- Continuous Learning

技术人是要保持不断学习的, 文章提到了很多个自学的方法。

“Technology changes fast. Don’t get left behind.”

Tip

What the f*ck Python! 🐍 中文版

这个有趣的项目意在收集 Python 中那些难以理解和反人类直觉的例子以及鲜为人知的功能特性, 并尝试讨论这些现象背后真正的原理!

Share

《如何超过大多数人》 陈皓

“在今天的中国,你基本上不用做什么,只需要不使用中国互联网,你就很自然地超过大多数人了。”

这句话真的是精髓!

Top
Foot