leetcode (更新中)

1 两数之和

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

2 两数相加

class Solution:
    def addTwoNumbers(self, l1, l2):
        a=""
        b=""
        while True:
            a+=str(l1.val)
            if l1.next:
                l1=l1.next
            else:
                break
        while True:
            b+=str(l2.val)
            if l2.next:
                l2=l2.next
            else:
                break
        a=''.join(list(reversed(list(a))))
        b=''.join(list(reversed(list(b))))
        c=str(int(a)+int(b))
        l=ListNode(c[0])
        l3=ListNode(0)
        for i in range(1,len(c)):
            l3=ListNode(c[i])
            l3.next=l
            l=l3
        return l

3 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s):
        if len(s)<=1:
            return len(s)
        max=0
        a=[s[0]]
        for i in range(1,len(s)):
            if s[i] in a:
                if max<len(a):
                    max=len(a)
                b=a.index(s[i])
                a=a[b+1:]
                a.append(s[i])
            else:
                a.append(s[i])
        if max<len(a):
            max=len(a)
        return max

4 寻找两个正序数组的中位数

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        nums1.sort()
        a=len(nums1)
        if a%2==0:
            return (nums1[a//2]+nums1[a//2-1])/2
        else:
            return nums1[a//2]

5 最长回文子串

class Solution:
    def longestPalindrome(self, s):
        def check(a,b):
            while a>=0 and b<len(s) and s[a]==s[b]:
                a-=1
                b+=1
            return s[a+1:b]
        max=""
        for i in range(len(s)):
            tmp = check(i,i)
            if len(max)<len(tmp):
                max=tmp
            tmp = check(i,i+1)
            if len(max)<len(tmp):
                max=tmp
        return max

6 Z 字形变换

class Solution:
    def convert(self, s, numRows):
        a = [[] for i in range(numRows)]
        i=0
        j=0
        index=1
        while j<len(s):
            a[i].append(s[j])
            if index==1:
                i+=1
                if i==numRows:
                    i=max(numRows-2,0)
                    index=-1
            else:
                i-=1
                if i==-1:
                    i=min(1,numRows-1)
                    index=1
            j+=1
        r=""
        for i in range(len(a)):
            for j in range(len(a[i])):
                r+=a[i][j]
        return r

7 整数反转

class Solution:
    def reverse(self, x):
        neg = -1
        s = str(x)
        if s[0]=='-':
            s = s[1:]
            neg = 1
        a = int(s[::-1])*neg*(-1)
        if a>2**31-1 or a<2**31*-1:
            return 0
        else:
            return a

8 字符串转换整数 (atoi)

class Solution:
    def myAtoi(self, s):
        s = s.lstrip()
        if s=='':
            return 0
        if s[0]=='+' and len(s)>1:
            if s[1]<'0' or s[1]>'9':
                return 0
            else:
                s=s[1:]
        if s[0]=='-' or (s[0]>='0' and s[0]<='9'):
            i=1
            while i<len(s) and s[i]>='0' and s[i]<='9':
                i+=1
            s=s[:i]
            if s=='-':
                return 0
            s=int(s[:i])
            if s>2**31-1:
                return 2**31-1
            if s<2**31*(-1):
                return 2**31*(-1)
            return s
        return 0

9 回文数

class Solution:
    def isPalindrome(self, x):
        s=str(x)
        i=0
        j=len(s)-1
        while i<=j:
            if s[i]!=s[j]:
                return False
            i+=1
            j-=1
        return True

10 正则表达式匹配

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if (s!='' and p=='') or (p!='' and p[0]=='*'):
            return False
        res = [(0,0)]
        only = []
        while res:
            si,pi=res.pop(0)
            if (si,pi) in only:
                continue
            only.append((si,pi))
            if pi==len(p):
                if si==len(s):
                    return True
                continue
            if si==len(s):
                if pi<len(p)-1 and p[pi+1]=='*':
                    res.append((si,pi+2))
                elif p[pi]=='*':
                    res.append((si,pi+1))
                continue
            if p[pi]=='.':
                res.append((si+1,pi+1))
                if pi<len(p)-2 and p[pi+1]=='*':
                    res.append((si,pi+2))
            elif p[pi]=='*':
                if p[pi-1]=='*':
                    continue
                if p[pi-1]=='.' or s[si-1]==p[pi-1]:
                    if p[pi-1]=='.' or s[si-1]==s[si]:
                        res.append((si+1,pi))
                        res.append((si+1,pi+1))
                    res.append((si,pi+1))
                res.append((si-1,pi+1))
            else:
                if s[si]==p[pi]:
                    res.append((si+1,pi+1))
                if pi<len(p)-2 and p[pi+1]=='*':
                    res.append((si,pi+2))
        return False

11 盛最多水的容器

class Solution:
    def maxArea(self, h):
        m=[]
        i=0
        j=len(h)-1
        while i<j:
            m.append((j-i)*min(h[i],h[j]))
            if h[i]<h[j]:
                i+=1
            else:
                j-=1
        return max(m)

12 整数转罗马数字

class Solution:
    def intToRoman(self, num: int) -> str:
        res = ''
        a=[1000,900,500,400,100,90,50,40,10,9,5,4,1]
        b=['M','CM','D',"CD",'C','XC','L','XL','X','IX','V','IV','I']
        while num>0:
            for i in range(len(a)):
                if num>=a[i]:
                    num-=a[i]
                    res+=b[i]
                    break
        return res

13 罗马数字转整数

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0
        a=[1000,900,500,400,100,90,50,40,10,9,5,4,1]
        b=['M','CM','D',"CD",'C','XC','L','XL','X','IX','V','IV','I']
        while s:
            for i in range(len(a)):
                if s.startswith(b[i]):
                    res+=a[i]
                    s=s[len(b[i]):]
                    break
        return res

14 最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        k = ""
        try:
            for i in range(len(strs[0])):
                for j in range(len(strs)-1):
                    if strs[j][i]!=strs[j+1][i]:
                        return k
                k = k+strs[0][i]
        except:
            pass
        return k

15 三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        if len(nums)==0 or nums[-1]<0:
            return []
        res = []
        for i in range(len(nums)-2):
            if nums[i]>0:
                break
            if i>0 and nums[i]==nums[i-1]:
                continue
            m,n=i+1,len(nums)-1
            while m<n:
                if nums[n]<0:
                    break
                elif nums[m]+nums[n]+nums[i]==0:
                    res.append([nums[i],nums[m],nums[n]])
                    while m<len(nums)-1 and nums[m]==nums[m+1]:
                        m+=1
                    while n>i and nums[n]==nums[n-1]:
                        n-=1
                    m+=1
                    n-=1
                elif nums[m]+nums[n]+nums[i]>0:
                    n-=1
                else:
                    m+=1
        return res

16 最接近的三数之和

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        dis = target-nums[0]-nums[1]-nums[2]
        k = len(nums)-1
        for i in range(k-1):
            m, n = i+1, k
            while m<n:
                s = nums[i]+nums[m]+nums[n]
                if s==target:
                    return target
                elif s>target:
                    if s-target<abs(dis):
                        dis = target-s
                    n-=1
                else:
                    if target-s<abs(dis):
                        dis = target-s
                    m+=1
        return target-dis

17 电话号码的字母组合

from functools import reduce 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        d = [['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],['m','n','o'],
            ['p','q','r','s'],['t','u','v'],['w','x','y','z']]
        r = []
        for i in digits:
            r.append(d[int(i)-2])
        def fn(list1,list2):
            return [i+j for i in list1 for j in list2]
        return reduce(fn,r)

18 四数之和

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        if len(nums)==0 or (target<0 and nums[-1]<target) or (target>=0 and nums[0]>target):
            return []
        res = []
        k = len(nums)-1
        for i in range(k-2):
            if target>=0 and nums[i]>target:
                break
            if i>0 and nums[i]==nums[i-1]:
                continue
            for j in range(i+1,k-1):
                if target>=0 and nums[i]+nums[j]>target:
                    break
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                m, n = j+1, k
                while m<n:
                    s = nums[i]+nums[j]+nums[m]
                    if target>=0 and s>target:
                        break
                    elif s+nums[n]==target:
                        res.append([nums[i],nums[j],nums[m],nums[n]])
                        while m<k and nums[m]==nums[m+1]:
                            m+=1
                        while n>j and nums[n]==nums[n-1]:
                            n-=1
                        m+=1
                        n-=1
                    elif s+nums[n]>target:
                        n-=1
                    else:
                        m+=1
        return res

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        a = head
        b = head
        for i in range(n):
            a = a.next
        if not a:
            return head.next
        while a.next:
            a = a.next
            b = b.next
        b.next = b.next.next
        return head

20 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        a = []
        for i in s:
            if len(a)==0:
                a.append(i)
            elif i==')' and a[-1]=='(':
                a.pop()
            elif i==']' and a[-1]=='[':
                a.pop()
            elif i=='}' and a[-1]=='{':
                a.pop()
            else:
                a.append(i)
        return len(a)==0

21 合并两个有序链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        k = p = ListNode()
        m, n = l1, l2
        while m and n:
            if m.val<=n.val:
                k.next = m
                k = k.next
                m = m.next
            else:
                k.next = n
                k = k.next
                n = n.next
        if m:
            k.next = m
        elif n:
            k.next = n
        return p.next

22 括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def onestep(s,left,right):
            if len(s)==n*2:
                if left==right:
                    res.append(s)
            elif left>right:
                onestep(s+'(',left+1,right)
                onestep(s+')',left,right+1)
            elif left==right:
                onestep(s+'(',left+1,right)
        onestep('(',1,0)
        return res

26 删除排序数组中的重复项

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums)<2:
            return len(nums)
        i = 1
        while i<len(nums):
            if nums[i]==nums[i-1]:
                del nums[i]
            else:
                i+=1
        return len(nums)

27 移除元素

class Solution:
    def removeElement(self, nums, val):
        i=0
        while i<len(nums):
            if nums[i]==val:
                nums.pop(i)
            else:
                i+=1
        return len(nums)

35 搜索插入位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i]>=target:
                return i
        return len(nums)

38 外观数列

class Solution:
    def countAndSay(self, n: int) -> str:
        a='1 '
        if n==1:
            return a[:-1]
        for i in range(n-1):
            b=m=n=''
            for k in a:
                if m=='' and n=='':
                    m=k
                    n=1
                elif k==m:
                    n+=1
                else:
                    b=b+str(n)+m
                    m=k
                    n=1
            a=b+' '
        return a[:-1]

53 最大子序和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            if nums[i-1]>0:
                nums[i]+=nums[i-1]
        return max(nums)

54 螺旋矩阵

class Solution:
    def spiralOrder(self, m):
        i=0
        j=-1
        t='L'
        a=[]
        if m==[]:
            return []
        while len(a)!=len(m)*len(m[0]):
            if t=='L':
                j+=1
            elif t=='R':
                j-=1
            elif t=='U':
                i-=1
            else:
                i+=1
            a.append(m[i][j])
            m[i][j]='$'
            if t=='L' and (j==len(m[0])-1 or m[i][j+1]=='$'):
                t='D'
            elif t=='D' and (i==len(m)-1 or m[i+1][j]=='$'):
                t='R'
            elif t=='R' and (j==0 or m[i][j-1]=='$'):
                t='U'
            elif t=='U' and (i==0 or m[i-1][j]=='$'):
                t='L'
        return a

55 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums)<2:
            return True
        end = len(nums)-1
        for i in range(len(nums)-1,-1,-1):
            if nums[i]>=end-i:
                end = i
        return end==0

58 最后一个单词的长度

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.strip().split(' ')[-1])

