Problem List
- [1] 最好的扑克手牌
- [2] 全 0 子数组的数目
- [3] 设计数字容器系统
- [4] 不可能得到的最短骰子序列
1 最好的扑克手牌
1.1 题目描述
- 题目链接：最好的扑克手牌
1.1 题目描述
给你一个整数数组 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” 。
1.2 思路
简单的模拟即可。
class Solution {
public:
string bestHand(vector<int>& ranks, vector<char>& suits) {
unordered_map<char, int> hash;
unordered_map<int, int> map;
for(char c: suits) ++hash[c];
if(hash.size()==1) return "Flush";
for(int i: ranks) ++map[i];
if(map.size() == 5) return "High Card";
for(auto it: map) {
if(it.second >= 3) return "Three of a Kind";
}
return "Pair";
}
}; 2 全 0 子数组的数目
2.1 题目描述
- 题目链接：6129. 全 0 子数组的数目
2.1 题目描述
给你一个整数数组 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 。
2.2 思路
滑动窗口，维护一个元素均为0的窗口，当右侧遍历到非0元素时，将窗中元素所能组成的子数组总数加到答案中。如窗中元素个数为n，那么子数组个数就是n*(n+1)/2.
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
int n = nums.size(), left = -1, right = 0;
long long ans = 0;
for(; right <= n; ++right) {
if(right==n || nums[right]!=0) {
ans += (1ll*right-left-1) * (right-left) / 2;
left = right;
}
}
return ans;
}
}; 3 设计数字容器系统
3.1 题目描述
- 题目链接：6130. 设计数字容器系统
3.1 题目描述
设计一个数字容器系统，可以实现以下功能：
- 在系统中给定下标处 插入 或者 替换 一个数字。
- 返回 系统中给定数字的最小下标。
请你实现一个 NumberContainers 类：
NumberContainers()初始化数字容器系统。void change(int index, int number)在下标index处填入number。如果该下标index处已经有数字了，那么用number替换该数字。int find(int number)返回给定数字number在系统中的最小下标。如果系统中没有number，那么返回-1。
示例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]
3.2 思路
一个map用于存储索引和值之间的映射，然年用一个map来存放值为number的下标，而由于需要返回最小的下标，因而同一number的下标需要有序，那么考虑采用set，即采用unordered_map<int, set<int>>同时实现number和index的映射以及下标有序。
class NumberContainers {
unordered_map<int, set<int>> hash; // number->index
unordered_map<int, int> map; // index->number
public:
NumberContainers() {
}
void change(int index, int number) {
if(map.count(index)) {
hash[map[index]].erase(index);
}
hash[number].insert(index);
map[index] = number;
}
int find(int number) {
if(!hash.count(number)) return -1;
if(hash[number].size()==0) return -1;
return *hash[number].begin();
}
}; 4 不可能得到的最短骰子序列
4.1 题目描述
- 题目链接：6131. 不可能得到的最短骰子序列
4.1 题目描述
给你一个长度为 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
示例2：
输入: rolls = [1,1,2,2], k = 2
输出: 2
示例3：
输入: rolls = [1,1,3,2,2,2,3,3], k = 4
输出: 1
4.2 思路
脑筋急转弯。直接数rolls中包括完整的1-k的序列的次数cnt，那么答案就是cnt+1。因为得不到的子序列中，第一个能出现的字符必定在第一个完整1-k序列中出现，第二字符一定会在第二个出现…，那么当完整序列共有cnt个，那么不能得到的最短子序列就是恰好最后一个字符没在rolls中出现，所以就是第cnt+1个字符没出现，所以答案就出来了。
class Solution {
public:
int shortestSequence(vector<int>& rolls, int k) {
unordered_set<int> s;
int ans = 0;
for(int i: rolls) {
s.insert(i);
if(s.size()==k){
s.clear();
++ans;
}
}
return ans + 1;
}
};
