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 = 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

        # python list 可以这样局部更新
        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

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        str_num = str(n)
        if len(str_num) <= 1:
            return -1

        i = len(str_num) - 1
        while i > 0:
            if str_num[i-1] >= str_num[i]:
                i -= 1
            else:
                break

        if i == 0:
            return -1

        pivot = i - 1
        j = len(str_num) - 1
        str_num_list = list(str_num)
        while j >= i - 1:
            if str_num[j] > str_num[pivot]:
                str_num_list[j], str_num_list[pivot] = str_num_list[pivot], str_num_list[j]
                break
            else:
                j -= 1

        str_num_list[pivot+1:] = reversed(str_num_list[pivot+1:])
        res = int(''.join(str_num_list))
        if res > 2**31 - 1:
            return -1
        return res