62 不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        a = []
        for i in range(m):
            a.append([0]*n)
        for i in range(m):
            a[i][0] = 1
        for i in range(n):
            a[0][i] = 1
        for i in range(1,m):
            for j in range(1,n):
                a[i][j] = a[i][j-1]+a[i-1][j]
        return a[m-1][n-1]

63 不同路径 II

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        a = []
        for i in range(m):
            a.append([0]*n)
        a[0][0] = 1 if obstacleGrid[0][0]==0 else 0
        for i in range(1,m):
            if obstacleGrid[i][0]==1:
                a[i][0] = 0
            else:
                a[i][0] = a[i-1][0]
        for i in range(1,n):
            if obstacleGrid[0][i]==1:
                a[0][i] = 0
            else:
                a[0][i] = a[0][i-1]
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j]==1:
                    a[i][j] = 0
                else:
                    a[i][j] = a[i][j-1]+a[i-1][j]
        return a[m-1][n-1]

66 加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)-1,-1,-1):
            if digits[i]<9:
                digits[i]+=1
                return digits
            else:
                digits[i]=0
                if i==0:
                    digits.insert(0,1)
                    return digits

67 二进制求和

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        c = 0
        d = ""
        if len(a)>len(b):
            while len(b)<len(a):
                b = '0'+b
        else:
            while len(b)>len(a):
                a = '0'+a
        for i in range(len(a)-1,-1,-1):
            t = int(a[i])+int(b[i])+c
            if t==0:
                d = "0"+d
                c = 0
            elif t==1:
                d = "1"+d
                c = 0
            elif t==2:
                d = "0"+d
                c = 1
            else:
                d = "1"+d
                c = 1
        if c==1:
            d = "1"+d
        return d

69 x 的平方根

class Solution:
    def mySqrt(self, x):
        if x<2:
            return x
        start = 0
        end = x
        middle = x//2
        while start<end-1:
            if middle**2>x:
                end = middle
                middle = (start+end)//2
            elif middle**2<x:
                start = middle
                middle = (start+end)//2
            else:
                return middle
        return start

70 爬楼梯

class Solution:
    def climbStairs(self, n):
        a=[0]*(n+1)
        a[0]=1
        for i in range(n):
            if i+2<n+1:
                a[i+2]+=a[i]
            if i+1<n+1:
                a[i+1]+=a[i]
        return a[n]

73 矩阵置零

class Solution:
    def setZeroes(self, m):
        a=len(m)
        b=len(m[0])
        for i in range(a):
            for j in range(b):
                if m[i][j]==0:
                    for k in range(a):
                        if m[k][j]!=0:
                            m[k][j]='$'
                    for k in range(b):
                        if m[i][k]!=0:
                            m[i][k]='$'
        for i in range(a):
            for j in range(b):
                if m[i][j]=='$':
                    m[i][j]=0

74 搜索二维矩阵

class Solution:
    def searchMatrix(self, m, t):
        if len(m)==0 or len(m[0])==0:
            return False
        i=0
        while i<len(m):
            if m[i][0]>t:
                break
            i+=1
        if i==0:
            return False
        else:
            return (t in m[i-1])

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

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        a = head
        t = head
        while head and head.next:
            head = head.next
            if head.val==t.val:
                t.next = head.next
            else:
                t = t.next
        return a

