1224. 最大相等频率

2022.8.18

题目描述

给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：

从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

示例 1：

输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。

示例 2：

输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13

提示：

2 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-equal-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个Counter以后学着用

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        # 先统计每个数字出现了几次
        # 一边遍历一边统计
        count, freq = Counter(), Counter()
        maxfre = 0
        ans = 0
        for i, num in enumerate(nums):
            if count[num]:
                freq[count[num]] -= 1
            count[num] += 1
            freq[count[num]] += 1
            maxfre = max(maxfre, count[num])
            if maxfre == 1:
                ans = i + 1
            # 如果只有一个数出现了一次，其他数出现次数相同
            elif maxfre * freq[maxfre] + 1 == i + 1 and freq[1] == 1:
                ans = i + 1
            # 如果其他数都是maxfre - 1,一个数是maxfre
            elif freq[maxfre] == 1 and freq[maxfre - 1] * (maxfre - 1) + maxfre == i + 1:
                ans = i + 1
            #elif freq[maxfre] == i + 1:
            #    ans = i + 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

2022.8.19 每日一题，周五了哈哈哈

题目描述

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

示例 1：

输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。

示例 2：

输入：startTime = [4], endTime = [4], queryTime = 4
输出：1
解释：在查询时间只有一名学生在做作业。

示例 3：

输入：startTime = [4], endTime = [4], queryTime = 5
输出：0

示例 4：

输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出：0

示例 5：

输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5

提示：

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

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

二分查找
关于这个函数的用法：https://blog.csdn.net/YMWM_/article/details/122378152

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        # 二分查找，先分别找到开始时间或结束时间满足条件的部分
        # 然后找出两个集合的交集
        startTime.sort()
        endTime.sort()
        # bisect_left()函数的输出是num在list中最左面值的数组下标，其余两个函数的输出为最右面的数组下标+1
        return bisect_right(startTime, queryTime) - bisect_left(endTime, queryTime)
1
2
3
4
5
6
7
8

差分数组，前缀和表示当前时间点的个数

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        # 差分数组
        maxEndTime = max(endTime)
        if queryTime > maxEndTime:
            return 0
        cnt = [0] * (maxEndTime + 2)
        for s, e in zip(startTime, endTime):
            cnt[s] += 1
            cnt[e + 1] -= 1
        return sum(cnt[:queryTime + 1])
1
2
3
4
5
6
7
8
9
10
11

655. 输出二叉树

2022.8.22 每日一题

题目描述

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

• 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
• 矩阵的列数 n 应该等于 2^(height+1) - 1 。
• 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
• 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2^(height-r-1)] ，右子节点放置在 res[r+1][c+2^(height-r-1)] 。
• 继续这一过程，直到树中的所有节点都妥善放置。
• 任意空单元格都应该包含空字符串 “” 。
• 返回构造得到的矩阵 res 。

示例 1：

输入：root = [1,2]
输出：
[[“”,“1”,“”],
[“2”,“”,“”]]

示例 2：

输入：root = [1,2,3,null,4]
输出：
[[“”,“”,“”,“1”,“”,“”,“”],
[“”,“2”,“”,“”,“”,“3”,“”],
[“”,“”,“4”,“”,“”,“”,“”]]

提示：

树中节点数在范围 [1, 2^10] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/print-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

其实题比较简单，先找到高度，创建列表，然后层序遍历，将节点加入列表中就行了
但是因为对python熟悉程度不够，导致还是定义函数，调用函数出现了很多问题

# 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:
    maxHeight = 0

    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        # 最简单的思路就是先找到树的高度，然后创建列表
        # 层序遍历添加节点
        self.findHeight(0, root)
        m = self.maxHeight + 1
        n = 2 ** m - 1
        matrix = []
        for i in range(m):
            matrix.append(["" for j in range(n)])
        # print(len(matrix))
        
        matrix[0][n // 2] = str(root.val)
        queue = [[root, 0, n // 2]]
        while queue:
            top = queue.pop(0)
            if top[0].left:
                x = top[1] + 1
                y = top[2] - 2 ** (self.maxHeight - top[1] - 1)
                matrix[x][y] = str(top[0].left.val)
                queue.append([top[0].left, x, y])
            if top[0].right:
                x = top[1] + 1
                y = top[2] + 2 ** (self.maxHeight - top[1] - 1)
                matrix[x][y] = str(top[0].right.val)
                queue.append(([top[0].right, x, y]))

        return matrix

    def findHeight(self, h, root):
        if not root:
            return self.maxHeight
        if root.left:
            self.findHeight(h + 1, root.left)
        if root.right:
            self.findHeight(h + 1, root.right)
        self.maxHeight = max(h, self.maxHeight)
        return self.maxHeight
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

dfs

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def calDepth(node: Optional[TreeNode]) -> int:
            return max(calDepth(node.left), calDepth(node.right)) + 1 if node else 0
        height = calDepth(root) - 1

        m = height + 1
        n = 2 ** m - 1
        ans = [[''] * n for _ in range(m)]
        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:
            ans[r][c] = str(node.val)
            if node.left:
                dfs(node.left, r + 1, c - 2 ** (height - r - 1))
            if node.right:
                dfs(node.right, r + 1, c + 2 ** (height - r - 1))
        dfs(root, 0, (n - 1) // 2)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22