自娱自乐的精神乐园

余凯迪的博客

0%

发表于 分类于 ， 阅读次数：

5452. 判断能否形成等差数列

思路：
排序后取前两个数的差，依次检查是否满足等差。
注意提示中给出的数组长度大于等于2，所以不需要考虑边界条件。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr = sorted(arr)
        num = arr[1] - arr[0]
        pre = arr[1]
        for x in arr[2:]:
            if x - pre != num:
                return False
            pre = x
        return True

5453. 所有蚂蚁掉下来前的最后一刻

思路：
题目一开始看起来还是挺绕的，其实蚂蚁同时改变移动方向可以理解为都没有改变，或者理解为蚂蚁换了身份一直按照既定的方向行走。

1
2
3
4
5
6
7
class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        if len(left) == 0:
            return n-min(right)
        if len(right) == 0:
            return max(left)
        return max(n-min(right),max(left))

5454. 统计全 1 子矩形

思路：
依次遍历每一行，记录从该位置往上1的个数。例如：

  • 1 0 1
  • 1 1 0
  • 1 1 0

每一行的就是 [[1,0,1],[2,1,0],[3,2,0]]
然后我们依次统计每一行为底的矩形的个数。然后按照长度从1到n依次进行统计。

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
30
31
32
33
class Solution:
    def cal(self, arr):
        # 计算每一行为底的不同高度的矩形个数
        # max_row为从左到右该点连续1的最大个数
        max_row = [0] * len(arr)
        for i in range(len(arr)):
            if arr[i] == 0:
                max_row[i] = 0
            else:
                max_row[i] = max_row[i-1] + 1
        ans = 0
        # 一次遍历k*l矩形的个数，l为矩形为底的长度，从1到n
        for l in range(1,len(arr)+1):
            for i, m_r in enumerate(max_row):
                if m_r < l:
                    continue
                min_height = min(arr[i-l+1:i+1])
                ans += min_height
        return ans

    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        arr = [0] * n
        res = 0
        for line in mat:
            for i in range(n):
                if line[i] == 0:
                    arr[i] = 0
                else:
                    arr[i] += 1
            res += self.cal(arr)
        return res

5455. 最多 K 次交换相邻数位后得到的最小整数

思路：
直接贪心可以过。从高位开始，遍历k范围内的最小值，取最近的一个交换即可。
可能是数据集太水了，正确解法还不太确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minInteger(self, num: str, k: int) -> str:
        if k > len(num) **2:
            return ''.join(sorted(num))
        num = list(num)
        for i in range(len(num)):
            if k > 0:
                max_l = min(k+1,len(num)-i)
                min_num = min(num[i:i+max_l])
                if num[i] == min_num:
                    continue
                index = num[i:i+max_l].index(min_num) + i
                tmp = num[i:index]
                num[i] = min_num
                num[i+1:index+1] = tmp
                k -= index - i
            else:
                break
        return ''.join(num)

发表于 分类于 ， 阅读次数：

1496. 判断路径是否相交

思路：
按照题目意思模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isPathCrossing(self, path: str) -> bool:
        path_set = set([(0,0)])
        pre = (0,0)
        for p in path:
            x, y = pre
            if p == 'N':
                y += 1
            elif p == 'S':
                y -= 1
            elif p == 'E':
                x += 1
            elif p == 'W':
                x -= 1
            # print(x,y)
            if (x,y) in path_set:
                return True
            path_set.add((x,y))
            pre = (x,y)
        return False

1497. 检查数组对是否可以被 k 整除

