leetcode 31-40

31.下一个排列

给出一组由正整数构成的序列，要求重排得到字典序中下一个更大的排列，如不存在则排成最小排列，要求原地修改。

class Solution:        
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        def reverse(nums, L, R):
            while L < R:
                nums[L], nums[R] = nums[R], nums[L]
                L += 1
                R -= 1
        
        x = len(nums)-2
        while x >= 0 and nums[x] >= nums[x+1]:
            x -= 1
        if x < 0:
            reverse(nums, 0, len(nums)-1)
        else:
            y = len(nums)-1
            while nums[y] <= nums[x]:
                y -= 1
            nums[x], nums[y] = nums[y], nums[x]
            reverse(nums, x+1, len(nums)-1)

32.最长有效括号

给定一个只包含'('和')'的字符串，找出最长的包含有效括号的子串的长度。

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stk = []
        dp = [0] * (len(s)+1)
        for i, j in enumerate(s):
            if j == '(':
                stk.append(i)
            else:
                if stk:
                    t = stk.pop()
                    dp[i] = i-t+1
                    if t: dp[i] += dp[t-1]
        return max(dp)

33.搜索旋转数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转，现要在数组中搜索一个给定的目标值，如果存在则返回索引，不存在返回-1。

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        def find1(L, R, nums, target):
            if L > R: return -1
            if nums[L] <= nums[R]:
                return find2(L, R, nums, target)
            M = L + (R-L) // 2
            if nums[L] <= nums[M]:
                if nums[L] <= target <= nums[M]:
                    return find2(L, M, nums, target)
                return find1(M+1, R, nums, target)
            else:
                if nums[M] <= target <= nums[R]:
                    return find2(M, R, nums, target)
                return find1(L, M-1, nums, target)

        def find2(L, R, nums, target):
            lo, hi = L, R
            while lo <= hi:
                mid = lo + (hi-lo) // 2
                if nums[mid] < target:
                    lo = mid+1
                elif nums[mid] > target:
                    hi = mid-1
                else:
                    return mid
            return -1

        return find1(0, len(nums)-1, nums, target)

34.搜索范围

给定一个按照升序排列的整数数组和一个目标值，找出给定目标值在数组中的开始位置和结束位置，如不存在，则返回[-1,-1]。

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        def find1(nums, target):
            if not nums: return -1
            lo, hi = 0, len(nums)-1
            while lo < hi:
                mid = lo + (hi-lo) // 2
                if nums[mid] < target:
                    lo = mid+1
                elif nums[mid] > target:
                    hi = mid-1
                else:
                    hi = mid
            if lo < len(nums) and nums[lo] == target:
                return lo
            return -1

        def find2(nums, target):
            if not nums: return -1
            lo, hi = 0, len(nums)-1
            while lo < hi:
                mid = lo + (hi-lo+1) // 2
                if nums[mid] < target:
                    lo = mid+1
                elif nums[mid] > target:
                    hi = mid-1
                else:
                    lo = mid
            if lo < len(nums) and nums[lo] == target:
                return lo
            return -1
    
        L = find1(nums, target)
        R = find2(nums, target)
        return [L, R]

35.搜索插入位置

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

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return 0
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < target:
                lo = mid+1
            else:
                hi = mid
        if lo < len(nums) and nums[lo] >= target:
            return lo
        return lo+1

36.有效的数独

判断一个9x9的数独是否有效，注意给定的数独序列只包含数字1-9和字符'.'，一个有效的数独不一定是可解的。

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        def ok(T):
            s = set()
            for i in T:
                if i == '.': continue
                if i in s: return False
                s.add(i)
            return True
        
        for i in range(9):
            t = []
            for j in range(9):
                t.append(board[i][j])
            if not ok(t):
                return False

        for j in range(9):
            t = []
            for i in range(9):
                t.append(board[i][j])
            if not ok(t):
                return False
            
        for i in range(0,9,3):
            for j in range(0,9,3):
                t = []
                for x in range(3):
                    for y in range(3):
                        t.append(board[i+x][j+y])
                if not ok(t):
                    return False
        return True

37.解数独

给定一个只包含数字1-9和字符'.'的数独序列，其中'.'代表未确定的数字，解出该数独。输入保证有唯一解。

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        
        def ok(T):
            s = set()
            for i in T:
                if i == '.': continue
                if i in s: return False
                s.add(i)
            return True
        
        def checkH(x):
            t = []
            for i in range(9):
                t.append(board[x][i])
            return ok(t)
        
        def checkV(y):
            t = []
            for i in range(9):
                t.append(board[i][y])
            return ok(t)
        
        def checkB(x, y):
            t = []
            for i in range(3):
                for j in range(3):
                    t.append(board[x+i][y+j])
            return ok(t)
        
        def check(x, y):
            return checkH(x) and checkV(y) and checkB(x//3*3, y//3*3)

        def dfs(n):
            if n == 81: return True
            x, y = n//9, n%9
            if board[x][y] != '.':
                return dfs(n+1)
            for i in range(1,10):
                board[x][y] = str(i)
                if check(x, y):
                    if dfs(n+1):
                        return True
            board[x][y] = '.'
            return False
        
        dfs(0)

38.报数

报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。给定一个正整数n，输出报数序列的第n项。

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ans = '1'
        for i in range(1, n):
            tmp = ''
            idx = 0
            while idx < len(ans):
                tag = ans[idx]
                cnt = 0
                while idx < len(ans) and ans[idx] == tag:
                    idx += 1
                    cnt += 1
                tmp += str(cnt) + tag
            ans = tmp
        return ans

39.组合求和

给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合，注意candidates中的数字可以无限制重复被选取，保证candidates中的数以及target都是正整数。输出结果要求不能包含重复的组合。

class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        def dfs(idx, cur, tmp, ans, candidates, target):
            if cur > target: return
            if cur == target:
                ans.append(tmp.copy())
                return
            if idx == len(candidates):
                return
            dfs(idx+1, cur, tmp+[candidates[idx]], ans, candidates, target)
            dfs(idx, cur+candidates[idx], tmp, ans, candidates, target)
        
        ans = []
        dfs(0, 0, [], ans, candidates, target)
        return ans

40.组合总和II

给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合，注意candidates中的数字在每个组合中最多只能使用一次，保证candidates中的数以及target都是正整数，要求解集不能包含重复的组合。

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        def dfs(idx, cur, tmp, ans, candidates, target):
            if cur > target: return
            if cur == target:
                ans.add(tuple(tmp))
                return
            if idx == len(candidates):
                return
            dfs(idx+1, cur, tmp, ans, candidates, target)
            dfs(idx+1, cur+candidates[idx], tmp+[candidates[idx]], ans, candidates, target)

        ans = set()
        candidates.sort()
        dfs(0, 0, [], ans, candidates, target)
        return sorted(list(ans))