数据结构和算法题 Data Structures& Algorothms

leetcode刷题记录 – 持续更新中

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 可以按任意顺序返回答案。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        j = -1
        for i in range(1,len(nums)):
            temp=nums[:i]
            if target-nums[i] in temp:
                j = temp.index(target-nums[i])
                break
        if j >=0:
            return [j, i]

3.无重复字符的最长子串

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len, hashmap=0,{}
        start =0
        for end in range(len(s)):
            hashmap[s[end]] = hashmap.get(s[end],0) + 1
            if len(hashmap) == end-start +1:
                max_len = max(max_len, end-start+1)
            
            while end-start+1 >len(hashmap):
                hashmap[s[start]] -=1
                if hashmap[s[start]]==0:
                    del hashmap[s[start]]
                start += 1
        return max_len
    

11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height)-1, 0
        while i<j:
            if height[i]<=height[j]:
                res = max(res, height[i]*(j-i))
                i += 1
            elif height[i]>height[j]:
                res = max(res, height[j]*(j-i))
                j -= 1
        return res

14.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs_dict = {}
        length = []
        output = []
        for str_ in  strs:
            strs_dict[str_] = list(str_)
            length.append(len(list(str_)))
        min_length = min(length)
        lengths=0
        temp = []
        while lengths < min_length and len(set(temp))<=1:
            temp=[]
            for keys in strs_dict:
                temp.append(strs_dict[keys][lengths])
            if len(set(temp))==1:
                output.append(temp[0])

            lengths+=1
        return "".join(output)

15.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            if nums[k] > 0: break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
            i, j = k + 1, len(nums) - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res

17.电话号码的数字组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        dic = {'2' :'abc', '3' :'def', '4' :'ghi', '5' :'jkl', '6' :'mno', '7' :'pqrs' ,'8' :'tuv' ,'9' :'wxyz'}
        n = len(digits)
        if n == 0:
            return []

        def dfs(index):
            if index == n:
                res.append(''.join(tmp))
            else:
                for i in dic[digits[index]]:
                    tmp.append(i)
                    dfs(index + 1)
                    tmp.pop()

        res = []
        tmp = []
        dfs(0)
        return res

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

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

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        #双指针 fast指向删除节点，slow指向删除节点的上一个节点
        dummy_head = ListNode(next = head)
        fast = dummy_head
        slow = dummy_head
        while n != -1:   #先让fast节点前进n步
            fast = fast.next
            n -= 1
        while fast != None:#再让fast slow一起前进，这样slow最终指向被删节点的前一个节点
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next

20.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution:
    def isValid(self, s: str) -> bool:
        # dic = {'{':'}','[':']','(':')'}
        dic = {')':'(',']':'[','}':'{'}
        stack = []
        for i in s:
            if stack and i in dic:
                if stack[-1] == dic[i]: stack.pop()
                else: return False
            else: stack.append(i)
        return not stack


# class Solution:
#     def isValid(self, s: str) -> bool:
#         dic = {')':'(',']':'[','}':'{'}
#         stack = []
#         for i in s:
#             if stack and i in dic:
#                 if stack[-1] == dic[i]: stack.pop()
#                 else: return False
#             else: stack.append(i)
#         return not stack

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:
        if not l1: return l2  # 终止条件，直到两个链表都空
        if not l2: return l1

        if l1.val <= l2.val:  # 递归调用
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
            
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

26.删除有效数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast = 0, 1
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow = slow + 1
                nums[slow] = nums[fast]
            fast = fast + 1
        return slow + 1

27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = nums.count(val)
        for i in range(n):
            nums.remove(val)
        return len(nums)

33.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        min_index = nums.index(min(nums))
        nums_ = nums[min_index:]+nums[:min_index]

        low = 0
        high = len(nums_)-1
        while low <= high:
            mid = (low + high)
            guess = nums_[mid]
            if guess == target:
                return nums.index(nums_[mid])
            if guess > target:
                high = mid - 1
            else:
                low = mid + 1
        return -1

34.在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearchLeft(nums:List[int], target:int)->List[int]:
            l = -1
            r = len(nums)
            while l+1 != r :
                mid = l+(r-l)//2
                if nums[mid] >= target :
                    r = mid
                else :
                    l = mid
            return r
        
        def binarySearchRight(nums:List[int], target:int)->List[int]:
            l = -1
            r = len(nums)
            while l+1 != r :
                mid = l+(r-l)//2
                if nums[mid] <= target :
                    l = mid
                else :
                    r = mid
            return l
        
        leftIdx = binarySearchLeft(nums, target)
        rightIdx = binarySearchRight(nums, target)

        if leftIdx<=rightIdx and rightIdx<len(nums) and nums[leftIdx]==target and nums[rightIdx]==target :
            return [leftIdx, rightIdx]

        return [-1, -1]