思路：
使用一个长度为k的数组存储不同取模后余数的个数，如果恰好满足条件，

  1. 余数为i和余数为k-i的个数应该正好相等，0<i<k
  2. 余数为0的数字个数为偶数才能凑对。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        num_map = [0] * k
        for i in range(len(arr)):
            arr[i] = (arr[i] % k + k) % k
            num_map[arr[i]] += 1
        # print(num_map)
        if num_map[0] % 2:
            return False
        for i in range(1, k // 2+1):
            if num_map[i] != num_map[k-i]:
                return False
        return True

1498. 满足条件的子序列数目

思路：
子序列最值与顺序无关，首先对数组排序，然后使用双指针寻找满足条件长度为n的区间[min,num1,num2,…,max]，满足条件的非空子序列为$[min],[min,num1],[min,num1,num2],[min,num2]…[min,max]$，从$num1$到$max$一共n-1个数字中至少选择一个，一共有$2^{n-1}-1$个，加上[min]一共有$2^{n-1}$中情况。剩下的工作就是寻找满足条件的区间即可，使用双指针，指针两数之和小于等于target，左端点往后，否则右端点往前。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        i = 0
        j = len(nums) - 1
        res = 0
        while i <= j:
            if nums[i] + nums[j] <= target:
                res += 2**(j-i)
                i += 1
            else:
                j -= 1
        return res %(10**9+7)

1499. 满足不等式的最大值

思路：
由于题目中$x_i$严格单调递增，对于$j>i$，条件$y_i+y_j+|x_i-x_j|$可转化为$x_j+y_j+y_i-x_i$，因此对于任一点，取满足k范围中 $y_i-x_i$最大之即可。因此可使用单调队列实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        q = collections.deque()
        q.append((points[0], points[0][1] - points[0][0]))
        res = -1e9
        for point in points[1:]:
            # 不在区间范围内的点从队列中删除
            while len(q) and point[0] - q[0][0][0] > k:
                q.popleft()
            # 根绝当前点数据更新结果 
            if len(q):
                res = max(res, q[0][1]+ point[1]+point[0])
            # 将当前点加入单调队列中，需根据 yi-xi 满足单调性
            while len(q) and q[-1][1] < point[1] - point[0]:
                q.pop()
            q.append((point, point[1] - point[0]))
        return res

发表于 分类于 ， 阅读次数：

5420. 商品折扣后的最终价格

思路：
两重循环直接遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> res;
        for(int i=0;i<prices.size();++i){
            int tmp =prices[i];
            for(int j=i+1;j<prices.size();++j){
                if(prices[j] <= tmp){
                    tmp -= prices[j];
                    break;
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};

5422. 子矩形查询

思路：
简答直接赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class SubrectangleQueries {
public:
    vector<vector<int>> res;
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        res = rectangle;
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1;i<=row2;++i){
            for(int j=col1; j<= col2;++j){
                res[i][j] = newValue;
            }
        }
    }
    
    int getValue(int row, int col) {
        return res[row][col];
    }
};

思路：

发表于 分类于 ， 阅读次数：

5416. 检查单词是否为句中其他单词的前缀

思路：
直接遍历数组，取前缀匹配满足的第一个字符串即可。前缀匹配可自己手写或直接用接口。

1
2
3
4
5
6
7
8
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        res = -1
        for i, word in enumerate(sentence.split(' ')):
            if word.startswith(searchWord):
                res= i+1
                break
        return res

5417. 定长子串中元音的最大数目

思路：
维护滑动窗口中的元音字母数量即可。可先对字符串预处理标记，为元音字母的标记为1，否则为0。遍历窗口的右侧端点，直接对出滑动窗口的端点进行进出操作即可，体现为代码就是对应位置的加减标记操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        tmp = [0] * len(s)
        for i,x in enumerate(s):
            if x in ('a','e','i','o','u'):
                tmp[i] = 1
        res= sum(tmp[:k])
        t_sum = res
        for i in range(k,len(s)):
            t_sum -= tmp[i-k]
            t_sum += tmp[i]
            res = max(res, t_sum)
        return res

5418. 二叉树中的伪回文路径

思路：
容易想到，深度优先搜索记录路径上的所有节点，但结合题目回文串的特点，可以使用计数器来进行记录。
判断能够构成回文串，如果所有字符的个数都是偶数个或者仅一个字符个数是奇数个，肯定可以构成。如果有两个及两个以上的字符是奇数个，无法构成回文串。
至此，递归深搜即可。

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
30
31
32
33
34
35
36
37
38
39
40
41
# 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

from collections import Counter
class Solution:
    def __init__(self):
        self.counter =Counter()
        self.res = 0
        
    def judge(self):
        flag = False
        for x,val in self.counter.items():
            if val % 2 == 1:
                if not flag:
                    flag=True
                else:
                    return 
        self.res += 1
        
        
    def dfs(self,root):
        if root is None:
            return
        self.counter[root.val] += 1
        if root.left is None and root.right is None:
            # 对叶节点进行判断
            self.judge()
            self.counter[root.val] -= 1
            return 
        self.dfs(root.left)
        self.dfs(root.right)
        self.counter[root.val] -= 1
        
            
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res

5419. 两个子序列的最大点积

思路：
本题对序列的顺序有要求，很容易联想到最长公共子序列等经典DP问题。然后进一步思考，状态表示$dp[i][j]$ 标识两个序列截止位置i和位置j的最大点击。
状态转移：因为对序列点击的顺序有要求，可以根据最后一个位置是否参与点击来进行状态集合的切分，又由于求最大值，所有不必要求切分的时候每个集合严格不重复，只需要保证情况不遗漏即可。

可以看到max函数中囊括了所有的可能情况，注意不要遗漏的情况是$nums1[i]*nums2[j]$这一种情况，即不考虑前面序列的点积只取当前结尾的两个数字的点积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n= len(nums2)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # print(dp)
        dp[0][0] = nums1[0] * nums2[0]
        res = dp[0][0]
        for i in range(1,m):
            dp[i][0] = max(dp[i-1][0], nums1[i]*nums2[0])
            res = max(res,dp[i][0])
        for j in range(1,n):
            dp[0][j] = max(dp[0][j-1], nums1[0]*nums2[j])
            res= max(res,dp[0][j])
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+nums1[i]*nums2[j])
                dp[i][j] = max(dp[i][j], nums1[i]*nums2[j])
                res = max(res,dp[i][j])
        return res

