作者： chenpaopao

给定一个正整数 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

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹,  2³¹ − 1]。本题中，如果除法结果溢出，则返回 2³¹ − 1。

思路：

一开始打算用 减法实现，但会超时，因为每次都是dividend-divisor，步子很小，导致对于一个大数-小数，很耗时，因此采用 步长每次*2，每次都是 dividend-divisor ， divisor =2* divisor，如果 dividend-2divisor <0,那么 步长在变为最初的大小。

# [29] 两数相除
#

# @lc code=start
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        n,m=dividend,divisor
        MAX=2**31-1
        MIN=0-2**31
        dividend=abs(dividend)
        divisor=abs(divisor)

        y=divisor
        i=1
        re=0
        while i>0:
            x=dividend-divisor
            if i==1 and x<0:
                print(re)
                break

            if x>0:
                dividend=x
                divisor+=divisor
                re=re+i
                i+=i
        


            elif x==0:
                re=re+i
                print(re)
                break
            else:
                i=1
                divisor=y

        if (m>0 and n>0) or (m<0 and n<0):
            return min(re,MAX)
        else:return max(0-re,MIN)



# @lc code=end