88 合并两个有序数组

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[m+i]=nums2[i]
        nums1[0:m+n]=sorted(nums1[0:m+n])

94 二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        t = root
        while stack or t:
            if t:
                stack.append(t)
                t = t.left
            else:
                t = stack.pop()
                res.append(t.val)
                t = t.right
        return res

100 相同的树

class Solution:
    def isSameTree(self, p, q):
        a=[]
        b=[]
        def s(m,r):
            if r:
                m.append(r.val)
                s(m,r.left)
                s(m,r.right)
            else:
                m.append('$')
        s(a,p)
        s(b,q)
        if len(a)!=len(b):
            return False
        for i in range(len(a)):
            if a[i]!=b[i]:
                return False
        return True

101 对称二叉树

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        a=[]
        b=[]
        stack=[]
        node=root
        while stack or node:
            while True:
                if not node:
                    a.append('null')
                    break
                a.append(node.val)
                stack.append(node)
                node=node.left
            node=stack.pop()
            node=node.right
        stack=[]
        node=root
        while stack or node:
            while True:
                if not node:
                    b.append('null')
                    break
                b.append(node.val)
                stack.append(node)
                node=node.right
            node=stack.pop()
            node=node.left
        for i in range(len(a)):
            if a[i]!=b[i]:
                return False
        return True

104 二叉树的最大深度

class Solution:
    def maxDepth(self, root):
        def se(a,r):
            if r:
                return max(se(a+1,r.left),se(a+1,r.right),1)
            else:
                return a
        return se(0,root)

107 二叉树的层次遍历 II

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        a=[root]
        b=[]
        res=[]
        while a:
            res.append([])
            for i in a:
                res[-1].append(i.val)
                if i.left:
                    b.append(i.left)
                if i.right:
                    b.append(i.right)
            a,b=b,[]
        res.reverse()
        return res

111 二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        t1 = [root]
        t2 = []
        c = 1
        while True:
            for t in t1:
                if t.left:
                    t2.append(t.left)
                if t.right:
                    t2.append(t.right)
                if t.left==None and t.right==None:
                    return c
            c+=1
            t1=t2
            t2=[]

112 路径总和

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        a,b=[root],[]
        while a:
            for i in a:
                if not i.left and not i.right and i.val==sum:
                    return True
            for i in a:
                if i.left:
                    i.left.val=i.left.val+i.val
                    b.append(i.left)
                if i.right:
                    i.right.val=i.right.val+i.val
                    b.append(i.right)
            a,b=b,[]
        return False

118 杨辉三角

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        a = [[1],[1,1]]
        if numRows<3:
            return a[:numRows]
        for i in range(2,numRows):
            a.append([1])
            for j in range(1,len(a[-2])):
                a[-1].append(a[-2][j]+a[-2][j-1])
            a[-1].append(1)
        return a

119 杨辉三角 II

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        a=[1]
        b=[]
        for i in range(rowIndex):
            b.append(1)
            for k in range(len(a)-1):
                b.append(a[k]+a[k+1])
            b.append(1)
            a,b=b,[]
        return a

120 三角形最小路径和

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

121 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)<2:
            return 0
        lmin=prices[0]
        best=0
        for i in range(1,len(prices)):
            if best<prices[i]-lmin:
                best=prices[i]-lmin
            if lmin>prices[i]:
                lmin=prices[i]
        return best

122 买卖股票的最佳时机 II

class Solution:
    def maxProfit(self, prices):
        a=0
        for i in range(len(prices)-1):
            if prices[i]<prices[i+1]:
                a+=prices[i+1]-prices[i]
        return a

136 只出现一次的数字

class Solution:
    def singleNumber(self, nums):
        a=sum(nums)
        b=sum(set(nums))
        return b*2-a

150 逆波兰表达式求值

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        a = []
        for t in tokens:
            if t=='+':
                a.append(a.pop()+a.pop())
            elif t=='-':
                a.append(0-a.pop()+a.pop())
            elif t=='*':
                a.append(a.pop()*a.pop())
            elif t=='/':
                t1 = a.pop()
                t2 = a.pop()
                if t1*t2==0:
                    a.append(0)
                else:
                    a.append(abs(t2)//abs(t1)*(t1*t2)//(abs(t2)*abs(t1)))
            else:
                a.append(int(t))
        return a[0]

151 翻转字符串里的单词

class Solution(object):
    def reverseWords(self, s):
        a=s.split(' ')
        a=[i for i in a if len(i)>0]
        if len(a)==0:
            return ""
        a.reverse()
        return ' '.join(a)

152 乘积最大子数组

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        m = nums[0]
        nums[0] = [nums[0]]
        for i in range(1,len(nums)):
            t = [nums[i]]
            for j in nums[i-1]:
                t.append(nums[i]*j)
            nums[i] = [max(t),min(t)]
            if max(t)>m:
                m = max(t)
        return m

165 比较版本号

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = version1.split('.')
        v2 = version2.split('.')
        k = min(len(v1),len(v2))
        for i in range(k):
            if int(v1[i])>int(v2[i]):
                return 1
            elif int(v1[i])<int(v2[i]):
                return -1
        if len(v1)>len(v2):
            for i in v1[k:]:
                if int(i)>0:
                    return 1
        elif len(v1)<len(v2):
            for i in v2[k:]:
                if int(i)>0:
                    return -1
        return 0

167 两数之和 II - 输入有序数组

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        a = {}
        for i in range(len(numbers)):
            if target-numbers[i] in a:
                return [a[target-numbers[i]],i+1]
            elif numbers[i] not in a:
                a[numbers[i]] = i+1

168 Excel表列名称

class Solution:
    def convertToTitle(self, n: int) -> str:
        s = ''
        while n>0:
            m = n%26
            if m==0:
                n = n//26-1
                s = 'Z'+s
            else:
                n = n//26
                s = chr(m+64)+s
        return s

169 多数元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

171 Excel表列序号

class Solution:
    def titleToNumber(self, s):
        a=list(s)
        m=0
        for i in a:
            m=m*26+ord(i)-64
        return m

172 阶乘后的零

class Solution:
    def trailingZeroes(self, n: int) -> int:
        c = 0
        k = 5
        while k<=n:
            c+=n//k
            k*=5
        return c

175 组合两个表

SELECT FirstName, LastName, City, State From Person LEFT OUTER JOIN Address ON Person.PersonId=Address.PersonId;

181 超过经理收入的员工

SELECT E1.NAME AS Employee FROM Employee E1 INNER JOIN Employee E2 ON E1.ManagerId = E2.Id AND E1.Salary > E2.Salary;

182 查找重复的电子邮箱

SELECT Email FROM Person GROUP BY Email Having count(Id)>1;

183 从不订购的客户

SELECT Name AS Customers From Customers LEFT OUTER JOIN Orders ON Customers.Id=Orders.CustomerId WHERE CustomerId IS NULL;

189 旋转数组

class Solution:
    def rotate(self, nums, k):
        for i in range(k):
            nums.insert(0,nums[-1])
            nums.pop()

196 删除重复的电子邮箱

DELETE p1 From Person AS p1, Person AS p2 WHERE p1.Email=p2.Email AND p1.Id>p2.Id;

198 打家劫舍

class Solution:
    def rob(self, nums: List[int]) -> int:
        include = 0
        exclude = 0
        for i in nums:
            include,exclude = max(exclude+i,include),include
        return include

200 岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        c = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=="1":
                    grid[i][j] = "0"
                    c+=1
                    t1 = [(i,j)]
                    t2 = []
                    while len(t1)>0:
                        for k in t1:
                            if k[0]>0 and grid[k[0]-1][k[1]]=="1":
                                grid[k[0]-1][k[1]] = "0"
                                t2.append((k[0]-1,k[1]))
                            if k[1]>0 and grid[k[0]][k[1]-1]=="1":
                                grid[k[0]][k[1]-1] = "0"
                                t2.append((k[0],k[1]-1))
                            if k[0]<len(grid)-1 and grid[k[0]+1][k[1]]=="1":
                                grid[k[0]+1][k[1]] = "0"
                                t2.append((k[0]+1,k[1]))
                            if k[1]<len(grid[0])-1 and grid[k[0]][k[1]+1]=="1":
                                grid[k[0]][k[1]+1] = "0"
                                t2.append((k[0],k[1]+1))
                        t1 = t2
                        t2 = []
        return c

202 快乐数

class Solution:
    def isHappy(self, n: int) -> bool:
        a = []
        while n not in a:
            if n==1:
                return True
            a.append(n)
            t = list(str(n))
            n = 0
            for i in t:
                n+=int(i)**2
        return False

203 移除链表元素

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        while head and head.val==val:
            head = head.next
        if not head:
            return head
        a = head
        while head.next:
            if head.next.val==val:
                head.next = head.next.next
            else:
                head = head.next
            if not head:
                break
        return a

205 同构字符串

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        d = {}
        for i in range(len(s)):
            if s[i] not in d:
                if t[i] in d.values():
                    return False
                d[s[i]] = t[i]
            elif t[i]!=d[s[i]]:
                return False
        return True

213 打家劫舍 II

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)<4:
            return max(nums)
        dp1 = [0]*(len(nums)-1)
        dp1[0] = nums[0]
        dp1[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)-1):
            dp1[i] = max(dp1[i-1],nums[i]+dp1[i-2])
        dp2 = [0]*(len(nums)-1)
        dp2[0] = nums[1]
        dp2[1] = max(nums[1],nums[2])
        for i in range(3,len(nums)):
            dp2[i-1] = max(dp2[i-2],nums[i]+dp2[i-3])
        return max(dp1[-1],dp2[-1])