发表于 更新于 分类于 ， 阅读次数：

通过这次周赛，对Python的喜爱又深了一层。

5412. 在既定时间做作业的学生人数

思路：
因为数据量较小并且只查询一次，直接遍历比较即可。
多次查询的话，考虑线段树。

1
2
3
4
5
6
7
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        res = 0
        for i in range(len(startTime)):
            if startTime[i]<=queryTime<=endTime[i]:
                res += 1
        return res

5413. 重新排列句子中的单词

思路：
Python大法好！！！

1
2
3
4
5
class Solution:
    def arrangeWords(self, text: str) -> str:
        items = text.lower().split(' ')
        items = sorted(items, key = lambda x:len(x))
        return ' '.join(items).capitalize()

5414. 收藏清单

思路：
看数据量不大，直接双重循环即可。运用Python中set相减的操作可快速判断是否为子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        for i in range(len(favoriteCompanies)):
            flag = False
            for j in range(len(favoriteCompanies)):
                if i==j:
                    continue
                if len(set(favoriteCompanies[i]) - set(favoriteCompanies[j])) == 0:
                    flag=True
            if not flag:
                res.append(i)
        return res

5415. 圆形靶内的最大飞镖数量

思路：
目前看到的做法都是两重循环，根据两个点确定最远的圆心位置，然后遍历判断个数。
通过向量运算确定最远圆心的位置，给出两点$A, B$，中点$m$向量$[(A.x+B.x)/2, (A.y+B.y)/2]$, 向量$\overrightarrow{AB}$为$[(A.x-B.x)/2, (A.y-B.y)/2]$，对应两点连线的单位法向量$\overrightarrow{MP}$为$[(A.y-B.y)/2/|AB|, -(A.x-B.x)/2/|AB|]$，$MP$对应的长度通过勾股定理$AP^2-MP^2$求出， 可得到对应的最远的圆心$P$。
图解
具体的图解可参考：图解圆心计算方法

题解评论区看到的比较精简的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        J = lambda o: sum(dist(p, o) <= r for p in points)
        m = 1
        for p1 in points:
            for p2 in points:
                if 0 < dist(p1, p2) <= 2 * r:
                    s = [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2]
                    d = [(p1[0] - p2[0]) / 2, (p1[1] - p2[1]) / 2]
                    z = sqrt(r ** 2 - d[0] ** 2 - d[1] ** 2) / hypot(*d)
                    # （d[1]*z, -d[0]*z）是向量垂直连线的向量
                    # p为圆心p1,p2两个点以r为圆心的两个圆的一个交点
                    p = [s[0] + d[1] * z, s[1] - d[0] * z]
                    m = max(m, J(p))
        return m

