LeetCode 31-35 记录

31

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

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1:
            return
        if nums[-1] > nums[-2]:
            nums[-1], nums[-2] = nums[-2], nums[-1]
            return
        i = len(nums) - 1
        while nums[i - 1] >= nums[i] and i >= 0:
            i -= 1
        if i == 0:
            nums.sort()
            return
        left = i - 1
        nums[i:] = sorted(nums[i:])
        for j in range(i, len(nums)):
            if nums[j] > nums[left]:
                nums[j], nums[left] = nums[left], nums[j]
                break
        nums[i:] = sorted(nums[i:])

if __name__ == '__main__':
    solu = Solution()
    nums = [1, 2, 3, 4, 5]
    nums = [2, 1, 4, 5, 3]
    nums = [5, 4, 3, 2, 1]
    solu.nextPermutation(nums)
    print(nums)

思路其实是比较简单的，只是一开始想要暴力解决，结果反而误入歧途，不过，也因此重新复习了一下如何生成一个列表的全排列。或许，有时间研究一下 itertool 中的库函数是一个不错的注意。

说回思路，就是判断列表最后两个元素的大小，如果是正序，直接交换两个元素即可，如果不是，则一直往前寻找到第一个打破秩序的数字，然后将这个元素和后面的列表切片中刚好大于这个数字的元素交换，最后，再将后面的部分排个序即可。

32

https://leetcode.com/problems/longest-valid-parentheses/

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        res = []
        stack = []
        for i in range(len(s)):
            if stack and s[i] == ')':
                res.append(stack.pop())
                res.append(i)
            if s[i] == '(':
                stack.append(i)
        res.sort()
        ans = 0
        if len(res) <= 1:
            return ans
        ans = 1
        index = 0
        tmp_res = 1
        while index < len(res) - 1:
            if res[index + 1] == res[index] + 1:
                tmp_res += 1
            else:
                tmp_res = 1
                index += 1
                continue
            if tmp_res > ans:
                ans = tmp_res
            index += 1
        return ans

if __name__ == '__main__':
    solu = Solution()
    s = ')(()())'
    Output = solu.longestValidParentheses(s)
    print(Output)

33

https://leetcode.com/problems/search-in-rotated-sorted-array/

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        if len(nums) == 1:
            return 0 if nums[0] == target else -1
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:  # 如果中间值等于目标值，直接返回
                return mid
            elif nums[mid] > nums[right]:  # 右边有序
                if nums[left] <= target <= nums[mid]:  # 如果目标值在左边有序的区间内，则右边查找
                    right = mid
                else:  # 否则，左边查找
                    left = mid + 1
            elif nums[mid] < nums[right]:  # 左边有序
                if nums[mid] <= target <= nums[right]:  # 如果目标值在右边有序的区间内，则左边查找
                    left = mid + 1
                else:  # 否则，右边查找
                    right = mid
            else:  # nums[mid] == nums[right]
                right -= 1
        # 如果目标值等于中间值，则返回中间值的下标，否则返回-1
        return left if nums[left] == target else -1


solu = Solution()
print(solu.search([4, 5, 6, 7, 0, 1, 2], 0))  # 4

依然是二分查找，只不过判断条件比普通的二分查找多了一些。

34