217 存在重复元素

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums)!=len(set(nums))

225 用队列实现栈

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.a = []
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        b=[]
        while len(self.a)>0:
            b.insert(0,self.a.pop())
        self.a.insert(0,x)
        while len(b)>0:
            self.a.insert(0,b.pop())
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.a.pop()
        

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.a[-1]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.a)==0

227 基本计算器 II

class Solution:
    def calculate(self, s: str) -> int:
        op = []
        num = []
        i = 0
        s = s.replace(' ','')
        while i<len(s):
            if s[i]>='0' and s[i]<='9':
                j=i
                while j<len(s) and s[j]>='0' and s[j]<='9':
                    j+=1
                num.append(int(s[i:j]))
                i = j-1
            elif s[i]=='-' or s[i]=='+':
                op.append(s[i])
            elif s[i]=='*':
                j = i+1
                while j<len(s) and s[j]>='0' and s[j]<='9':
                    j+=1
                num.append(num.pop()*int(s[i+1:j]))
                i = j-1
            elif s[i]=='/':
                j = i+1
                while j<len(s) and s[j]>='0' and s[j]<='9':
                    j+=1
                num.append(num.pop()//int(s[i+1:j]))
                i = j-1
            i+=1
        while len(op)>0:
            if op.pop(0)=='-':
                num.insert(0,num.pop(0)-num.pop(0))
            else:
                num.insert(0,num.pop(0)+num.pop(0))
        return num[0]

228 汇总区间

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        if len(nums)==0:
            return nums
        a = [str(nums[0])]
        last = nums[0]
        for i in range(1,len(nums)):
            if nums[i]>nums[i-1]+1:
                if last!=nums[i-1]:
                    a[-1] = a[-1]+"->"+str(nums[i-1])
                last = nums[i]
                a.append(str(nums[i]))
        if last<nums[-1]:
            a[-1] = a[-1]+"->"+str(nums[-1])
        return a

238 除自身以外数组的乘积

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [nums[0]]
        for i in range(1,len(nums)):
            res.append(res[-1]*nums[i])
        tmp = 1
        for i in range(len(nums)-1,0,-1):
            res[i] = res[i-1]*tmp
            tmp*=nums[i]
        res[0] = tmp
        return res

242 有效的字母异位词

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(list(s))==sorted(list(t))

258 各位相加

class Solution:
    def addDigits(self, num: int) -> int:
        if num==0:
            return 0
        return (num-1)%9+1

263 丑数

class Solution:
    def isUgly(self, num: int) -> bool:
        while num>0:
            if num%2==0:
                num/=2
            elif num%3==0:
                num/=3
            elif num%5==0:
                num/=5
            else:
                break
        return num==1

268 缺失数字

class Solution:
    def missingNumber(self, nums):
        n=len(nums)
        return (n*n+n)//2-sum(nums)

278 第一个错误的版本

class Solution:
    def firstBadVersion(self, n):
        start = 1
        end = n
        if isBadVersion(start):
            return 1
        middle = (start+end)//2
        while start<end-1:
            if isBadVersion(middle):
                end = middle
            else:
                start = middle
            middle = (start+end)//2
        if isBadVersion(start):
            return start
        return end

283 移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = len(nums)-1
        while i>=0:
            if nums[i]==0:
                nums.pop(i)
                nums.append(0)
            i-=1

290 单词规律

class Solution:
    def wordPattern(self, p, s):
        a=list(p)
        b=s.split(' ')
        if len(a)!=len(b):
            return False
        d={}
        f={}
        for i in range(len(a)):
            d[a[i]]=b[i]
            f[b[i]]=a[i]
        c=[d[i] for i in a]
        w=[f[i] for i in b]
        if ' '.join(c)!=s or ''.join(w)!=p:
            return False
        return True

292 Nim 游戏

class Solution:
    def canWinNim(self, n):
        if n%4==0:
            return False
        return True

299 猜数字游戏

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        a = 0
        b = 0
        d1 = {}
        d2 = {}
        for i in range(len(secret)):
            if secret[i] not in d1:
                d1[secret[i]] = [i]
            else:
                d1[secret[i]].append(i)
            if guess[i] not in d2:
                d2[guess[i]] = [i]
            else:
                d2[guess[i]].append(i)
        x = set(d1.keys()) & set(d2.keys())
        for i in list(x):
            a+=len(set(d1[i])&set(d2[i]))
            if len(d1[i])<len(d2[i]):
                b+=len(set(d1[i])-set(d2[i]))
            else:
                b+=len(set(d2[i])-set(d1[i]))
        return str(a)+"A"+str(b)+"B"

303 区域和检索 - 数组不可变

class NumArray:

    def __init__(self, nums: List[int]):
        self.n = nums

    def sumRange(self, i: int, j: int) -> int:
        return sum(self.n[i:j+1])

307 区域和检索 - 数组可修改

class NumArray:

    def __init__(self, nums: List[int]):
        self.n = nums

    def update(self, i: int, val: int) -> None:
        self.n[i] = val

    def sumRange(self, i: int, j: int) -> int:
        return sum(self.n[i:j+1])

343 整数拆分

class Solution:
    def integerBreak(self, n: int) -> int:
        a = [0]*n
        a[0] = 1
        a[1] = 1
        for i in range(2,n):
            res = 0
            for j in range(i):
                res = max(res,a[j]*(i-j),(j+1)*(i-j))
            a[i] = res
        return a[-1]

344 反转字符串

class Solution:
    def reverseString(self, s: List[str]) -> None:
        i = 0
        j = len(s)-1
        while i<j:
            s[i],s[j] = s[j],s[i]
            i+=1
            j-=1

345 反转字符串中的元音字母

class Solution:
    def reverseVowels(self, s: str) -> str:
        a = ["a","e","i","o","u","A","E","I","O","U"]
        s = list(s)
        i,j = 0,len(s)-1
        while i<j:
            while i<len(s) and s[i] not in a:
                i+=1
            while j>0 and s[j] not in a:
                j-=1
            if i<j:
                s[i],s[j] = s[j],s[i]
                i+=1
                j-=1
        return ''.join(s)

349 两个数组的交集

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

367 有效的完全平方数

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num==1:
            return True
        left = 2
        right = num//2
        while left<=right:
            mid = (left+right)//2
            s = mid*mid
            if mid==left or mid==right:
                return s==num
            if s==num:
                return True
            elif s>num:
                right = mid
            else:
                left = mid
        return False

371 两整数之和

class Solution:
    def getSum(self, a: int, b: int) -> int:
        return sum((a,b))

376 摆动序列

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums)<2:
            return len(nums)
        flag = [0,0]
        wmax = 1
        for i in range(1,len(nums)):
            if nums[i]>nums[i-1]:
                flag.append(1)
                if flag[-1]!=flag[-2]:
                    wmax+=1
            elif nums[i]<nums[i-1]:
                flag.append(-1)
                if flag[-1]!=flag[-2]:
                    wmax+=1
        return wmax

