【Leetcode第 308 场周赛】6160、6101、6102、6103

前言

这周的周赛比较简单，前面两道简单题，第三道题中等题，第四道题hard题

写出来了3道题，最后一道不会

一、Leetcode6060.和有限的最长子序列

模拟：简单题

6160. 和有限的最长子序列

这道题很容易想复杂，用dp或者dfs来做，反而把简单问题复杂化了。

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        res = [0 for _ in range(len(queries))]
        
        for i in range(len(queries)):
            cur_sum = 0
            for j in range(len(nums)):
                if cur_sum + nums[j] <= queries[i]:
                    cur_sum += nums[j]
                    res[i] += 1
                else: break
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

二、Leetcode6161. 从字符串中移除星号

普通stack：简单题

6161. 从字符串中移除星号

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            # if i == 0: return ''
            if s[i] != '*':
                stack.append(s[i])
            else:
                if stack:
                    stack.pop()
        return ''.join(stack)
1
2
3
4
5
6
7
8
9
10
11

三、Leetcode6162. 收集垃圾的最少总时间

模拟题：中等题

用个hash表来记录每种垃圾的出现次数，来判断垃圾车还需不需要继续开往下一个地点。

6162. 收集垃圾的最少总时间

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        mapp = defaultdict(int)
        for string in garbage:
            for j in range(len(string)):
                if string[j] == 'M':
                    mapp['M'] += 1
                elif string[j] == 'P':
                    mapp['P'] += 1
                elif string[j] == 'G':
                    mapp['G'] += 1
        def son(mapp, key):
            res = 0
            i = 0
            while mapp[key] != 0 and i < len(garbage):
                if 0 < i < len(garbage):
                    res += travel[i-1]   
                for j in range(len(garbage[i])):
                    if garbage[i][j] == key:
                        res += 1
                        mapp[key] -= 1
                i += 1
            return res
        
        res = 0
        g = ['M', 'P', 'G']
        for i in range(len(g)):  
            res += son(mapp, g[i])
        return res
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
29

四、Leetcode6103. 给定条件下构造矩阵

Leetcode6103. 给定条件下构造矩阵

hard题，拓扑排序，没写出来