发表于 分类于 ， 阅读次数：

5396. 连续字符

思路：
用单独的变量记录前一个字符，判断当前字符和前一个字符是否相同，以此来进行计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxPower(self, s: str) -> int:
        pre = s[0]
        count = 1
        res = 1
        for x in s[1:]:
            if x == pre:
                count += 1
            else :
                res = max(res, count)
                pre = x
                count = 1
        res = max(res,count)
        return res

5397. 最简分数

思路：
比较简单，依次遍历2到n，找到其对应的所有互质的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def gcd(self,a,b):
        # 欧几里得算法求最大公约数
        return a if b==0 else self.gcd(b,a%b)
    
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for x in range(2,n+1):
            res.append("1/%d"%x)
            for i in range(2,x):
                if self.gcd(i,x) == 1:
                    res.append("%d/%d" % (i,x))
        return res

5398. 统计二叉树中好节点的数目

思路：
深度优先搜索的时候，将路径上遇到的最大值依次往下传递即可。

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
# 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 __init__(self):
        # 记录结果
        self.res = 0
    
    def dfs(self, root, max_num):
        if root is None:
            return 0
        max_num  = max(max_num, root.val)
        if root.val >= max_num:
            self.res += 1
        self.dfs(root.left, max_num)
        self.dfs(root.right, max_num)
        
    def goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        self.dfs(root, root.val)
        return self.res

5399. 数位成本和为目标值的最大数字

思路：
给定cost数组， 对target分解进行求解，很明显的搜索或者DP的思路。

  1. 对于cost相同的数字，只需要记录最大的那个即可。
  2. 对于给定的cost数组，任意target的方案的最大值是唯一的；深度优先搜索的时候，可以利用哈希记录不同target对应的值，及时终止递归。
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
30
31
class Solution:
    def dfs(self, target):
        if target in self.mm:
            return self.mm[target]
        if target < 0:
            # 返回0意味着target没有成功进行拆分
            return 0
        max_res =  0
        for key, val in self.cost_map.items():
            if target == key:
                max_res = max(val, max_res)
                continue
            tmp = val
            tmp_res = self.dfs(target-key)
            if tmp_res != 0:
                max_res = max(int(str(tmp)+str(tmp_res)), max_res)
                max_res = max(int(str(tmp_res)+str(tmp)), max_res)
        self.mm[target] = max_res
        return max_res
    
    def largestNumber(self, cost: List[int], target: int) -> str:
        self.cost_map = {}
        self.mm = {}
        for i,x in enumerate(cost):
            if x in self.cost_map:
                self.cost_map[x] = max(i+1, self.cost_map[x])
            else:
                self.cost_map[x] = i+1
        print(self.cost_map)
        res = self.dfs(target)
        return str(res)

发表于 分类于 ， 阅读次数：

5404. 用栈操作构建数组

思路：
如果一个数在最后的数组里，只push；不在最后的数组里面，先push再pop

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        res = []
        cur = 1
        for x in target:
            while cur != x:
                res.append('Push')
                res.append('Pop')
                cur += 1
            res.append('Push')
            cur += 1
        return res

5405. 形成两个异或相等数组的三元组数目

思路：
类似前缀和的想法，将前n个数的异或和存储下来，例如$sum[i]= arr[0] \land arr[1] \land … \land arr[i]$，那么从i到j的异或和为 $sum[i-1] \land sum[j]$，另外0和任何数x异或和为x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        pre_sum = [0]
        tmp = 0
        for x in arr:
            tmp ^= x
            pre_sum.append(tmp)
        res = 0
        for i in range(1,len(arr)):
            for k in range(i+1, len(arr)+1):
                for j in range(i+1,k+1):
                    a = pre_sum[i-1] ^ pre_sum[j-1]
                    b = pre_sum[k] ^ pre_sum[j-1]
                    if a==b:
                        res += 1
        return res

5406. 收集树上所有苹果的最少时间

思路：
类似层次遍历，对于每一个需要遍历的节点，从下向根节点回溯；如果该节点没有走过，结果加2，将该节点的父节点加入待遍历的节点；如果之前走过则，则忽略。
对于样例1