383 赎金信

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if not ransomNote:
            return True
        a = list(ransomNote)
        b = list(magazine)
        for i in a:
            if i not in b:
                return False
            b.pop(b.index(i))
        return bool(a)

389 找不同

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = sorted(s)
        t = sorted(t)
        for i in range(len(s)):
            if s[i]!=t[i]:
                return t[i]
        return t[-1]

391 完美矩形

class Solution:
    def isRectangleCover(self, rectangles):
        m=set()
        size=0
        for a,b,c,d in rectangles:
            size+=(d-b)*(c-a)
            for r in [(a,b),(a,d),(c,d),(c,b)]:
                if r not in m:
                    m.add(r)
                else:
                    m.remove(r)
        if len(m)!=4:
            return False
        m=list(m)
        xs=min(m[0][0],m[1][0],m[2][0],m[3][0])
        xm=max(m[0][0],m[1][0],m[2][0],m[3][0])
        ys=min(m[0][1],m[1][1],m[2][1],m[3][1])
        ym=max(m[0][1],m[1][1],m[2][1],m[3][1])
        if size!=(xm-xs)*(ym-ys):
            return False
        return True

412 Fizz Buzz

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        a = []
        for i in range(1,n+1):
            if i%15==0:
                a.append("FizzBuzz")
            elif i%5==0:
                a.append("Buzz")
            elif i%3==0:
                a.append("Fizz")
            else:
                a.append(str(i))
        return a

415 字符串相加

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        if len(num1)>len(num2):
            num2 = "0"*(len(num1)-len(num2))+num2
        else:
            num1 = "0"*(len(num2)-len(num1))+num1
        a = ""
        c = 0
        for i in range(len(num1)-1,-1,-1):
            t = int(num1[i])+int(num2[i])
            if c:
                t+=1
                c = 0
            if t>9:
                c = 1
                a = str(t-10)+a
            else:
                a = str(t)+a
        if c:
            a = "1"+a
        return a

429 N叉树的层序遍历

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        s = [root]
        last = 0
        p = n = 0
        res = []
        while s:
            res.append([])
            while p<=last:
                k = s.pop(0)
                res[-1].append(k.val)
                p+=1
                for j in k.children:
                    s.append(j)
                    n+=1
            last = n
        return res

434 字符串中的单词数

class Solution:
    def countSegments(self, s: str) -> int:
        return len([i for i in s.split(" ") if len(i)>0])

441 排列硬币

class Solution:
    def arrangeCoins(self, n: int) -> int:
        L = 0
        R = 99999999
        while L<=R:
            M = (L+R)//2
            if L==R-1:
                break
            if (M*M+M)//2>n:
                R = M
            else:
                L = M
        if (L*L+L)//2<=n:
            return L
        return R

442 数组中重复的数据

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            while nums[i]!=i+1 and nums[i]>0:
                if nums[nums[i]-1]==nums[i]:
                    res.append(nums[i])
                    nums[i] = 0
                else:
                    t = nums[i]
                    nums[i] = nums[t-1]
                    nums[t-1] = t
        return res

452 用最少数量的箭引爆气球

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points)<2:
            return len(points)
        p = sorted(points,key=lambda x:x[1])
        last = -1
        count = 0
        for i in p:
            if i[0]>last:
                last = i[1]
                count+=1
        return count

453 最小移动次数使数组元素相等

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        return sum(nums)-min(nums)*len(nums)

455 分发饼干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)
        i,j,k = 0,0,0 
        while i<len(s) and j<len(g):
            if s[i]>=g[j]:
                j+=1
                k+=1
            i+=1
        return k

494 目标和

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        d1 = {}
        d2 = {}
        if nums[0]==0:
            d1[0] = 2
        else:
            d1[nums[0]] = 1
            d1[-nums[0]] = 1
        for i in nums[1:]:
            k = list(d1.keys())
            for j in k:
                if j+i in d2:
                    d2[j+i]+=d1[j]
                else:
                    d2[j+i] = d1[j]
                if j-i in d2:
                    d2[j-i]+=d1[j]
                else:
                    d2[j-i] = d1[j]
            d1 = d2
            d2 = {}
        if S in d1:
            return d1[S]
        return 0

495 提莫攻击

class Solution:
    def findPoisonedDuration(self, timeSeries, duration):
        m=0
        end=-1
        for t in timeSeries:
            if t>=end:
                m+=duration
                end = t+duration
            elif t+duration<=end:
                continue
            else:
                m+=duration-end+t
                end = t+duration
        return m

500 键盘行

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        a = [['q','w','e','r','t','y','u','i','o','p'],
            ['a','s','d','f','g','h','j','k','l'],
            ['z','x','c','v','b','n','m']]
        r = []
        for w in words:
            s = set(w.lower())
            for i in a:
                if s.issubset(i):
                    r.append(w)
                    break
        return r

509 斐波那契数

class Solution:
    def fib(self, N: int) -> int:
        if N==0:
            return 0
        a=b=1
        for i in range(N-2):
            a,b = b,a+b
        return b

515 在每个树行中找最大值

class Solution:
    def largestValues(self, root):
        m=[]
        mm=[]
        tmp1=[]
        if root:
            tmp1.append(root)
        tmp2=[]
        while len(tmp1)>0:
            for r in tmp1:
                mm.append(r.val)
                if r.left:
                    tmp2.append(r.left)
                if r.right:
                    tmp2.append(r.right)
            m.append(max(mm))
            mm=[]
            tmp1=tmp2
            tmp2=[]
        return m

