题目名称：两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答

直接暴力两层循环搜索了，当然花时间也很多…

1
2
3
4
5
6
7
8
9
10
11
class Solution:

  def twoSum(self, nums: List[int], target: int) -> List[int]:

    for i in range(len(nums)):

      for j in range(len(nums)-1,i,-1):

        if nums[i] + nums[j] == target:

          return(i,j)

执行用时：6212 ms, 在所有 Python3 提交中击败了11.20%的用户

内存消耗：14.6 MB, 在所有 Python3 提交中击败了13.41%的用户

复杂度O(N^2)

23333，看一下别人的简单方法。

第一个思路使用nums.index(num2)函数，其中num2=target-num1.

1
2
3
4
5
6
def twoSum(nums, target):
    hashmap={}
    for i,num in enumerate(nums):
        if hashmap.get(target - num) is not None:
            return [i,hashmap.get(target - num)]
        hashmap[num] = i #这句不能放在if语句之前，解决list中有重复值或target-num=num的情况

其实本质上还是构建索引字典的思路，刷题时要放开思路了。

两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l = ListNode(None)
        j = 0
        while l1 or l2 or j:
            sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + j
            l.next = ListNode(sum % 10)
            j = sum // 10
            l = l.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return head.next

原理很简单，需要注意的是：

  • sum 相加时要判断l1和l2是否存在值
  • 到下一节点时要判断是否存在

无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解答

我自己的解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        longth = 0
        for i in range(len(s)):
            dirct = []
            dirct.append(s[i])
            ls = 1
            for j in range(i + 1, len(s)):
                if s[j] in dirct:
                    break
                else:
                    dirct.append(s[j])
                    ls += 1
                    continue
            if ls > longth:
                longth = ls
        return longth

哈哈哈，还是很c的写法。。

O（n^2）

image-20200711010805278

看看别人的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

思路差不多啊。。。为什么快这么多

寻找两个正序数组的中位数

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1：

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例：

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解答