36.有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row, col, sqrt = defaultdict(set), defaultdict(set), defaultdict(set)
        for i in range(9):
            for j in range(9):
                val = board[i][j]
                if val == '.':
                    continue
                point = i // 3 * 3 + j // 3
                print(point)
                if val in row[i] or val in col[j] or val in sqrt[point]:
                    print(i, j, val)
                    print(row, col, sqrt)
                    return False
                row[i].add(val)
                col[j].add(val)
                sqrt[point].add(val)
        return True

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res, path, used = [], [], [False] * len(nums)

        def dfs() -> None:
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if used[i]: 
                    continue
                path.append(nums[i])
                used[i] = True
                dfs()
                # 回溯的过程中，将当前的节点从 path 中删除
                path.pop()
                used[i] = False

        dfs()
        return res

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = {}
        for s in strs:
            s_ = "".join(sorted(s))
            if s_ not in res:
                res[s_] = [s]
            else:
                res[s_].append(s)
        return list(res.values())

53.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = [nums[0],]
        for i in range(1,len(nums)):
            res.append(max(res[i-1]+nums[i],nums[i]))
        return max(res)

56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals: return []
        intervals.sort()
        res = [intervals[0]]
        for x, y in intervals[1:]:
            if res[-1][1] < x:
                res.append([x,y])
            else:
                res[-1][1] = max(y, res[-1][1])
        return res

58.最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.strip(" ")
        word_list = s.split(" ")
        last_word = word_list.pop()
        return len(last_word)

61.加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(num) for num in list(str(int(''.join(str(num) for num in digits))+1))]

67.二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a,2)+int(b,2))[2:]

69.x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x
        x_2 = x // 2
        for i in range(x_2+1):
            if i * i == x:
                return i
            elif i * i > x:
                return i-1
        return x_2

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution:
    def climbStairs(self, n: int) -> int:
        s = [1, 2]
        if n <= 2:
            return s[n - 1]
        while len(s) < n:
            print(s)
            s.append(s[-1] + s[-2])
        return s[-1]

73.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        row_zero = set()
        col_zero = set()
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    row_zero.add(i)
                    col_zero.add(j)
        for i in range(row):
            for j in range(col):
                if i in row_zero or j in col_zero:
                    matrix[i][j] = 0

74.搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非递减顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nums = []
        for list_ in matrix:
            nums += list_
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (low + high)
            guess = nums[mid]
            if guess == target:
                return True
            if guess > target:
                high = mid - 1
            else:
                low = mid + 1
        return False

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

class Solution:
    def combine(self, n: int, k: int) -> list:
        ans = list()

        def backtrack(tmp: list, index: int) -> None:
            if len(tmp) == k:
                ans.append(tmp[:])
                return
            for i in range(index, n + 1):
                tmp.append(i)
                backtrack(tmp, i + 1)
                tmp.pop()
        backtrack([], 1)
        return ans

82.删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next:
            return head
        if head.val != head.next.val:
            head.next = self.deleteDuplicates(head.next)
        else:
            move = head.next
            while move and head.val == move.val:
                move = move.next
            return self.deleteDuplicates(move)
        return head

83.删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        if head is None:
            return None
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
                
            else:
                cur =cur.next
        return head

# class Solution:
#     def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
#         if head is None:
#             return None
#         cur = head
#         while cur.next:
#             if cur.next.val == cur.val:
#                 cur.next = cur.next.next
#             else:
#                 cur = cur.next
#         return head

88.合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m]+nums2)
        # nums1[:] = sorted(nums1[:m] + nums2)

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

111.二叉树的最大深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def min_tree_depth(r):
            if r == None: 
                return 0
            l = min_tree_depth(r.left)
            right = min_tree_depth(r.right)
            
            if l == 0 or right == 0: 
                return max(l, right) + 1
            else: 
                return min(l, right) + 1

        return min_tree_depth(root)

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return root

        def BFS(oneLayer):
            nextLayer = []   # 每一次都搞个空的列表，去建立nextLayer
            for i in oneLayer:
                if i.left:
                    nextLayer.append(i.left)
                if i.right:
                    nextLayer.append(i.right)

            if len(nextLayer) > 1:  # 一共只有1个节点就没必要搞了。
                for j in range(0, len(nextLayer) - 1):
                    nextLayer[j].next = nextLayer[j + 1]  # 每个节点的next指向后面一个节点。

            if nextLayer:  # nextLayer不是空的话就继续往下走。
                BFS(nextLayer)

        BFS([root])  # 最开始就是只有一层一个根节点。
        return root

117.填充每个节点的下一个右侧节点指针 II