530 二叉搜索树的最小绝对差

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        a = [root]
        b = []
        while a:
            k = a.pop()
            if not k:
                continue
            b.append(k.val)
            a.append(k.left)
            a.append(k.right)
        b.sort()
        m = -1
        for i in range(1,len(b)):
            if b[i]-b[i-1]<m or m<0:
                m = b[i]-b[i-1]
        return m

540 有序数组中的单一元素

class Solution:
    def singleNonDuplicate(self, n):
        if len(n)==1:
            return n[0]
        a=len(n)//2
        if n[a]==n[a+1]:
            if a%2==1:
                return self.singleNonDuplicate(n[:a])
            else:
                return self.singleNonDuplicate(n[a+2:])
        elif n[a]==n[a-1]:
            if a%2==0:
                return self.singleNonDuplicate(n[:a-1])
            else:
                return self.singleNonDuplicate(n[a+1:])
        else:
            return n[a]

554 砖墙

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        d = {}
        for w in wall:
            c = 0
            for i in range(len(w)-1):
                c+=w[i]
                if c in d:
                    d[c]+=1
                else:
                    d[c] = 1
        if not d:
            return len(wall)
        m = max(d.values())
        return len(wall)-m

559 N叉树的最大深度

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        a = [root]
        b = []
        d = 1
        while a:
            for i in a:
                if i and i.children:
                    b.extend(i.children)
            if b:
                d+=1
                a,b = b,[]
            else:
                break
        return d

583 两个字符串的删除操作

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for i in range(len(word1)+1)] for j in range(len(word2)+1)]
        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i]==word2[j]:
                    dp[j+1][i+1] = dp[j][i]+1
                else:
                    dp[j+1][i+1] = max(dp[j][i+1],dp[j+1][i])
        return len(word1)+len(word2)-2*dp[len(word2)][len(word1)]

593 有效的正方形

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        d = [(p1[0]-p2[0])**2+(p1[1]-p2[1])**2,
            (p1[0]-p3[0])**2+(p1[1]-p3[1])**2,
            (p1[0]-p4[0])**2+(p1[1]-p4[1])**2,
            (p2[0]-p3[0])**2+(p2[1]-p3[1])**2,
            (p2[0]-p4[0])**2+(p2[1]-p4[1])**2,
            (p3[0]-p4[0])**2+(p3[1]-p4[1])**2]
        print(d)
        if len(set(d))!=2 or (d.count(d[0])!=2 and d.count(d[0])!=4):
            return False
        return True

595 大的国家

SELECT name, population, area from World where area>3000000 OR population>25000000;

596 超过5名学生的课

SELECT class FROM courses GROUP BY class Having count(DISTINCT student)>=5;

620 有趣的电影

SELECT * FROM cinema WHERE description!='boring' AND id%2=1 ORDER BY rating DESC;

627 交换工资

UPDATE salary SET sex=IF(sex='m','f','m');

633 平方数之和

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        L = 0
        R = int(math.sqrt(c))
        while L<=R:
            m = L**2+R**2
            if m==c:
                return True
            elif m<c:
                L+=1
            else:
                R-=1
        return False

641 设计循环双端队列

class MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.nums = []
        self.limit = k
        

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if len(self.nums)==self.limit:
            return False
        self.nums.insert(0,value)
        return True
        

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if len(self.nums)==self.limit:
            return False
        self.nums.append(value)
        return True
        

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if len(self.nums)==0:
            return False
        del self.nums[0]
        return True
        

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if len(self.nums)==0:
            return False
        del self.nums[-1]
        return True
        

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        if len(self.nums)==0:
            return -1
        return self.nums[0]
        

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        if len(self.nums)==0:
            return -1
        return self.nums[-1]
        

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        if len(self.nums)==0:
            return True
        return False
        

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        if len(self.nums)==self.limit:
            return True
        return False

657 机器人能否返回原点

class Solution:
    def judgeCircle(self, moves):
        x=0
        y=0
        for i in moves:
            if i=='L':
                x+=1
            elif i=='R':
                x-=1
            elif i=='U':
                y+=1
            else:
                y-=1
        if x==0 and y==0:
            return True
        return False

670 最大交换

class Solution:
    def maximumSwap(self, num: int) -> int:
        if num<10:
            return num
        s = list(str(num))
        m = []
        k = s[-1]
        for i in range(len(s)-1,0,-1):
            k = max(k,s[i])
            m.insert(0,k)
        for i in range(len(s)-1):
            if s[i]<m[i]:
                for j in range(len(s)-1,i,-1):
                    if s[j]==m[i]:
                        break
                s[i], s[j] = s[j], s[i]
                break
        return int(''.join(s))

678 有效的括号字符串

class Solution:
    def checkValidString(self, s: str) -> bool:
        a = set()
        b = set()
        a.add(0)
        for i in s:
            if i=='(':
                for j in a:
                    b.add(j+1)
            elif i==')':
                for j in a:
                    if j>0:
                        b.add(j-1)
            else:
                for j in a:
                    b.add(j)
                    b.add(j+1)
                    if j>0:
                        b.add(j-1)
            a = b
            b = set()
        return (0 in a)

680 验证回文字符串 Ⅱ

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i,j = 0,len(s)-1
        c = True
        f = False
        while i<j:
            if s[i]!=s[j]:
                if c:
                    c = False
                    i+=1
                else:
                    f = True
                    break
            else:
                i+=1
                j-=1
        if f:
            i,j = 0,len(s)-1
            while i<j:
                if s[i]!=s[j]:
                    if not c:
                        c = True
                        j-=1
                    else:
                        return False
                else:
                    i+=1
                    j-=1
        return True

695 岛屿的最大面积

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    s = [(i,j)]
                    area = 0
                    while s:
                        p,q = s.pop()
                        if grid[p][q]==0:
                            continue
                        area+=1
                        grid[p][q] = 0
                        if p>0 and grid[p-1][q]==1:
                            s.append((p-1,q))
                        if p<len(grid)-1 and grid[p+1][q]==1:
                            s.append((p+1,q))
                        if q>0 and grid[p][q-1]==1:
                            s.append((p,q-1))
                        if q<len(grid[0])-1 and grid[p][q+1]==1:
                            s.append((p,q+1))
                    m = max(m,area)
        return m

704 二分查找

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums)-1
        middle = (start+end)//2
        while start<end-1:
            if nums[middle]==target:
                return middle
            elif nums[middle]>target:
                end = middle
                middle = (start+end)//2
            else:
                start = middle
                middle = (start+end)//2
        if nums[start]==target:
            return start
        elif nums[end]==target:
            return end
        return -1

739 每日温度

class Solution:
    def dailyTemperatures(self, t):
        a=[33333]*101
        m=[]
        for i in range(len(t)-1,-1,-1):
            if i<a[t[i]]:
                a[t[i]]=i
            if t[i]==100:
                m.append(0)
            else:
                k=min(a[t[i]+1:])
                if k==33333:
                    m.append(0)
                else:
                    m.append(k-i)
        m.reverse()
        return m

744 寻找比目标字母大的最小字母

class Solution:
    def nextGreatestLetter(self, letters, target):
        a = list(set(letters))
        a.sort()
        for i in a:
            if i>target:
                return i
        return a[0]

766 托普利茨矩阵

