leetcode biweekly conttest 83

比较简单的周赛，4个题目感觉都挺无聊的。

6128. 最好的扑克手牌

题目

给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。

下述是从好到坏你可能持有的手牌类型：

"Flush"：同花，五张相同花色的扑克牌。
"Three of a Kind"：三条，有 3 张大小相同的扑克牌。
"Pair"：对子，两张大小一样的扑克牌。
"High Card"：高牌，五张大小互不相同的扑克牌。
请你返回一个字符串，表示给定的 5 张牌中，你能组成的最好手牌类型。

注意：返回的字符串大小写需与题目描述相同。

示例 1：

输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
输出："Flush"
解释：5 张扑克牌的花色相同，所以返回 "Flush" 。

示例 2：

输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]
输出："Three of a Kind"
解释：第一、二和四张牌组成三张相同大小的扑克牌，所以得到 "Three of a Kind" 。
注意我们也可以得到 "Pair" ，但是 "Three of a Kind" 是更好的手牌类型。
有其他的 3 张牌也可以组成 "Three of a Kind" 手牌类型。

示例 3：

输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]
输出："Pair"
解释：第一和第二张牌大小相同，所以得到 "Pair" 。
我们无法得到 "Flush" 或者 "Three of a Kind" 。

提示：

ranks.length == suits.length == 5
1 <= ranks[i] <= 13
'a' <= suits[i] <= 'd'
任意两张扑克牌不会同时有相同的大小和花色。

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/best-poker-hand/

题意

直接遍历

思路

简单题目，直接尝试所有的可能即可
复杂度分析：

时间复杂度：$O(n \log n)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    string bestHand(vector<int>& ranks, vector<char>& suits) {
        bool isFlush = true; 
        for (int i = 1; i < suits.size(); i++) {
            if (suits[i] != suits[i-1]) {
                isFlush = false;
                break;
            }
        }
        if (isFlush) {
            return "Flush";
        }
        
        sort(ranks.begin(), ranks.end());
        for (int i = 2; i < ranks.size(); i++) {
            if (ranks[i] == ranks[i-1] && ranks[i] == ranks[i-2]) {
                return "Three of a Kind";
            }
        }
        for (int i = 1; i < ranks.size(); i++) {
            if (ranks[i] == ranks[i-1]) {
                return "Pair";
            }
        }
        return "High Card";
    }
};

6129. 全 0 子数组的数目

题目

给你一个整数数组 nums ，返回全部为 0 的子数组数目。

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

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/number-of-zero-filled-subarrays/

题意

动态规划

思路

设 x 为当前连续的 0 的长度，则此时可以产生 $\frac{n *(n - 1)}{2}$ 个全 0 的子数组。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示数组的长度。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long ans = 0;
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                cnt++;
            } else{
                cnt = 0;
            }
            ans += cnt;
        }
        return ans;
    }
};

6130. 设计数字容器系统

题目

设计一个数字容器系统，可以实现以下功能：

在系统中给定下标处插入或者替换一个数字。
返回系统中给定数字的最小下标。
请你实现一个 NumberContainers 类：

NumberContainers() 初始化数字容器系统。
void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字。
int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。

示例：

输入：
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
输出：
[null, -1, null, null, null, null, 1, null, 2]

解释：
NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ，所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。

提示：

1 <= index, number <= 109
调用 change 和 find 的总次数不超过 105 次。

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/design-a-number-container-system/

题意

hash + treeset

思路

感觉可以算是一个简单题目，用两个hash 表实现即可。一个 hash 用来存储索引到值的映射，另一个用来存储值到索引的映射，每次 change 操作时，两个 hash 同时替换即可。确实没有多少可讲的。
复杂度分析：

时间复杂度：暴力模拟的时间复杂度为 $O(n \log n)$。
空间复杂度：$O(n)$。

代码

class NumberContainers {
public:
    NumberContainers() {

    }
    
    void change(int index, int number) {
        if (nums.count(index)) {
            int val = nums[index];
            cnt[val].erase(index);
            if (cnt[val].size() == 0) {
                cnt.erase(val);
            }
            nums.erase(index);
        } 
        nums[index] = number;
        cnt[number].emplace(index);
    }
    
    int find(int number) {
        if (!cnt.count(number)) {
            return -1;
        }
        return *(cnt[number].begin());
    }
private:
    unordered_map<int, int> nums;
    unordered_map<int, set<int>> cnt;
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

6131. 不可能得到的最短骰子序列

题目

给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。

请你返回无法从 rolls 中得到的最短骰子子序列的长度。

扔一个 k 面的骰子 len 次得到的是一个长度为 len 的骰子子序列。

注意，子序列只需要保持在原数组中的顺序，不需要连续。

示例 1：

输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4
输出：3
解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。
所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。
子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。
还有别的子序列也无法从原数组中得到。

示例 2：

输入：rolls = [1,1,2,2], k = 2
输出：2
解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。
子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。
还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。
还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。

提示：

n == rolls.length
1 <= n <= 105
1 <= rolls[i] <= k <= 105

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/shortest-impossible-sequence-of-rolls/

题意

数学问题

思路

感觉是比较简单的排列组合理论即可，我们仔细观察一下：

如果满足长度为 $1$ 的子序列全部出现，则此时数组中一定满足出现 $s = [1,\cdots, k]$，当然可以是 $s$ 的任意顺序；
如果满足长度为 $2$ 的子序列全部出现，则此时数组中一定满足对于任意的 $i \in [1,k]$ 的索引后面一定会出现 $s = [1,\cdots, k]$ 的任意排列，综上可以知道此时数组中一定出现两个 $s$ 序列 $s_1 = [1,\cdots, k], s_0 = [1,s\cdots, k]$ 且 $s_1$ 中的全部元素一定在 $ s_0$ 的前面。只有这样才能保证所有长度为$2$ 的子序列全部出现。
综上我们可以观察出，我们只需要计算数组中连续出现序列 $s = [1, \cdots, k] $ 的最大次数即可。
连续出现的最大次数加 $1$ 即为无法得到的最短序列。我们可以用 hash 表来统计当前序列中已经出现的不同元素是否达到 $k$ 个。

复杂度分析：

时间复杂度：$O(n)$，$n$ 表示数组 $rolls$ 的长度。
空间复杂度：$O(k)$，哈希表中最多存储 $k$ 个元素。

代码

class Solution {
public:
    int shortestSequence(vector<int>& rolls, int k) {
        int n = rolls.size();
        int ans = 0;
        unordered_set<int> cnt;
        for (int i = n - 1; i >= 0; i--) {
            cnt.emplace(rolls[i]);
            if (cnt.size() == k) {
                ans++;
                cnt.clear();
            }
        }
        return ans + 1;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode conttest 303 leetcode conttest 302 →

扫描二维码，分享此文章