初始时 需要遍历(2,4,5);依次遍历，每次路径长度结果+2，然后将对应的父节点(1,0)加入待遍历节点；此时结果为6；
现在需要遍历(1,0),对于0已经是根节点，可以跳过；对于1，结果+2，将对应的父节点(0)加入待遍历节点；此时结果为8；
最后只剩下(0)，跳过。最终结果为8。

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
30
31
class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        res = 0
        # 记录每个节点对应的子节点和父节点关系
        children = collections.defaultdict(list)
        father = [-1]*len(hasApple)
        for x in edges:
            children[x[0]].append(x[1])
            father[x[1]] = x[0]
        has_check = set()
        apple_id = []
        for i,x in enumerate(hasApple):
            if x:
                apple_id.append(i)
        t = apple_id
        # 宽搜来进行从下向上依次遍历
        while len(t) > 0:
            # 记录每个节点的父节点
            tt = set()
            for x in t:
                # 当前节点为根节点，跳过
                if x==0:
                    continue
                # 当前节点没有以前没有遇到。将其父节点加入待遍历节点，当前节点置为已遍历到。
                elif x not in has_check:
                    tt.add(father[x])
                    has_check.add(x)
                    res += 2
            # print(t,tt,res)
            t = list(tt)
        return res

5407. 切披萨的方案数

思路：
比较容易想到的方法是直接搜索，递归实现深度优先搜索进行寻找。直接暴力搜索会超时，加入简单的剪枝操作和记忆化搜索可以过。之后想了会用动态规划应该是比较直观的方法，但是动态规划和记忆化的搜索本质上没有太大的区别，都是记录了中间过程的最优方案。
因为每次切完都是拿掉左边和上边的部分，剩余右下的部分，因此可以用剩余pizza的左上角的点的位置，来形象的表示切pizza的操作。
横向切pizza即改变左上角的横坐标，纵向切pizza即改变左上角的纵坐标。
搜索剪枝：对于剩余的pizza，如果横切和纵切所有的可能方案数比k-1小，那么不可能将当前剩余的pizza切成k份。
记忆化：对于同一个pizza，(i,j,k) 可以唯一标识 剩余的pizza需要被切成k份的方案数量。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def __init__(self):
        self.counter = {}
    
    def cut(self,pizza,i,j,k):
        # 记忆化搜索
        if (i,j,k) in self.counter:
            return self.counter[(i,j,k)]
        # 递归终止条件
        if k==1:
            # 当前pizza只需要分成1份，只需要判断是否包含苹果（'A'）
            for r in range(i,len(pizza)):
                for c in range(j,len(pizza[0])):
                    if pizza[r][c] == 'A':
                        # print(i,j,r,c)
                        self.res += 1
                        return 1
            return 0
        # 剪枝
        if len(pizza)-i-1 + len(pizza[0])-j-1 < k-1:
            return 0
        num = 0
        # 切的话需要满足上面或者左边的部分包含苹果（'A'）
        # 从上向下遍历，如果前面的行已经出现苹果，之后的行可以省略判断。因此用flag标志是否出现苹果。
        flag = False
        for m in range(i,len(pizza)-1):
            if flag:
                num += self.cut(pizza,m+1,j,k-1)
            else:
                for c in range(j,len(pizza[0])):
                    if pizza[m][c] == 'A':
                        flag = True
                        break
                if flag:
                    num += self.cut(pizza,m+1,j,k-1)
        flag = False
        for m in range(j,len(pizza[0])-1):
            if flag:
                num += self.cut(pizza,i,m+1,k-1)
            else:
                for r in range(i,len(pizza)):
                    if pizza[r][m] == 'A':
                        flag = True
                        break
                if flag:
                    num += self.cut(pizza,i,m+1,k-1)
        self.counter[(i,j,k)] = num
        return num

    def ways(self, pizza: List[str], k: int) -> int:
        return (self.cut(pizza,0,0,k) % int(1e9 + 7))