class Solution:
    def isToeplitzMatrix(self, m):
        for i in range(len(m[0])):
            s=m[0][i]
            p=0
            q=i
            while p<len(m) and q<len(m[0]):
                if m[p][q]!=s:
                    return False
                p+=1
                q+=1
        for i in range(len(m)):
            s=m[i][0]
            p=i
            q=0
            while p<len(m) and q<len(m[0]):
                if m[p][q]!=s:
                    return False
                p+=1
                q+=1
        return True

781 森林中的兔子

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        a = {}
        for i in answers:
            if i+1 in a:
                a[i+1]+=1
            else:
                a[i+1] = 1
        res = 0
        for i in a:
            if a[i]<=i:
                res+=i
            else:
                res+=a[i]//i*i
                if a[i]%i>0:
                    res+=i
        return res

783 二叉搜索树节点最小距离

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        a = [root]
        b = []
        while a:
            k = a.pop()
            if not k:
                continue
            b.append(k.val)
            a.append(k.left)
            a.append(k.right)
        b.sort()
        m = -1
        for i in range(1,len(b)):
            if b[i]-b[i-1]<m or m<0:
                m = b[i]-b[i-1]
        return m

794 有效的井字游戏

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        cx = co = 0
        xwin = owin = False
        for i in range(3):
            for j in board[i]:
                if j=='X':
                    cx+=1
                elif j=='O':
                    co+=1
        if co>cx or cx>co+1:
            return False
        for i in range(3):
            if board[i][0]==board[i][1]==board[i][2]:
                if board[i][0]=='X':
                    xwin = True
                elif board[i][0]=='O':
                    owin = True
            if board[0][i]==board[1][i]==board[2][i]:
                if board[0][i]=='X':
                    xwin = True
                elif board[0][i]=='O':
                    owin = True
        if board[0][0]==board[1][1]==board[2][2]:
                if board[0][0]=='X':
                    xwin = True
                elif board[0][0]=='O':
                    owin = True
        if board[0][2]==board[1][1]==board[2][0]:
                if board[1][1]=='X':
                    xwin = True
                elif board[1][1]=='O':
                    owin = True
        if xwin and owin:
            return False
        if (xwin and cx==co+1) or (owin and cx==co):
            return True
        if not xwin and not owin:
            return True
        return False

804 唯一摩尔斯密码词

class Solution:
    def uniqueMorseRepresentations(self, words):
        a=[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        m=[]
        for i in words:
            k=list(i)
            p=""
            for j in k:
                p+=a[ord(j)-97]
            m.append(p)
        return len(set(m))

807 保持城市天际线

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        m = [0]*len(grid)
        n = [0]*len(grid[0])
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]>m[i]:
                    m[i] = grid[i][j]
                if grid[i][j]>n[j]:
                    n[j] = grid[i][j]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                res+=min(m[i],n[j])-grid[i][j]
        return res

817 链表组件

class Solution:
    def numComponents(self, head, G):
        a=[0]*10000
        for i in G:
            a[i]=1
        flag=0
        count=0
        while head:
            if a[head.val]==1 and flag==0:
                flag=1
            elif a[head.val]==0 and flag==1:
                flag=0
                count+=1
            head=head.next
        if flag==1:
            count+=1
        return count

830 较大分组的位置

class Solution:
    def largeGroupPositions(self, S: str) -> List[List[int]]:
        if len(S)<3:
            return []
        res = []
        n = S[0]
        count = 0
        for i in range(len(S)):
            if S[i]!=n:
                if count>=3:
                    res.append([i-count,i-1])
                n = S[i]
                count = 1
            else:
                count+=1
        if count>=3:
            res.append([len(S)-count,len(S)-1])
        return res

832 翻转图像

class Solution:
    def flipAndInvertImage(self, A):
        a=[]
        for k in A:
            k.reverse()
            a.append([0 if i==1 else 1 for i in k])
        return a

844 比较含退格的字符串

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        a = []
        b = []
        for i in S:
            if i=='#':
                if len(a)>0:
                    a.pop()
            else:
                a.append(i)
        for i in T:
            if i=='#':
                if len(b)>0:
                    b.pop()
            else:
                b.append(i)
        return a==b

852 山脉数组的峰顶索引

class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        for i in range(1,len(A)):
            if A[i]<A[i-1]:
                return i-1

856 括号的分数

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        a = []
        for i in S:
            if i=='(':
                a.append(i)
            elif i==')':
                if a[-1]=='(':
                    a.pop()
                    a.append(1)
                    while len(a)>1 and type(a[-1])==type(a[-2])==int:
                        a[-2] += a[-1]
                        a.pop()
                else:
                    t = a[-1]
                    a.pop()
                    a.pop()
                    a.append(2*t)
                    while len(a)>1 and type(a[-1])==type(a[-2])==int:
                        a[-2] += a[-1]
                        a.pop()
        return a[0]

860 柠檬水找零

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        d={5:0,10:0}
        for i in bills:
            if i==5:
                d[5]+=1
            elif i==10:
                if d[5]==0:
                    return False
                d[10]+=1
                d[5]-=1
            else:
                if d[5]==0:
                    return False
                if d[10]==0:
                    if d[5]<3:
                        return False
                    else:
                        d[5]-=3
                else:
                    d[10]-=1
                    d[5]-=1
        return True

867 转置矩阵

class Solution:
    def transpose(self, A: List[List[int]]) -> List[List[int]]:
        return [[k[i] for k in A] for i in range(len(A[0]))]

868 二进制间距

class Solution:
    def binaryGap(self, N: int) -> int:
        s = bin(N)
        m=start=0
        for i in range(len(s)):
            if s[i]=='1':
                start=i
                break
        for j in range(i+1,len(s)):
            if s[j]=='1':
                m=max(m,j-start)
                start=j
        return m

869 重新排序得到 2 的幂

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        if N==1:
            return True
        a = int(''.join(sorted(list(str(N)))))
        for i in range(2,30):
            b = int(''.join(sorted(list(str(2**i)))))
            if a==b and len(str(N))==len(str(2**i)):
                return True
        return False

872 叶子相似的树

class Solution:
    def leafSimilar(self, root1, root2):
        a=[]
        b=[]
        def scan(r,k):
            if r:
                if r.left:
                    scan(r.left,k)
                if r.right:
                    scan(r.right,k)
                if r.left==None and r.right==None:
                    k.append(r.val)
        scan(root1,a)
        scan(root2,b)
        if len(a)!=len(b):
            return False
        for i in range(len(a)):
            if a[i]!=b[i]:
                return False
        return True

877 石子游戏

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # piles.length是偶数，所以先手必赢
        return True

896 单调数列

class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        c = 0
        for i in range(1,len(A)):
            if A[i]>A[i-1]:
                if c==0:
                    c = 1
                elif c==-1:
                    return False
            elif A[i]<A[i-1]:
                if c==0:
                    c = -1
                elif c==1:
                    return False
        return True

912 排序数组

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

925 长按键入

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i,j = 0,0
        while j<len(typed):
            if name[i]==typed[j]:
                if i==len(name)-1:
                    return True
                i+=1
                j+=1
            else:
                j+=1
        return False

930 和相同的二元子数组

