题解

全排列、dp、zip()用法

通配符匹配

思路：

  • 创建一个 (len(p)+1)*(len(s)+1) 大小的数组lst，除了lst[0][0]外，其他的都为False
  • lst是显示状态的数组，lst[i][j]标识当前p[:i]能匹配s[:j]
  • 正式开始填充数组，首先数组初始化，用于填充第一行lst[0]。若当前p[i]==’‘ 且 lst[0][i-1]==True 的情况，lst[0][i]=True。 这个是覆盖``替代多个s中字符串的情况；
  • 开始比对s与p：如果p当前字符不是* ，lst[i][j]=lst[i-1][j-1]
  • 否则的话，lst[i][j]=lst[i-1][j](*覆盖了多个s字符的情况) or lst[i][j-1](*等于空串的情况)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def Solution(self, s: str, p: str) -> bool:
    lenp,lens=len(p),len(s)
   #初始化dp数组，以pattern+1长度为列，str+1长度为行
    lst=[[False] * lenp+1 for _ in range(lens+1)]
    #0行0列是加入的空字符，lst[0][0]=True意为空字符串匹配结果为True
    lst[0][0]=True

    #初始化lst[0]，如果p第一个字符为'*'的话，置为True，在后面的遍历中，这一列将全部为True
    for i in range(1,lenp+1):
        lst[0][i]=lst[0][i-1] and p[i-1]=='*'

    #从1开始遍历。根据p的不同有不同的结果：
    #p[j-1]等于字母，如果和s[i-1]匹配的话，当前p[:j]能和s[:i]匹配；
    #p[j-1]等于*，此时*可以替代一个空串，也可以替代多个字符。如果*为空串，检查lst[i][j-1]，即p[:j-1]和s[:i]是否匹配；如果*替代非空串，检查lst[i-1][j]，即延续s[:j]&p[:i]的匹配结果
    for i in range(1,lens+1):
        for j in range(1,lenp+1):
            if p[j-1]=='*':
                lst[i][j]= lst[i-1][j] or lst[i][j-1]
            else:
                lst[i][j]=lst[i-1][j-1]and (p[j-1]==s[i-1] or p[j-1]=='?')

    return lst[-1][-1]

是一个比较典型的dp，有比较典型的同类题型。和同类题型需要注意的地方在*

可被3整除

pic

思路

  • 一个数字，要么被3整除，要么余1或余2，只有这三种情况
  • 一开始的想法是：余1+余2 || 余2x3 || 余1x3 ，这三种组合能够变成一个被三整除的数，结果发现如果按这个思路求结果还需要用dp算最优解，不划算；
  • 看了别人的题解受到启发，整个nums相加后%3，若余1则减去数组中最小的余1数，余2减去最小的余2数，然后再返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(nums):
    res=sum(nums)
    #一个键值为余数、值为list的字典
    dic=defualtdict(list)
    for i in nums:
        dic[i%3].append(3)

    #查看nums的总和，看它的余数是多少。如果为2，减去min(余数为2的最小值,两个余数为1的值之和)，余数为1同理。
    if res%3==1:
        dic[1]=sorted(dic[1])
        return res-dic[1][0]
    elif res%3==2:
        dic[2]=sorted(dic[2])
        return res-dic[2][0]
    return res

受污染的二叉树

pic

思路：

  • 从根节点开始，为左右子节点赋值，迭代
  • 将当前节点值加入lst，lst为二叉树中出现的所有节点值
  • 当整个树遍历完之后，看看要找的值在不在lst中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class FindElements:
    lst=[]
    def fill(self,root,lst):
    '''重新填写被污染二叉树的值，并且把每个节点的值加入lst'''
        if root.val==-1:
            root.val=0
        lst.append(root.val)
        if root.left:
            root.left.val=root.val*2+1
            self.fill(root.left,lst)
        if root.right:
            root.right.val=root.val*2+2
            self.fill(root.right,lst)
    
    def __init__(self, root: TreeNode):
        self.lst=[]#必须有这一步！不然会非常混乱，不同测试用例的值会混在一起
        self.fill(root,self.lst)
        
    def find(self, target: int) -> bool:
    '''检查target是否在lst中'''
       #print(self.lst)
        return target in self.lst

这题蛮简单的，主要的问题在于lst的传递。一定要记得这种私有变量要在init函数里初始化，不然出事。

接雨水

pic
思路：

  • 下雨后能接到多少水，就是看有多少个坑。
  • 假如有一个[3,2,1,4]的高度图，一定是用[4]和[3]当边界，因为选其他任何两个的计算的结果都会被他们俩覆盖；
  • 所以从最高的柱子mid开始，以他为分界线向两边找最高的柱子，得到左边最高的柱子left和右边最高的柱子right
  • 计算 [left,mid]+[mid,right]=[left,right]的体积，得到当前最大值
  • 继续向left左边和right取最高的柱子，继续计算，直到得到总共水的体积。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def rsum(self,height,top,mid):
    '''迭代计算右边的雨水容积'''
        if not height:return 0#返回条件
        rtop=max(height)
        ind=height.index(rtop)
    
        sm=self.rsum(height[ind+1:],rtop,ind)#这里是传递从ind开始的height数组
        return min(rtop,top)*ind-sum(height[:ind])+sm#计算本段的雨水容积
    
    def lsum(self,height,top,mid):
        if not height:return 0
        ltop=max(height)
        ind =height.index(ltop)
        sm=self.lsum(height[:ind],ltop,ind)
        return min(ltop,top)*(len(height)-ind-1)-sum(height[ind+1:mid])+sm

    def trap(self, height: List[int]) -> int:
        if not height:return 0
        num,top,lens=0,max(height),len(height)
        mid=height.index(top)

        num+=self.lsum(height[:mid],top,mid)

        num+=self.rsum(height[mid+1:],top,mid)


        return num

这题其实思路比较简单，难的地方一个在怎么找左右最高(切片数组传参)，另一个在怎么判断迭代的出口。

螺旋矩阵


思路

  • 没什么好思路，直接用Python列表自带的函数和切片做的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> list:
        res=[]
        while matrix:
            res+=matrix[0]
            matrix.pop(0)
            if matrix:
                for i in matrix:
                    res+=[i[-1]]
                    i.pop()
            while [] in matrix:
                matrix.remove([])
                    
            if matrix:
                res+=matrix[-1][::-1]
                matrix.pop()
            if matrix:
                for i in matrix[::-1]:
                    res+=[i[0]]
                    i.pop(0)
            while [] in matrix:
                matrix.remove([])#每行的第一个和最后一个pop出来可能会产生空的列表，把它们除掉
        return res