很自然现到归并为一个数组，在找中位数，但是时间复杂度肯定是$O(m+n)$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        i = j = k = 0;
        numssum = []
        while i < len(nums1) or j < len(nums2):
            if i >= len(nums1):
                for z in range(j,len(nums2)):
                    numssum.append(nums2[z])
                    k+=1
                break
            elif j>=len(nums2):
                for z in range(i,len(nums1)):
                    numssum.append(nums1[z])
                    k+=1
                break
            else:
                if nums1[i] <= nums2[j]:
                    numssum.append(nums1[i])
                    i+=1
                else:
                    numssum.append(nums2[j])
                    j+=1
                k+=1
        #print(len(numssum))
        if len(numssum)%2 == 0:
            return((numssum[len(numssum)//2-1]+numssum[len(numssum)//2])/2)
        else:
            return numssum[len(numssum)//2]

最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

解答

开始用的最简单的方法超时了………O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    # 如果相等 首尾肯定一样
    def longestPalindrome(self, s: str) -> str:
        max_len = 0
        max_str = ''
        if len(s) == 0:
            return ''
        if len(s) == 1:
            return s
        for i in range(len(s)-1):
            for j in range(i+1,len(s)):
                if s[i] == s[j]:
                    a,b = i,j
                    while(a <= b):
                        if s[a] != s[b]:
                            break
                        else:
                            a += 1
                            b -= 1
                    if a >= b:
                        if(max_len < j - i + 1):
                            max_len = j - i + 1
                            #print(i,j)
                            max_str = s[i:j+1]
        if max_len != 0:
            return max_str
        else:
            return s[0]

然后用的动态规划 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 子串的长度 lens
        for lens in range(n):
            # 子串的起始位置 i，最长位置i+lens
            for i in range(n):
                j = i + lens
                if j >= len(s):
                    break
                if lens == 0:
                    dp[i][j] = True
                elif lens == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and lens + 1 > len(ans):
                    ans = s[i:j + 1]
        return ans

核心思想是如果一个字符串是回文串，那么去掉首尾两个字符仍然是回文串。例如‘abcba’是回文串那么‘bcb’，‘c’也是字符串。则动态规划方程是：

现在才发现leecode的解答有视频的，想想不能为了刷题而刷题，要搞懂，明天要补一下。

Z字形变换

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3
输出: “LCIRETOESIIGEDHN”
示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:

L D R
E O E I I
E C I H N
T S G

解答

直接确定每个字符在哪行，然后按行输出就可以呢…找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    #确定每个元素在哪一行，再按行输出.......
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 2 or numRows >= len(s) :
            return s
        out = ['']*numRows
        j,k = 0,1
        for i in s:
            out[j] += i
            j += k
            if j==0 or j == numRows -1:
                k = -k
        return "".join(out)

盛最多水的容器

题目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

1
2
输入：[1,8,6,2,5,4,8,3,7]
输出：49

解答

先放这儿 明天看了官方解答来填坑

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left,right = 0,len(height)-1
        max_area = 0
        while left < right:
            area = height[left if height[left] <= height[right] else right] * (right - left)
            max_area = area if area >= max_area else max_area
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return max_area

整数转罗马数字

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: “III”

示例 2:

输入: 4
输出: “IV”

示例 3:

输入: 9
输出: “IX”

示例 4:

输入: 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答

比较简单。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def intToRoman(self, num: int) -> str:
        a = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        r = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']
        lens = len(a)
        roma = ''
        for i in range(lens):
            sums = num // a[i]
            num = num % a[i]
            roma = roma+(r[i]*sums)
        return roma
if __name__ == "__main__":
    a = Solution
    print(a.intToRoman(a,1994))

罗马数字转整数

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

示例 3:

1
2
输入: "IX"
输出: 9

示例 4:

1
2
3
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答

比较简单，建立个词典。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def romanToInt(self, s: str) -> int:
        a = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        r = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']
        roma = []
        i2r = {}
        sum = 0
        for i in range(len(a)):
            i2r[r[i]] = a[i]
        for ss in s:
            roma.append(ss)
        for i in range(len(roma)-1):
            if i2r[roma[i]] >= i2r[roma[i+1]]:
                sum += i2r[roma[i]]
            else:
                sum -= i2r[roma[i]]
        sum += i2r[roma[-1]]
        return sum
            

if __name__ == "__main__":
    a = Solution
    print(a.romanToInt(a,"MCMXCIV"))

三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

解答

刚开始做的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        sums = []
        for i in range(len(nums)):
            a = 0 - nums[i]
            for j in range(i+1,len(nums)):
                b = a - nums[j]
                try:
                    k = nums.index(b,j+1,len(nums))
                except ValueError:
                    continue
                else:
                    if k > i and k > j: 
                        c = [nums[i],nums[j],nums[k]]
                        if c not in sums:
                            sums.append(c)
        return sums

超时了，后来仿照答案写的双指针也超时了，竟然是因为 not in 查找的时候耗时太多了，看来python自带的函数也不能乱用

最终解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        sums = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            a = 0 - nums[i]
            k = len(nums) - 1
            for j in range(i + 1,len(nums)):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                while j < k and nums[j] + nums[k] > a :
                    k -= 1
                if j == k:
                    break
                if nums[j] + nums[k] == a:
                    c = [nums[i],nums[j],nums[k]]
                    #if c not in sums:
                    sums.append(c)
        return sums

if __name__ == "__main__":
    a = Solution
    nums = [3,0,-2,-1,1,2]
    nums.sort()
    print(nums)
    print(a.threeSum(a,nums))

电话号码的数字组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例:

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解答

深度搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:

    def letterCombinations(self, digits: str) -> List[str]:
        number_letter = {'2': ['a', 'b', 'c'],
                         '3': ['d', 'e', 'f'],
                         '4': ['g', 'h', 'i'],
                         '5': ['j', 'k', 'l'],
                         '6': ['m', 'n', 'o'],
                         '7': ['p', 'q', 'r', 's'],
                         '8': ['t', 'u', 'v'],
                         '9': ['w', 'x', 'y', 'z']}
        sums = []
        def dfs(begin,digit):
            if len(digit) == 0:
                sums.append(begin)
            else:
                for i in number_letter[digit[0]]:
                    dfs(begin+i,digit[1:])
        if digits:
            dfs('',digits)
        return sums

不大熟悉python的面向对象..

后来看了别人的解答有了更简单的方法，其实也是深搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:

    def letterCombinations(self, digits: str) -> List[str]:
        sum = ['']
        number_letter = {'2':['a','b','c'],
                         '3':['d','e','f'],
                         '4':['g','h','i'],
                         '5': ['j', 'k', 'l'],
                         '6': ['m', 'n', 'o'],
                         '7': ['p', 'q', 'r', 's'],
                         '8': ['t', 'u', 'v'],
                         '9': ['w', 'x', 'y', 'z']}
        for i in digits:
            sum = [a + b for a in sum for b in number_letter[i]]
        return sum

删除链表的倒数第N个节点

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解答

思路很简单，双指针，一个走的快一个走得慢，相差n，快的走完时，慢的那个接上其下下个节点，就相当于删掉了倒数第n个。我的代码写的太c语言了=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        top = l = ListNode(None)
        i = 0
        j = i - n
        l1 = head
        while head:
            if j >= 0:
                l.next = ListNode(l1.val)
                #print(l1.val)
                l1 = l1.next
                l = l.next
            i += 1
            j += 1
            head = head.next
        l1 = l1.next
        while l1:
            l.next = ListNode(l1.val)
            l1 = l1.next
            l = l.next
        return top.next

看一下写的简单的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head:
            return head
        dummy = l = r =ListNode(10086)
        dummy.next = head
        for i in range(n):
            r = r.next
        while r.next is not None:
            r = r.next
            l = l.next
        l.next = l.next.next
        return dummy.next

有效的括号

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解答

刚开始没读懂题意。

因为题目说的只有括号没有其他内容，所以字符串如果是正确的话，一定至少包含一对‘[]’,‘()’或‘{}’，所以我们不断的删除这样成对的括号，如果最后结果是空字符串，那么这个字符串就是正确的，否则就是错误的。

当然，可以用栈来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        return s == ''


if __name__ == "__main__":
    a = Solution
    s = "{[]}"
    print(a.isValid(a, s))

合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解答

数据结构经典题目，建立新链表，分别把小的节点放入新链表，最后直接连上未空的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l =ListNode(None)
        while l1 and l2:
            if(l1.val <= l2.val):
                l.next = ListNode(l1.val)
                l1 = l1.next
            else:
                l.next = ListNode(l2.val)
                l2 = l2.next
            l = l.next
        if l1:
            l.next = l1
        else:
            l.next = l2
        return head.next

括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

1
2
3
4
5
6
7
8
9
10
> 输入：n = 3
> 输出：[
>        "((()))",
>        "(()())",
>        "(())()",
>        "()(())",
>        "()()()"
>      ]


解答

深度搜索，当左括号数小于右括号数时，添加左括号；

当左右括号数达到题目给定的n时输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(s:str,left:int,right:int):
            if left > n :
                return
            if left < right:
                return
            if left == n and right == n:
                res.append(s)
            dfs(s+'(',left+1,right)
            dfs(s+')',left,right+1)

        dfs('',0,0)
        #return list(set(res))
        return res



if __name__ == "__main__":
    a = Solution
    n = 5

    print(a.generateParenthesis(a,n))

下一个排列

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解答

  • 从后到左遍历，找到第一个nums[i] > nums[i-1]的情况
    • 如果不存在这种状况，直接把list升序排序。
    • 如果存在，将nums[i:]排序，在nums[i:]中找到第一个大于nums[i-1]的数，并与其交换顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        13542
        13245
        """
        for i in range(len(nums)-1,0,-1):
            if nums[i] > nums[i-1]:
                nums[i:] = sorted(nums[i:])
                for j in range(i,len(nums)):
                    if nums[j] > nums[i-1]:
                        nums[i-1],nums[j] = nums[j],nums[i-1]
                        break
                return
        nums.sort()

if __name__ == "__main__":
    a = Solution
    nums = [1,2,3]
    a.nextPermutation(a,nums)
    print(nums)