给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return root

        def BFS(oneLayer):
            nextLayer = []   # 每一次都搞个空的列表，去建立nextLayer
            for i in oneLayer:
                if i.left:
                    nextLayer.append(i.left)
                if i.right:
                    nextLayer.append(i.right)

            if len(nextLayer) > 1:  # 一共只有1个节点就没必要搞了。
                for j in range(0, len(nextLayer) - 1):
                    nextLayer[j].next = nextLayer[j + 1]  # 每个节点的next指向后面一个节点。

            if nextLayer:  # nextLayer不是空的话就继续往下走。
                BFS(nextLayer)

        BFS([root])  # 最开始就是只有一层一个根节点。
        return root

118.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]*i for i in range(1, numRows+1)]
        for index, element in enumerate(res):
            for j in range(1, len(element)-1):
                element[j] = res[index-1][j-1] + res[index-1][j]

        return res

120.三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for i in range(len(triangle)-2,-1,-1):
            for j in range(len(triangle[i])):
                triangle[i][j] = triangle[i][j] + min(triangle[i+1][j], triangle[i+1][j+1])
        return triangle[0][0]

121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''前i天的最大收益等于 max(前i-1天最大收益,第i天价格-前i天最小价格)'''
        profit = 0
        minprice = 1e9
        for i in range(len(prices)):
            minprice = min(minprice, prices[i])
            profit = max(profit,prices[i]-minprice)
        return profit

128.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res=0
        num_set = set(nums)
        for num in num_set:
            if (num-1) not in num_set:
                seq_len = 1 
                while (num+1) in num_set:
                    seq_len += 1
                    num += 1
                res = max(res, seq_len)
        return res

136.只出现一次的数

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in nums:
            n = nums.count(i)
            if n==1:
                return i
            else:
                continue

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                return True
        return False

142.环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return 
            fast, slow = fast.next.next, slow.next
            if fast == slow: 
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

153.寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        nodeA = headA
        nodeB = headB
        while (nodeA != nodeB):
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA
        return nodeA

162.寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return nums.index(max(nums))

169.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count_dict={}
        # length = len(nums)//2
        for num in list(set(nums)):
            count_dict[num] = nums.count(num)
        # res = [k for k, v in count_dict.items() if v >= length]
        return max(count_dict, key=lambda x: count_dict[x])

175.组合两个表

表: Person
+————-+———+
| 列名 | 类型 |
+————-+———+
| PersonId | int |
| FirstName | varchar |
| LastName | varchar |
+————-+———+
personId 是该表的主键（具有唯一值的列）。
该表包含一些人的 ID 和他们的姓和名的信息。

# Write your MySQL query statement below
select  firstName ,lastName ,city ,state
from Person t1 left join Address t2 on t1.PersonId=t2.PersonId    

176.第二高的薪水

Employee 表：
+————-+——+
| Column Name | Type |
+————-+——+
| id | int |
| salary | int |
+————-+——+
在 SQL 中，id 是这个表的主键。
表的每一行包含员工的工资信息。
查询并返回 Employee 表中第二高的薪水 。如果不存在第二高的薪水，查询应该返回 null(Pandas 则返回 None) 。

# Write your MySQL query statement below
select (
    select salary from (
        select salary, dense_rank() over (order by salary desc) rn 
        from Employee
        ) t where t.rn=2 limit 1
        ) SecondHighestSalary;

190.颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

class Solution:
    def reverseBits(self, n: int) -> int:
        bits = bin(n)[2:][::-1]
        bits += "0"*(32-len(bits))
        return int(bits, 2)

191.位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count("1")

193.有效电话号码

给定一个包含电话号码列表（一行一个电话号码）的文本文件 file.txt，写一个单行 bash 脚本输出所有有效的电话号码。
你可以假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字）
你也可以假设每行前后没有多余的空格字符。

# Read from the file file.txt and output all valid phone numbers to stdout.
python3 -c "import re;lines=open('file.txt').readlines();lines=[i.strip()for i in lines];ans=[i for i in lines if re.match('^\(\d{3}\) \d{3}-\d{4}$',i) or re.match('^\d{3}-\d{3}-\d{4}$',i)];   print('\n'.join(ans))"

196.删除重复的电子邮箱

表: Person
+————-+———+
| Column Name | Type |
+————-+———+
| id | int |
| email | varchar |
+————-+———+
id 是该表的主键列(具有唯一值的列)。
该表的每一行包含一封电子邮件。电子邮件将不包含大写字母。
编写解决方案 删除 所有重复的电子邮件，只保留一个具有最小 id 的唯一电子邮件。
（对于 SQL 用户，请注意你应该编写一个 DELETE 语句而不是 SELECT 语句。）
（对于 Pandas 用户，请注意你应该直接修改 Person 表。）
运行脚本后，显示的答案是 Person 表。驱动程序将首先编译并运行您的代码片段，然后再显示 Person 表。Person 表的最终顺序 无关紧要 。
返回结果格式如下示例所示。

# Please write a DELETE statement and DO NOT write a SELECT statement.
# Write your MySQL query statement below
DELETE p1 FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email AND p1.Id > p2.Id

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev = 0
        curr = 0
        # 每次循环，计算“偷到当前房子为止的最大金额”

        for i in nums:
            # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
            # dp[k] = max{ dp[k-1], dp[k-2] + i }
            prev, curr = curr, max(curr, prev + i)
            
            # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
        return curr

200.岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1
示例 2：
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid,r,c):
            if not 0<=r<len(grid) or not 0<=c<len(grid[0]):return
            if grid[r][c]!="1":return  #注意题目这里输入的是字符"0",“1”
            grid[r][c]="2"
            dfs(grid,r-1,c)
            dfs(grid,r+1,c)
            dfs(grid,r,c-1)
            dfs(grid,r,c+1)
            return 1  #是岛屿,则返回1

        res=0
        for  r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c]=="1":
                    res+=dfs(grid,r,c)  #累加岛屿的数量
        return res

205.同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # return all(s.index(s[i]) == t.index(t[i])  for i in range(len(s)))
        for i in range(len(s)): 
            if s.index(s[i]) == t.index(t[i]): 
                continue 
            else: 
                return False 
        return True

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        
    #     prev, curr = None, head
    #     while curr is not None:
    #         next = curr.next
    #         curr.next = prev
    #         prev = curr
    #         curr = next
    #     return prev

    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return p

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_len, sum_ = math.inf, 0    # Step 1: 定义需要维护的变量, 本题求最小长度，所以需要定义min_len, 本题又涉及求和，因此还需要一个sum变量
        start = 0   # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        for end in range(len(nums)):
            sum_ += nums[end]   # Step 3: 更新需要维护的变量 (min_len, sum_)
            while sum_ >= target:    # Step 4 这一题这里稍微有一点特别: sum_ >= target其实是合法的，但由于我们要求的是最小长度，
                min_len = min(min_len, end - start + 1)
                sum_ -= nums[start]    
                # 所以当sum_已经大于target的时候继续移动右指针没有意义，因此还是需要移动左指针慢慢逼近答案
                # 由于左指针的移动可能影响min_len和sum_的值，因此需要在移动前将它们更新
                start += 1
        if min_len == math.inf:   # Step 5：返回答案 (最小长度)
            return 0
        return min_len

217.存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        len1 = len(nums)
        len2 = len(list(set(nums)))
        if len1 != len2:
            return True
        else:
            return False

219.存在重复的元素II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        list_dict = {}
        for i in range(len(nums)):
            if nums[i] not in list_dict:
                list_dict[nums[i]]=i
            else:
                if i- list_dict[nums[i]] <=k:
                    return True
                else :
                    list_dict[nums[i]] = i
        return False

231.2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (n - 1) == 0

258.各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

class Solution:
    def addDigits(self, num: int) -> int:
        while len(str(num)) >= 2:
            num = sum(int(i) for i in list(str(num)))
        return num

263.丑数

丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <=0:
            return False
        while n % 2 == 0 :
            n //= 2
        while n % 3 == 0 :
            n //= 3
        while n % 5 == 0 :
            n //= 5
        return n ==1

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set([i for i in nums1 if i in nums2]))

350.两个数组的交集II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致
（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        jiaoji = set(nums1) & set(nums2)
        res = []
        for i in jiaoji:
            res += [i] * min(nums1.count(i), nums2.count(i))
        return res

382.链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.nodes = []
        while head:
            self.nodes.append(head)
            head = head.next

    def getRandom(self) -> int:
        return self.nodes[randint(0, len(self.nodes) - 1)].val

387.字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # list_ = list(s)
        # cnt = {}
        # for c in list_:
        #     cnt[c] = list_.count(c)
        # for key,vaule in cnt.items():
        #     if vaule == 1:
        #         return list_.index(key)
        # return -1

        m = {}
        l_s = list(s)
        for word in l_s:
            m[word] = 0
        for word in l_s:
            m[word] += 1
        for key,vaule in m.items():
            if vaule == 1:
                return l_s.index(key)
        return -1

389.找不同

给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return list(Counter(t) - Counter(s))[0] 

434.字符串中的单词数

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: “Hello, my name is John”
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 “Hello,” 算作 1 个单词。

class Solution:
    def countSegments(self, s: str) -> int:
        s = s.strip()
        s_list = s.split(" ")

        if len(s)== 0:
            return 0 
        else: 
            return (len([i for i in s_list if len(i)>0]))

438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        output, hashmap, hashmap_p = [], {}, {}

        for char in p:
            hashmap_p[char]=hashmap_p.get(char,0) + 1

        start=0
        for end in range(len(s)):
            hashmap[s[end]] = hashmap.get(s[end], 0) + 1
            if hashmap == hashmap_p:
                output.append(start)

            if end>= len(p) -1:
                hashmap[s[start]] -= 1
                if hashmap[s[start]] == 0:
                    del hashmap[s[start]]
                start += 1
        return output

485.最大连续1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        result,max_res = 0, 0
        start=0
        for end in range(len(nums)):
            if nums[end] ==1:
                result += 1
                max_res=max(max_res, result)
            else:
                result = 0
                start += 1
        return max_res

509.斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

class Solution:
    def fib(self, n: int) -> int:
        if n == 0 :
            return 0
        elif n ==1:
            return 1
        else :
            return (self.fib(n-1) + self.fib(n-2))

520.检测大写字母

我们定义，在以下情况时，单词的大写用法是正确的：
全部字母都是大写，比如 “USA” 。
单词中所有字母都不是大写，比如 “leetcode” 。
如果单词不只含有一个字母，只有首字母大写， 比如 “Google” 。
给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。

class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        if  str.isupper(word):
            return True
        elif str.islower(word):
            return True
        elif str.islower(word[1:]) and str.isupper(word[0]):
            return True
        else:
            return False

542.01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat and mat[0])
        dir = [(-1,0), (0,1), (1,0), (0,-1)]

        queue = deque()
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 0:
                    queue.append((r, c))
                else:
                    mat[r][c] = -1

        while queue:
            r, c = queue.popleft()
            for dr,dc in dir:
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= m or nc < 0 or nc >= n or mat[nr][nc] != -1: 
                    continue
                mat[nr][nc] = mat[r][c] + 1
                queue.append((nr, nc))
        return mat

547.省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            for j in range(cities):
                if isConnected[i][j] == 1 and j not in visited:
                    visited.add(j)
                    dfs(j)

        cities = len(isConnected)
        visited = set()
        provinces = 0

        for i in range(cities):
            if i not in visited:
                dfs(i)
                provinces += 1

        return provinces

566.重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        if len(mat) * len(mat[0]) != r * c: 
            return mat
        res, stack = [], []
        for row in mat:
            for e in row:
                stack.append(e)
                if len(stack) == c:
                    res.append(stack)
                    stack = []
        return res

567.字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        hashmap1, hashmap2, result = {}, {}, False
        for char in s1:
            hashmap1[char] = hashmap1.get(char, 0) + 1

        start = 0
        for end in range(len(s2)):
            hashmap2[s2[end]] = hashmap2.get(s2[end], 0) + 1
            if hashmap2 == hashmap1:
                result = True

            if end >= len(s1) - 1:
                hashmap2[s2[start]] -= 1
                if hashmap2[s2[start]] == 0:
                    del hashmap2[s2[start]]
                start += 1

        return result
        

572.另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if not s and not t:
            return True
        if not s or not t:
            return False
        return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)

617.合并二叉树

给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if root1 == None:        # 如果 root1 为空，则合并之后节点为 root2
            return root2
        if root2 == None:        # 如果 root2 为空，则合并之后节点为 root1
            return root1
        root = TreeNode(root1.val + root2.val)               # 如果都存在节点，创建一个新的节点存储合并后的值
        root.left = self.mergeTrees(root1.left, root2.left)  # 递归合并左子树
        root.right = self.mergeTrees(root1.right, root2.right)  # 递归合并右子树
        return root

627.变更性别

Salary 表：
+————-+———-+
| Column Name | Type |
+————-+———-+
| id | int |
| name | varchar |
| sex | ENUM |
| salary | int |
+————-+———-+
id 是这个表的主键（具有唯一值的列）。
sex 这一列的值是 ENUM 类型，只能从 (‘m’, ‘f’) 中取。
本表包含公司雇员的信息。
请你编写一个解决方案来交换所有的 ‘f’ 和 ‘m’ （即，将所有 ‘f’ 变为 ‘m’ ，反之亦然），仅使用 单个 update 语句 ，且不产生中间临时表。
注意，你必须仅使用一条 update 语句，且 不能 使用 select 语句

# Write your MySQL query statement below
# update salary set sex = if (sex = "m", "f", "m");

UPDATE salary
SET
    sex = CASE sex
        WHEN 'm' THEN 'f'
        ELSE 'm'
    END;

643.子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        sum_, max_avg = 0, -math.inf
        start = 0
        for end in range(len(nums)):
            sum_ += nums[end]
            if end - start + 1 == k:
                max_avg = max(max_avg, sum_ / k)
            if end >= k - 1:
                sum_ -= nums[start]
                start += 1
        return max_avg
        

695.岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution:
    """ 遍历二维数组，对于每块土地，去其前后左右找相邻土地，再去前后左右的土地找其前后左右的土地，直到周围没有土地
        对于每一块已找过的土地，为避免重复计算，将其置为0
        其实就是遍历了所有的岛屿，然后取这些岛屿的最大面积res = max(res, dfs(i, j)) """

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j]:
                grid[i][j] = 0
                return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
            return 0

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res = max(res, dfs(i, j))
        return res

713.乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        result, mutil = 0, 1    # Step 1: 定义需要维护的变量
        start = 0                        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        for end in range(len(nums)):
            mutil *= nums[end]           # Step 3: 更新需要维护的变量 (min_len, sum_)
            while mutil >= k and start <= end:
                mutil //= nums[start]    
                start += 1
            else:
                result += end-start+1
        return result

728.自除数

自除数 是指可以被它包含的每一位数整除的数。
例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
自除数 不允许包含 0 。
给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        res = []
        for i in range(left,right+1):
            for j in str(i):
                if j=='0' or i % int(j)!=0:
                    break
            else:
                res.append(i)
        return res

733.图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。

from queue import Queue

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if newColor == image[sr][sc]:  # 起始颜色和目标颜色相同，则直接返回原图
            return image
        directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}  # 设置四个方向偏移量，一种常见的省事儿技巧
        que = Queue()  # 构造一个队列，先把起始点放进去
        que.put((sr, sc))  # 记录初始颜色
        originalcolor = image[sr][sc]  # 当队列不为空
        while not que.empty():  # 取出队列的点并染色
            point = que.get()
            image[point[0]][point[1]] = newColor  # 遍历四个方向
            for direction in directions:  # 新点是(new_i,new_j)
                new_i = point[0] + direction[0]
                new_j = point[1] + direction[1]  # 如果这个点在定义域内并且它和原来的颜色相同
                if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == originalcolor:
                    que.put((new_i, new_j))
        return image

739.每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack, res = [], [0]* len(temperatures)
        for i , num in enumerate(temperatures):
            while stack and temperatures[stack[-1]]< num:
                index = stack.pop()
                res[index] = i - index
            stack.append(i)
        return res

746.使用最小的花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost)==1:return cost[0]
        if len(cost)==2:return min(cost)
        dp=[0 for _ in range(len(cost)+1)]
        for i in range(2,len(dp)):
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        return dp[-1]

771.宝石与石头

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

class Solution:
    def numJewelsInStones(self, jewels, stones):
        J = [j for j in jewels]
        S = [s for s in stones]
        res = 0
        for i in range(len(J)):
            res += S.count(J[i])
        return res

784.字母大小全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        ans = [""]
        for i, c in enumerate(s):
            if c.isalpha():
                ans = [a + c.lower() for a in ans] + [a + c.upper() for a in ans]
            else:
                ans = [a + c for a in ans]
        return ans

796.旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
例如, 若 s = ‘abcde’，在旋转一次之后结果就是’bcdea’ 。

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        length = len(s)
        i = 0
        while i <= length:
            s = s[1:]+s[0]
            if s == goal:
               return True
            i+=1
        return False

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def remove_(str_):
            r = []
            for i in range(len(str_)):
                if str_[i] != '#':
                    r.append(str_[i])
                elif str_[i] == '#' and len(r)>=1:
                    r.pop()

            return r

        return remove_(s) ==remove_(t)

944.腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2} # 腐烂集合
        fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}  # 新鲜集合
        time = 0
        while fresh:
            if not rotten: return -1
            # 即将腐烂的如果在新鲜的集合中，就将它腐烂
            rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh} 
            fresh -= rotten # 剔除腐烂的
            time += 1
        return time

986.区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        res=[]
        n,m=len(firstList),len(secondList)
        i,j=0,0
        while i<n and j<m:
            left = max(firstList[i][0],secondList[j][0])
            right = min(firstList[i][1],secondList[j][1])
            if left <= right:                         #判断是否有交集的条件
                res.append([left,right])
            if firstList[i][1]<secondList[j][1]:    #哪个右区间元素较小，指针就向前移动一位
                i+=1
            else:e
                j+=1
        return res

1021.删除最外层的括号

有效括号字符串为空 “”、”(“ + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。
对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        m, j, re = 0, 0, str()
        for i in range(len(S)):
            m += 1 if S[i]=='(' else -1
            if not m:
                re += S[j+1:i]
                j = i + 1
        return re

1137.第N个泰波那契数

泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

class Solution:
    @lru_cache(None)
    def tribonacci(self, n: int) -> int:
        if not n:
            return 0
        if n <= 2:
            return 1
        return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)

1266.访问所有点的最小时间

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。
你需要按照下面的规则在平面上移动：
每一秒内，你可以：
沿水平方向移动一个单位长度，或者
沿竖直方向移动一个单位长度，或者
跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        total = 0
        for i in range(1,len(points)):
            a = abs(points[i][0]-points[i-1][0])
            b = abs(points[i][1]-points[i-1][1])
            t = max(a,b)
            total += t
        return total

1281.整数的各位积和之差

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

class Solution(object):
    def subtractProductAndSum(self, n):
        return eval("*".join(str(n))) - eval("+".join(str(n)))
        # n = list(str(n))
        # muti = 1
        # summ = 0
        # for i in n:
        #     muti *= int(i)
        #     summ += int(i)
        # return muti-summ
        

1295.统计位数为偶数的数字

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        # res = 0
        # for num in nums:
        #     if len(str(num)) %2 == 0:
        #         res +=1
        # return res
        return sum(map(lambda x: len(str(x)) & 1 ^ 1, nums))

1342.将数字变成0的操作次数

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

class Solution:
    def numberOfSteps(self, num: int) -> int:
        flag = 0
        while num != 0:
            if num%2 == 0:
                num = num/2
                flag += 1
            else: 
                num = num - 1
                flag += 1
        return flag

1365.有多小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        nums_ = sorted(nums)
        res = []
        for i in nums:
            res.append(nums_.index(i))
        return res

1389.按既定顺序创建目标数组

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：
目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。
请你返回目标数组。
题目保证数字插入位置总是存在。

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        target = []
        for i in range(len(nums)):
            target.insert(index[i],nums[i])
        return target

1470.重新排列数组

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。

class Solution:
	def shuffle(self,nums,n):
		nums[::2],nums[1::2] = nums[:n],nums[n:]
		return nums

1431.拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        target = max(candies)
        return [x+extraCandies >= target for x in candies]

1572.矩阵对角线元素的和

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

import numpy as np
class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        mat = np.array(mat)
        for i in range(mat.shape[0]):
            for j in range(mat.shape[1]):
                if i != j and i + j + 1 != mat.shape[0]:
                    mat[i, j] = 0
        return int(np.sum(mat))

1603.设计停车系统

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类：
ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，三个参数分别对应每种停车位的数目。
bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.bucket = {1:big, 2:medium, 3:small}

    def addCar(self, carType: int) -> bool:
        if self.bucket[carType] > 0:
            self.bucket[carType] -= 1
            return True
        return False
# Your ParkingSystem object will be instantiated and called as such:
# obj = ParkingSystem(big, medium, small)
# param_1 = obj.addCar(carType)

1614.括号的最大嵌套深度

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
字符串是一个空字符串 “”，或者是一个不为 “(“ 或 “)” 的单字符。
字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
depth(“”) = 0
depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 “(“ 或者 “)”
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串

class Solution(object):
    def maxDepth(self, s):
        if '(' and ')' not in list(s):
            return 0 
        dep,m = [],0
        for st in s:
            if st == '(' : 
                m += 1
                dep.append(m)
            if st == ')' : 
                m -= 1
                dep.append(m)
        return max(dep)
        # try :
        #     return max(dep)
        # except:
        #     return 0

1662.检查两个字符串数组是否相等

给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        # word1 = ''.join(word1)
        # word2 = ''.join(word2)
        # return word1 == word2
        return ''.join(word1) == ''.join(word2)

1672.最富有客户的资产数量

1684.统计一致字符串的数目

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。
请你返回 words 数组中 一致字符串 的数目。

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        num_result = len(words) #默认都是
        for word in words:
            for a_char in word:
                if  allowed.find(a_char)==-1:
                    num_result-=1 #一个字母不在allowed里面 就减去
                    break
        return num_result

1695.删除子数组的最大得分

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        sum_,max_sum, hashmap=0, 0, {}
        start = 0
        for end in range(len(nums)):
            sum_ += nums[end]
            hashmap[nums[end]] = hashmap.get(nums[end], 0) + 1
            if hashmap.get(nums[end], 0) < 2:
                max_sum = max(max_sum, sum_)
            while hashmap[nums[end]]>=2:
                head = nums[start]
                sum_ -= head
                hashmap[head] -= 1
                if hashmap[head] ==0:
                    del hashmap[head]
                start += 1
        return max_sum

1773.统计匹配检测规则的物品数量

给你一个数组 items ，其中 items[i] = [typei, colori, namei] ，描述第 i 件物品的类型、颜色以及名称。
另给你一条由两个字符串 ruleKey 和 ruleValue 表示的检索规则。
如果第 i 件物品能满足下述条件之一，则认为该物品与给定的检索规则 匹配 ：
ruleKey == “type” 且 ruleValue == typei 。
ruleKey == “color” 且 ruleValue == colori 。
ruleKey == “name” 且 ruleValue == namei 。
统计并返回 匹配检索规则的物品数量 。

class Solution(object):
    def countMatches(self, items, ruleKey, ruleValue):
        """
        :type items: List[List[str]]
        :type ruleKey: str
        :type ruleValue: str
        :rtype: int
        """
        rule = {
            "type":0,
            "color":1,
            "name":2}
        i = 0
        for item in items:
            if item[rule[ruleKey]] == ruleValue:
                i +=1
        return i 

1822.数组元素积的符号

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：
如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。
返回 signFunc(product) 。

class Solution(object):
    def arraySign(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num = 1
        for i in nums:
            num *= i
        if 0 in nums:
            return 0
        elif num >0:
            return 1
        elif num <0:
            return -1

1827.最少操作使数组递增

给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。
比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。
请你返回使 nums 严格递增 的 最少 操作次数。
我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

class Solution:
    def minOperations(self, nums):
        length = len(nums)
        if length <= 1:
            return 0
        ret = 0
        left = nums[0]
        for right in nums[1:]:
            tmp = max(left  + 1, right)
            ret += tmp - right
            left = tmp 
        return ret

1832.判断句子是否为全字母句

全字母句 指包含英语字母表中每个字母至少一次的句子。
给你一个仅由小写英文字母组成的字符串 sentence ，请你判断 sentence 是否为 全字母句 。
如果是，返回 true ；否则，返回 false 。

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        # return len(set(list(sentence))) >= 26
        return len(collections.Counter(sentence)) == 26

面试题16.08.整数的英语表示

给定一个整数，打印该整数的英文描述。

class Solution:
    def numberToWords(self, num: int) -> str:
        to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
        tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()

        def helper(num):
            if num < 20:
                return to19[num - 1:num]
            if num < 100:
                return [tens[num // 10 - 2]] + helper(num  % 10)
            if num < 1000:
                return [to19[num // 100 - 1]] + ['Hundred'] + helper(num % 100)
            for p, w in enumerate(['Thousand', 'Million', 'Billion'], 1):
                if num < 1000 ** (p + 1):
                    return helper(num // 1000 ** p) + [w] + helper(num % 1000 ** p)
        return ' '.join(helper(num)) or 'Zero'

LCR28采购方案

小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

class Solution:
    def purchasePlans(self, nums: List[int], target: int) -> int:
        # nums.sort()
        # j = len(nums)
        # while nums[0] + nums[j] >target:
        #     j -= 1
        #     break
        # return (j) % 1000000007
        nums.sort()
        ans=0
        i=0
        while nums[i]<target:
            index=bisect.bisect_right(nums,target-nums[i])
            if index>i:
                ans+=index-i-1
            else:
                break
            i+=1
            if i==len(nums):
                break
        return ans % 1000000007

LCR125.图书整理II

读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：
push(bookID)：把借阅的书籍还到图书馆。
pop()：从图书馆中借出书籍。
为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是 最早 归还到图书馆的书籍。你需要返回 每次读者借出书的值 。
如果没有归还的书可以取出，返回 -1 。

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if len(self.stack2) == 0 and len(self.stack1) == 0:
            return -1
        elif len(self.stack2) == 0:
            while len(self.stack1) > 0:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

LCR146.螺旋遍历二维数组

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

class Solution:
    def spiralOrder(self, matrix:[[int]]) -> [int]:
        if not matrix: return []
        l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
        while True:
            for i in range(l, r + 1): res.append(matrix[t][i]) # left to right
            t += 1
            if t > b: break
            for i in range(t, b + 1): res.append(matrix[i][r]) # top to bottom
            r -= 1
            if l > r: break
            for i in range(r, l - 1, -1): res.append(matrix[b][i]) # right to left
            b -= 1
            if t > b: break
            for i in range(b, t - 1, -1): res.append(matrix[i][l]) # bottom to top
            l += 1
            if l > r: break
        return res

LCR147.最小栈

请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """        
        self.stack = []
        self.minStack = []


    def push(self, x: int) -> None:
        self.stack.append(x)
        if self.minStack == [] or x < self.min():
            self.minStack.append(x)
        else:
            temp = self.min()
            self.minStack.append(temp)

    def pop(self) -> None:
        if self.stack == [] or self.minStack == []:
            return None
        self.minStack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.minStack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

LCR159.库存管理III

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[0:k]

####LCR173.点名
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # if nums == [1]:
        #     return 0
        # elif len(nums) == 1:
        #     return nums[0]+1
        # else:
        #     start = nums[0]
        #     end = nums[-1]
        #     re = []
        #     for i in range(start,end+1):
        #         re.append(i)
        #     for i in re:
        #         if i not in nums:
        #             return i 
        length = len(nums) + 1
        return (length - 1) * length // 2 - sum(nums)

LCR181.字符串中的单词反转

你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息 message 转换为正常语序。
注意：输入字符串 message 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split()[::-1])

LCR182.动态口令

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：
设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾
请返回更新后的密码字符串。

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:]+ s[:n]

LCP01.猜数字

小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。

class Solution:
    def game(self, guess: List[int], answer: List[int]) -> int:
        res = 0
        for i in range(len(guess)):
            if guess[i] == answer[i]:
                res += 1
            else: res += 0
        return res
        

LCP06.拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

class Solution:
    def minCount(self, coins: List[int]) -> int: 
        return sum([int(i/2) + i%2 for i in coins])