`

发表于 分类于 ， 阅读次数：

5400. 旅行终点站

思路：
直接使用dict记录出度即可

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import defaultdict
class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        res_map = defaultdict(int)
        tmp = set()
        for path in paths:
            tmp.add(path[0])
            tmp.add(path[1])
            res_map [path[0]] += 1
        for x in tmp:
            if res_map[x] ==0:
                return x
        return None

是否所有 1 都至少相隔 k 个元素

思路：
比较简单，直接模拟寻找即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        pre = -1
        for i,num in enumerate(nums):
            if num == 1:
                if pre==-1 or i-pre-1>=k:
                    pre = i
                else:
                    return False
        return True

5402. 绝对差不超过限制的最长连续子数组

思路：
使用两个单调队列来存储窗口内的最大值和最小值，使用left标志来表示队列的左侧端点。
窗口内的最大值使用降序队列存储，队列头为最大值；最小值使用升序队列存储，队列头为最小值；
遍历数组时，维数窗口内的两个队列，如果最大值减最小值大于limit，将窗口左端点向右移动，直到两个队列的最值满足小于limit。

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
30
31
32
class Solution {
public:
	int longestSubarray(vector<int> & nums, int limit) {
		deque<int> maxq;
		deque<int> minq;
		int n = nums.size();
		int ans = 1;
		int left = 0;
		for (int i = 0; i < n; ++i) {
			int tmp = nums[i];
			while (!maxq.empty() && nums[maxq.back()] < tmp) {
				maxq.pop_back();
			}
			while (!minq.empty() && nums[minq.back()] > tmp) {
				minq.pop_back();
			}
			maxq.push_back(i);
			minq.push_back(i);
			while ((nums[maxq.front()] - nums[minq.front()]) > limit) {
				++left;
                if (maxq.front()<left){
                    maxq.pop_front();
                }
                if (minq.front()<left){
                    minq.pop_front();
                }
			}
            ans = max(ans, i - left + 1);
		}
		return ans;
	}
};

5403. 有序矩阵中的第 k 个最小数组和

思路：
直接暴力求解就行。。每一行累加，然后取top k，继续加上下一行。

1
2
3
4
5
6
7
8
9
class Solution:
    def kthSmallest(self, mat: List[List[int]], k: int) -> int:
        res = mat[0][:k]
        for x in mat[1:]:
            tmp = []
            for t in x:
                tmp += [y+t for y in res]
            res = sorted(tmp)[:k]
        return res[-1]

发表于 分类于 ， 阅读次数：

1422. 分割字符串的最大得分

思路：
先统计数组中所有为1的数量num，使用l记录左边0的数量，然后从第一个位置开始，依次往后遍历。当前位置为0，则l加1，为1则num减1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxScore(self, s: str) -> int:
        num = 0
        for x in s:
            if x=='1':
                num += 1
        res = 0
        l = 0
        for x in s[:-1]:
            if x == '0':
                l += 1
                res = max(res, l+num)
            else :
                num -= 1
                res = max(res, l+ num)
        return res

1423. 可获得的最大点数

思路：
每次只能从两个端点取数，先假设从左端点取完k个，依次减少从左端点取的个数，减去左边尾部加上右侧端点，遍历取最大值。

1
2
3
4
5
6
7
8
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        num = sum(cardPoints[:k])
        res = num
        for i in range(1,k+1):
            num = num - cardPoints[k-i] + cardPoints[-i]
            res = max(num, res)
        return res

1424. 对角线遍历 II

思路：
容易想到对角线上的坐标之和为定值。此题直接模拟会超时，可以提前用哈希表存储好每条对角线上的值，最后直接对角线即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import defaultdict
class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        mm = defaultdict(list)
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                mm[i+j].append(nums[i][j])
        n = max(mm.keys())
        res = []
        for i in range(n+1):
            if len(mm[i])==0:
                continue
            for j in range(len(mm[i])-1 ,-1,-1):
                res.append(mm[i][j])
        return res

带限制的子序列和

思路：
很容易想到dp来求解, $dp[i]$ 表示以 $i$ 结尾的最大的子序列和。然后用单调队列存储区间窗口内最大的子序列和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = nums[0]
        dp = nums[:]
        dp[0] = nums[0]
        s = [0]
        for i in range(1, len(nums)):
            if i-s[0]>k:
                s.pop(0)
            dp[i] = nums[i]
            dp[i] = max(dp[i], dp[s[0]] + nums[i])
            while s and dp[i] >= dp[s[-1]]:
                s.pop()
            s.append(i)
            
            res = max(res, dp[i])
        return res

发表于 分类于 ， 阅读次数：

5388. 重新格式化字符串

思路：
统计字母个数n1和数字个数n2， 如果abs(n1-n2) > 1，不存在满足要求的字符串，返回空串。否则，相邻间隔一次插入就行。

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 reformat(self, s: str) -> str:
        res = ""
        ch=""
        num=""
        for x in s:
            if x>='a' and x<='z':
                ch += x
            else:
                num += x
        if abs(len(ch)-len(num)) >= 2 :
            return ""
        else:
            i=0
            
            while i<min(len(ch),len(num)) :
                if len(ch)>len(num) :
                    res += ch[i]+num[i]
                else:
                    res += num[i]+ch[i]
                i+=1
            if i>=len(ch) and i<len(num) :
                res += num[i]
            elif i>=len(num) and i<len(ch) :
                res += ch[i]
        return res

5389. 点菜展示表

思路：
以(tableNumberi, foodItemi)为键，利用哈希表（python中的字典）存储对应的数据；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import Counter
class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        food_set = set()
        table_set = set()
        table_food_dict = Counter()
        res = []
        for order in orders:
            _,table,food = order
            table = int(table)
            table_food_dict[(table, food)] += 1
            food_set.add(food)
            table_set.add(table)
        food_set= sorted(list(food_set))
        table_set= sorted(list(table_set))
        res.append(['Table']+food_set)
        for table in table_set:
            line = []
            line.append(str(table))
            for food in food_set:
                line.append(str(table_food_dict[(table,food)]))
            res.append(line)
        return res

5390. 数青蛙

思路：
利用数组记录每个字符的个数， 根据当前字符i计算需要的前一个字符i-1，前一个字符串个数减1，当前字符串个数加1。因为'c'是起始字符，前一个字符为'k'，特殊判断当前是否有字符为k，没有的话需要增加一只青蛙。查找过程中如果有字符个数小于0，直接返回。最后判断‘c’, ’r’, ’o’, ’a’ 四个字符的个数。

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
from collections import defaultdict
import queue
class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        map_ = {'c':0,'r':1,'o':2,'a':3,'k':4}
        num_list = [0] * 5
        res = 0
        for x in croakOfFrogs:
            num = map_[x]
            if num == 0:
                if num_list[4] <= 0:
                    res += 1
                    num_list[num] += 1
                else :
                    num_list[4] -= 1
                    num_list[0] += 1
            else:
                t = (num + 4) % 5
                num_list[t] -= 1
                num_list[num] += 1
            for i in range(5):
                if num_list[i] < 0:
                    return -1
        for i in range(4):
            if num_list[i] < 0:
                    return -1
        return res

5391. 生成数组

思路：
动态规划求解：设 dp[i][j][l] 为长度为 i，最大值为 j，search_cost 为 l 的数组的数目，则 $ \sum_{j=1}^{m}dp[n][j][k]$ 即为所求.
边界条件 dp[0][j][l] = dp[i][0][l] = dp[i][j][0] = 0，dp[1][j][1] = 1，而对于其它的 i, j, l 分两种情况考虑：

  1. 当最大值 j 恰好只出现在数组末尾时，构造的方法有 $\sum_{t=1}^{j-1}dp[i-1][t][l-1] $种，即前 i-1 个元素都小于 j；
  2. 而当最大值出现在前 i-1个元素之中时，数组末尾的元素可以从 1 到 j 中任意选取，即有 $ j \times dp[i-1][j][l]$种构造方法。
    综上所述，有
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
30
class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        const int MOD = 1e9+7;
        long long dp[55][110][55];
        memset(dp,0,sizeof dp);

        for(int i=1;i<=m;++i) dp[1][i][1] = 1;
        
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                for(int l=1;l<=k;++l){
                    if(i==1 && l==1)continue;
                    for(int t=1;t<j;++t){
                        dp[i][j][l] += dp[i-1][t][l-1];
                        dp[i][j][l] %= MOD;
                    }
                    dp[i][j][l] += j*dp[i-1][j][l];
                    dp[i][j][l] %= MOD;
                }
            }
        }
        long long res = 0;
        for(int i=0;i<=m;++i){
            res += dp[n][i][k];
            res %= MOD;
        }
        return int(res);
    }
};