chenpaopao

解法：（参考了官方 解法）

1、哈希表

对于「前言」中提到的第一种做法：

我们可以将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中。

仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是[1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：

我们对数组进行遍历，对于遍历到的数 xx，如果它在[1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：

• 我们将数组中所有小于等于 0 的数修改为N+1；
• 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 |x| in [1, N]∣x∣∈[1,N]，那么我们给数组中的第 |x| – 1个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。

def firstMissingPositive(nums):
        lens=len(nums)
        for i in range(lens):
            if nums[i]<0:
                nums[i]=lens+1

        for i in range(lens):
            num = abs(nums[i])
            if num <= lens:
                nums[num - 1] = -abs(nums[num - 1])
        print(nums)
        for i in range(lens):
            if nums[i]>=0:
                return i+1
        return lens+1 

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

• 1 <= n <= 30

代码：

# @lc app=leetcode.cn id=38 lang=python3
#
# [38] 外观数列
#

# @lc code=start
from unittest import result


class Solution:
    def countAndSay(self, n: int) -> str:
      def subAndSay(n):
        if n==1 :
            return "1*"
        string = subAndSay(n-1)
        m=1
        result=""
        for i in range(len(string)-1):
            if string[i]==string[i+1]:
                m=m+1
            else: 
                result+=str(m)+string[i]
                m=1
        result+="*"
        return result
      return subAndSay(n)[:-1]

        

结果：

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

思路：回溯法：通俗理解就是如果board[i][j]=VALUE不满足条件就回退到上一步的选择，重新选择。

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

代码实现：（递归）【参考了解题思路】

# [37] 解数独
#
#回溯法
"""
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。

"""
# @lc code=start
class Solution:
    def solveSudoku(self, board)->None:
        """
        Do not return anything, modify board in-place instead.
        """
        #判断改行、列、3*3小格子是否满足数独规则：

        def isRowSafe(row,value):
            for i in range(9):
                if board[row][i]==value:
                    return False
            return True
    
        def isColSafe(col,value):
            for i in range(9):
                if board[i][col]==value:
                    return False
            return True
        
        def isSmallboxSafe(row,col,value):
            inirow=row//3*3
            inicol=col//3*3
            for i in range(3):
                for j in range(3):
                    if board[i+inirow][j+inicol]==value:
                        return False  
            return True
        #判断该位置是否可行
        def isSafe(row,col,value):
            return isRowSafe(row,value) and isColSafe(col,value) and isSmallboxSafe(row,col,value)                 
        #解数独，结束条件
        def solve(row,col):
            if row==8 and col ==9:
                return True
            if col ==9:
                col=0
                row+=1
            if board[row][col]!=".":
                return solve(row,col+1)
            for i in range(1,10):
                if isSafe(row,col,str(i)):
                    i=str(i)
                    board[row][col] = i
                    if solve(row, col+1):
                        return board
           #回溯到上一个状态（也就是前一个solve）
            board[row][col]="."
            return False
        solve(0,0)
        print(board)

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

#思路：遍历一遍数组，就要完成该目标，行和列简单，对于方格：[int(i/3)][int(j/3)]
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 1、先生成三个数组
        rows = [[0] * 9 for _ in range(9)]
        columns = [[0] * 9 for _ in range(9)]
        subboxes = [[[0] * 9 for _ in range(3)] for _ in range(3)]
        # 遍历行
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c != '.':
                    c = int(c) - 1
                    rows[i][c] += 1
                    columns[j][c] += 1
                    subboxes[int(i/3)][int(j/3)][c] += 1
                    if rows[i][c] > 1 or columns[j][c]>1 or subboxes[int(i/3)][int(j/3)][c]>1:
                        return False
        return True

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为无重复元素的升序排列数组
• -104 <= target <= 104

思路 ： 时间复杂度为 O(log n) 的算法 首先想到的是二分查找，递归，每次查找mid值，如果大于mid，在右边寻找，否则在左边寻找。

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

# @lc code=start
#思路：二分查找
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binarySearch (arr, l, r, x): 
  
            # 基本判断
            if r >= l: 
  
                mid = int(l + (r - l)/2)

  
            # 元素整好的中间位置
                if arr[mid] == x: 
                    return mid 
          
        # 元素小于中间位置的元素，只需要再比较左边的元素
                elif arr[mid] > x: 
                    return binarySearch(arr, l, mid-1, x) 
  
        # 元素大于中间位置的元素，只需要再比较右边的元素
                else: 
                    return binarySearch(arr, mid+1, r, x) 
  
            else: 
        # 不存在
                return r+1
        return binarySearch(nums,0, len(nums)-1,target )
# @lc code=end

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

直接给出代码：

# @lc code=start
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        j=len(nums)-1
        i=0
        while i<=j:
            if nums[i]!=target:
                i=i+1
            if nums[j]!=target:
                j=j-1
            if nums[j]==target and nums[i]==target:
                return [i,j]
        return [-1,-1]

# @lc code=end

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

#
# @lc app=leetcode.cn id=26 lang=python3
#
# [26] 删除有序数组中的重复项
#

# @lc code=start
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums.append(10**4+1)
        j=0
        for i in range(len(nums)-1):
            if nums[i]==nums[i+1]:
                continue
            else:
                nums[j]=nums[i]
                j=j+1
        return j
# @lc code=end

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

思路：记录每个打破成对括号规则的位置，那么最长的符合要求的长度就在这些位置之间 。

# @lc code=start
class Solution:
    def longestValidParentheses(self,s: str) -> int:
        if s=="":
            return 0
        length = len(s)
        rev,div=list(),list()
        i=0
        lens=0
        result=0
        while i<=length-1:
            lens=len(rev)
            if s[i]=="(": 
                rev.append(s[i])
                div.append(i)
                

            elif lens!=0 and s[i]==")": 
                rev.pop()
                #result=mid if mid  >=result else result
                div.pop()
                
            else:
                div.append(i)
                #result=mid if mid  >=result else result
            i=i+1   

        
        res=list()
        if div.count(length)==0:
            div.append(length)
        res.append(div[0])
        if len(div)>1:
            for i in range(1,len(div)):
                res.append(div[i]-div[i-1]-1)

        return max(res) if max(res)>result else result
            

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

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

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

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：

输入：nums = [1]
输出：[1]

第一次做法：思路，找到 需要交换的nums[i] 和nums[j]，交换后，对nums[i+1:]进行排序即可

# @lc code=start



class Solution:
    def InsertSort(self,lst):
        n=len(lst)
        if n<=1:
            return lst
        for i in range(1,n):
            j=i
            target=lst[i]            #每次循环的一个待插入的数
            while j>0 and target<lst[j-1]:       #比较、后移，给target腾位置
                lst[j]=lst[j-1]
                j=j-1
            lst[j]=target            #把target插到空位
        return lst
    
    def nextPermutation(self,nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
            
        m=j=len(nums)-1
        x=-1
        for i in range(len(nums)-2,-1,-1):
            re=100
            l=j
            for h in range(j,m+1):
              
              if 0<nums[h]-nums[i]<re:
                  l=h
                  re=nums[h]-nums[i]
            print(l)
            
            if nums[i]<nums[l]:
                rev=nums[l]
                nums[l]=nums[i]
                nums[i+1:]=self.InsertSort(nums[i+1:])
                nums[i]=rev
                return nums
            else: 
                j=j-1
        n=0
        while n<m:
            rev=nums[m]
            nums[m]=nums[n]
            nums[n]=rev
            n+=1
            m-=1
        return nums