31. Next Permutation

https://leetcode.com/problems/next-permutation/

solution

• Find the breakpoint from the end which breaks the non-increasing sequence. [1, 3, 5, 4, 2] -> 3

• Traverse from end in right part and find the first element greater than breakpoint. [1, 4, 5, 3, 2] -> 34互换

• Reverse the right part. [1, 4, 2, 3, 5]

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 如果第一部分也用 for i in range(len(nums) -1, 0, -1)的写法，会导致单元素的list为空, 或者初始化一个i=1
        i = len(nums) - 1
        while i > 0:
            if nums[i-1] < nums[i]:
                break
            i -= 1

        pivot = i - 1
        if pivot == -1:
            nums.reverse()
            return

        for j in range(len(nums) - 1, pivot, -1):
            if nums[j] > nums[pivot]:
                nums[j], nums[pivot] = nums[pivot], nums[j]
                break

        nums[pivot+1:] = reversed(nums[pivot+1:])

时间复杂度：O(n) 空间复杂度：O(1)

follow up-多步翻转法

189. Rotate Array

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

• in-place

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        lens = len(nums)
        if k == lens:
            return
        k = k % lens
        self.reverse(nums, 0, lens-1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, lens-1)

    def reverse(self, nums, l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

179. Largest Number

剑指Offer 45: 把数组排成最小的数

import functools

class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        num = list(map(str, numbers))
        cmp = lambda a, b: 1 if a + b > b + a else -1
        num = sorted(num, key=functools.cmp_to_key(cmp))
        return ''.join(num)

186 Reverse Words in a String II

24. Swap Nodes in Pairs

556. Next Greater Element III