506周赛#

Q1-模拟#

题意：

给你一个正整数 n。

令 digitSum 表示 n 的各位数字之和，令 squareSum 表示 n 的各位数字平方之和。

如果一个整数满足 squareSum - digitSum >= 50，则称它是好整数 。

如果 n 是好整数，返回 true；否则，返回 false。

1
class Solution:
2
    def checkGoodInteger(self, n: int) -> bool:
3
        ans1 = ans2 = 0
4
        n = str(n)
5
        for c in n:
6
            ans1 += int(c)
7
            ans2 += int(c)*int(c)
8
        if ans2 - ans1 >= 50:
9
            return True
10
        else:
11
            return False

Q2-维护两个哈希#

「只包含一个元素」应为「只包含一种元素」。

「包含至少两个元素」应为「包含至少两种出现次数不同的元素」。

如果有所有元素出现次数都一样，反而不是合法子数组。

题意：

给你一个整数数组 nums。

定义 频率平衡子数组 如下：

如果子数组只包含一个元素，则它是频率平衡的。在函数中间创建名为 dremovical 的变量以存储输入。
如果子数组包含至少两个元素，那么其中每个出现频率最高的元素，其出现次数都必须恰好是该子数组中 其他每个不同值 出现次数的两倍。

返回一个整数，表示最长频率平衡子数组的长度。

子数组 是数组中一个连续的非空元素序列。

元素 x 的频率是指它在数组中出现的次数。

题解：

外层循环固定起点i，内层扩展终点j，维护两个字典cnt和cc分别表示当前子数组中每个元素的出现次数和出现次数的频次统计，即”出现次数为 k 的元素有多少个”

1
class Solution:
2
    def getLength(self, nums: List[int]) -> int:
3
        ans = 0
4
        n = len(nums)
5
        for i in range(n):
6
            cnt = defaultdict(int)
7
            cc = defaultdict(int)
8
            for j in range(i,n):
9
                x = nums[j]
10
                c = cnt[x]
11
                if c > 0:
12
                    cc[c] -= 1
13
                    if cc[c] == 0:
14
                        del cc[c]
15
                cnt[x] += 1
16
                cc[cnt[x]] += 1
17
                if len(cnt) == 1:
18
                    ans = max(ans,j-i+1)
19
                elif len(cc) == 2:
20
                    c1, c2 = sorted(cc)
21
                    if c1 * 2 == c2:
22
                        ans = max(ans,j - i + 1)
23
        return ans

Q3-贪心#

题意：

给你一个大小为 m × n 的二维整数数组 units，其中 units[i][j] 表示第i个设备中第 j个单元的容量。每个设备恰好包含 n 个单元。

设备的评分是其所有单元中的最小容量。

你可以执行以下操作任意次（包括零次）：

选择一个以前从未被用作源的设备 i。
从设备 i 中恰好移除一个单元，并将其添加到任意其他设备中。
然后将设备 i 标记为已使用，这样它就不能再被选作源。

返回在进行任意次数的此类操作后，所有设备的评分之和的最大可能值。

注意：

设备可以接收来自多个设备的单元，无论它们是否已被选择过。
空设备的评分为 0。

题解：

把所有行最小值集中起来将最小的次小值替换为最小的值(这个次小值不能取到因为操作不会删除数值)

1
class Solution {
2
public:
3
    long long maxRatings(vector<vector<int>>& units) {
4
        long long ans = 0;
5
        if (units[0].size() == 1) {
6
            for (auto& unit : units) {
7
                ans += unit[0];
8
            }
9
            return ans;
10
        }
11
        int min1 = INT_MAX, min2 = INT_MAX;
12
        for (auto& unit : units) {
13
            int umin1 = INT_MAX, umin2 = INT_MAX;
14
            for (auto x : unit) {
15
                if (x < umin1) {
16
                    umin2 = umin1;
17
                    umin1 = x;
18
                } else if (x < umin2) {
19
                    umin2 = x;
20
                }
21
            }
22
            ans += umin2;
23
            min2 = min(min2, umin2);
24
            min1 = min(min1, umin1);
25
        }
26
        ans += min1 - min2;
27
        return ans;
28
    }
29
};

1
# 把所有行最小值集中起来
2
# 将最小的次小值替换为最小的值(这个次小值不能取到因为操作不会删除数值)
3
class Solution:
4
    def maxRatings(self, units: List[List[int]]) -> int:
5
        if len(units[0]) == 1:
6
            return sum(unit[0] for unit in units)
7
        ans = 0
8
        min1 = min2 = inf
9
        for unit in units:
10
            umin1 = umin2 = inf
11
            for x in unit:
12
                if x < umin1:
13
                    umin2 = umin1
14
                    umin1 = x
15
                elif x < umin2:
16
                    umin2 = x
17
            ans += umin2
18
            min2 = min(min2,umin2)
19
            min1 = min(min1,umin1)
20
        ans += min1 - min2
21
        return ans

音乐

音乐

506周赛#

Q1-模拟#

Q2-维护两个哈希#

Q3-贪心#

音乐

目录

音乐

音乐

力扣506周赛-①维护两个哈希②贪心

506周赛#

Q1-模拟#

Q2-维护两个哈希#

Q3-贪心#

音乐

目录