题解

不同路径 合并区间 颜色分类 最小覆盖子串 子集

不同路径


思路

  • 看着就像个dp，一个格子多一点的上楼梯
  • 机器人从上往下，从左往右，所以说当前格子的路径数量等于左边格子的路径数量+上面格子的路径数量

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==0 or n==0:return 0
        #为了防止在第一行和第一列取上方格子和左边格子时溢出，加一行一列空的
        lst=[[0]*(m+1) for _ in range(n+1)]
        lst[0][1]=1
        for i in range(1,n+1):
            for j in range(1,m+1):
                lst[i][j]=lst[i-1][j]+lst[i][j-1]
        print(lst)
        return lst[-1][-1]

合并区间


思路

  • 首先先将区间的起点按照从小到大的顺序排序
  • 开始合并，如果当前区间的起点小于前一个区间的终点，将它们并起来
  • 最后得到合并区间的结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals,lens=sorted(intervals),len(intervals)
        if lens<1:return []
        if lens<1:return intervals
        res,i=[],0
        while i<lens:
            mx,j,tmp=intervals[i][1],i+1,[intervals[i][0]]
            while j<lens and intervals[j][0]<=mx:
                mx=max(intervals[j][1],mx)
                j+=1
            i=j
            tmp.append(mx)
            res.append(tmp)
            
        return res

颜色分类


思路

  • 一个排序，练一练快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums)<=1:return nums
        def ksort(l,r,nums):
            if l>=r:
                return
            key,left,right=nums[l],l,r
            while left<right:
                while left<right and key <nums[right]:
                    right-=1
                while left<right and key >=nums[left]:
                    left+=1
                nums[left],nums[right]=nums[right],nums[left]
            nums[l],nums[left]=nums[left],nums[l]
            ksort(l,left-1,nums)
            ksort(left+1,r,nums)
        ksort(0,len(nums)-1,nums)
        return nums

最小覆盖子串


思路

  • 滑动窗口
  • 窗口用left，right两个指针划定。左指针遍历到第一T中的字符时停住，右指针从左指针的位置向后移动，直到窗口中包含T中的所有字符，统计当前的字符数量。
  • 随后左指针向后移动，若窗口内的字符仍然包含T中的所有字符，更新窗口大小并继续向后移动
  • 若窗口内的字符没有完全包含T中的字符，左指针重新定住，右指针向后移动，重复第2、3步的操作。
  • 最后，直到右指针遍历完整个S字符，结束，返回最小的窗口大小

代码

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
class Solution:
    def isvalid(self,tmp,t):
    '''用tmp存储窗口的Counter，用t存储T的Counter，通过Counter的值能
    够查看tmp中是否包括T的所有字符'''
        for i in t.keys():
            if not tmp[i]:return False
            if tmp[i]<t[i]:return False
        return True

    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        #用Counter字典存储当前窗口字符串的{字符:频率}
        dic_t=Counter(t)
        l,r,lens=0,0,len(s)
        if lens<1:return ""
        tmp,m_s,m_len = Counter(),'',len(s)
        while r<lens:
            tmp[s[r]]+=1
            #当tmp中包括所有T的字符时，固定right指针，left指针向后并更新窗口大小
            while self.isvalid(tmp,dic_t):
                if m_len>=r-l:
                    m_len,m_s=r-l,s[l:r+1]
                tmp[s[l]]-=1
                l+=1
            r+=1
        return m_s#得到最小的窗口大小

子集


思路

  • 创建一个结果集，结果集中有一个[]元素，称结果集为basement
  • 从nums第一个元素开始，每次遍历到一个新的元素，就用basement中的元素与当前元素组合，就能得到当前元素的全所有结果
  • 将当前元素的结果加入结果集，为下一个元素basement
1
2
3
4
5
6
7
8
9
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res=[[]]#basement
        for i in nums:
            tmp=[]#当前字符的结果集
            for j in res:
                tmp.append(j+[i])
            res+=tmp
        return res