class Solution:
    def numSubarraysWithSum(self, A: List[int], S: int) -> int:
        start = 0
        count = 0
        ans = 0
        for i in range(len(A)):
            count += A[i]
            if count<S:
                continue
            else:
                while count>S and start<i:
                    count -= A[start]
                    start += 1
                if count==S:
                    ans += 1
                    for j in range(start,i):
                        if A[j]==1:
                            break
                        ans += 1
        return ans

935 骑士拨号器

class Solution:
    def knightDialer(self, N: int) -> int:
        a = [1,1,1,1,1,1,1,1,1,1]
        b = [0,0,0,0,0,0,0,0,0,0]
        for i in range(N-1):
            b[0] = a[4]+a[6]
            b[1] = a[6]+a[8]
            b[2] = a[7]+a[9]
            b[3] = a[4]+a[8]
            b[4] = a[0]+a[3]+a[9]
            b[6] = a[0]+a[1]+a[7]
            b[7] = a[2]+a[6]
            b[8] = a[1]+a[3]
            b[9] = a[2]+a[4]
            a = b
            b = [0,0,0,0,0,0,0,0,0,0]
        return sum(a)%(10**9+7)

941 有效的山脉数组

class Solution:
    def validMountainArray(self, A: List[int]) -> bool:
        if len(A)<2:
            return False
        stage = 0
        up = False
        for i in range(1,len(A)):
            if stage==0 and A[i]>A[i-1]:
                up = True
                continue
            elif stage==0 and A[i]<A[i-1] and up:
                stage = 1
                continue
            elif stage==1 and A[i]<A[i-1]:
                continue
            else:
                return False
        return stage==1

946 验证栈序列

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if len(pushed)==0:
            return len(popped)==0
        a = [pushed[0]]
        i = 1
        j = 0
        while True:
            if len(a)==0:
                if i==len(pushed):
                    break
                a.append(pushed[i])
                i+=1
            elif a[-1]==popped[j]:
                a.pop()
                j+=1
            else:
                if i==len(pushed):
                    break
                a.append(pushed[i])
                i+=1
        return len(a)==0

1003 检查替换后的词是否有效

class Solution:
    def isValid(self, S: str) -> bool:
        if not S:
            return False
        m = 0
        while len(S)!=m:
            m = len(S)
            S = S.replace('abc','')
        return len(S)==0

1014 最佳观光组合

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        m = A[0]
        r = 0
        for i in range(1,len(A)):
            r = max(r,m+A[i]-i)
            m = max(m,A[i]+i)
        return r

1021 删除最外层的括号

class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        res = ""
        start = 0
        count = 0
        for i in range(len(S)):
            if S[i]=='(':
                count+=1
            else:
                count-=1
            if count==0:
                if start+1<=i:
                    res+=S[start+1:i]
                start=i+1
        return res

1023 驼峰式匹配

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        a = []
        for i in queries:
            m,n,fa,fb = 0,0,0,0
            while True:
                if fb==0 and i[m]==pattern[n]:
                    if m==len(i)-1 and n==len(pattern)-1:
                        a.append(True)
                        break
                    if n==len(pattern)-1:
                        fb=1
                        m+=1
                    else:
                        m+=1
                        n+=1
                else:
                    if m<len(i) and i[m]>='A' and i[m]<='Z':
                        a.append(False)
                        break
                    if m==len(i)-1:
                        fa=1
                    if fa and fb:
                        a.append(True)
                        break
                    if fa and not fb:
                        a.append(False)
                        break
                    m+=1
        return a

1025 除数博弈

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N%2==0

1249 移除无效的括号

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        a = []
        b = []
        pos = 0
        for i in range(len(s)):
            if s[i]=='(':
                pos+=1
                a.append(s[i])
                b.append(i)
            elif s[i]==')':
                if len(a)>0 and pos>0:
                    a.pop()
                    b.pop()
                    pos-=1
                else:
                    a.append(s[i])
                    b.append(i)
        res = ''
        for i in range(len(s)):
            if i not in b:
                res+=s[i]
        return res

1291 顺次数

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        for i in range(len(str(low)),len(str(high))+1):
            base = int(''.join([str(i) for i in range(1,i+1)]))
            agg = int('1'*i)
            if low<=base<=high:
                res.append(base)
            for j in range(9-i):
                base+=agg
                if low<=base<=high:
                    res.append(base)
        return res

1299 将每个元素替换为右侧最大元素

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        if len(arr)==0:
            return []
        if len(arr)==1:
            return [-1]
        a = [-1]
        m = arr[-1]
        for i in range(len(arr)-2,-1,-1):
            a.insert(0,m)
            if m<arr[i]:
                m = arr[i]
        return a

1304 和为零的N个唯一整数

class Solution:
    def sumZero(self, n: int) -> List[int]:
        a = []
        for i in range(n-1):
            a.append(i)
        a.append(sum(a)*(-1))
        return a

1313 解压缩编码列表

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        res = []
        while nums:
            a = nums.pop(0)
            b = nums.pop(0)
            for i in range(a):
                res.append(b)
        return res

1337 方阵中战斗力最弱的 K 行

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        s = [sum(i) for i in mat]
        res = [0]
        for i in range(1,len(s)):
            for j in range(len(res)):
                if s[res[j]]>s[i]:
                    res.insert(j,i)
                    break
                elif j==len(res)-1:
                    res.append(i)
        return res[:k]

1380 矩阵中的幸运数

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        m = [999999]*len(matrix)
        n = [0]*len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]<m[i]:
                    m[i] = matrix[i][j]
                if matrix[i][j]>n[j]:
                    n[j] = matrix[i][j]
        res = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==m[i]==n[j]:
                    res.append(matrix[i][j])
        return res

1385 两个数组间的距离值

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        m = 0
        for i in arr1:
            acc = True
            for j in arr2:
                if abs(i-j)<=d:
                    acc = False
            if acc:
                m+=1
        return m

1394 找出数组中的幸运数

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        d = {}
        for i in arr:
            d[i] = d[i]+1 if i in d else 1
        res = -1
        for i in d:
            if d[i]==i and i>res:
                res = i
        return res

面试题 02.02 返回倒数第 k 个节点

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        c = 1
        p = head
        while p.next:
            p = p.next
            c+=1
        c = c-k
        while c:
            head = head.next
            c-=1
        return head.val

面试题17 打印从1到最大的n位数

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        a = []
        for i in range(1,int('9'*n)+1):
            a.append(i)
        return a

面试题 17.04 消失的数字

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.append(-1)
        for k in range(len(nums)):
            while nums[k]!=k and nums[k]!=-1:
                t = nums[k]
                nums[k] = nums[t]
                nums[t] = t
        for i in range(len(nums)):
            if nums[i]==-1:
                return i

面试题46 把数字翻译成字符串

class Solution:
    def translateNum(self, num: int) -> int:
        a = [1,1]
        s = str(num)
        for i in range(1,len(s)):
            if 9<int(s[i-1:i+1])<26:
                a.append(a[-1]+a[-2])
            else:
                a.append(a[-1])
        return a[-1]

面试题55 - I 二叉树的深度

class Solution:
    def maxDepth(self, root):
        def se(a,r):
            if r:
                return max(se(a+1,r.left),se(a+1,r.right),1)
            else:
                return a
        return se(0,root)

剑指 Offer 56 - I 数组中数字出现的次数

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        a = 0
        index = 0
        for i in nums:
            a ^= i
        while a%2==0:
            a >>= 1
            index += 1
        b = 0
        for i in nums:
            if (i>>index)%2==1:
                b ^= i
        return [b, a<<index^b]