运气也是实力的一部分，哦吼吼…
最后一题猜过去的emmm
最好的扑克手牌3
题目
思路
模拟，也许有好的方法？
代码
class Solution { public: string bestHand(vector<int>& ranks, vector<char>& suits) { string res[10] = {"", "Flush", "Three of a Kind", "Pair", "High Card"}; int n = ranks.size(), m = suits.size(); bool o1 = true, o2 = true, o3 = true, o4 = true; // 分别对应四种 for (int i = 1; i < m; i++) if(suits[i] != suits[i - 1]) o1 = false; if(o1) { return res[1]; } map<int, int> mp; for (auto &x: ranks) mp[x]++; for (auto &x: mp) { if(x.second >= 3) o2 = false; else if(x.second >= 2) o3 = false; } if(!o2) { return res[2]; } if(!o3) { return res[3]; } return res[4]; } };
全 0 子数组的数目4
题目
思路
- 分别找出每一堆 0，比如1100011，[0] -> 3，[0,0] -> 2，[0,0,0] -> 1。那么对于每一堆 0，就是 (len + 1) * len / 2 个。
代码
class Solution { public: #define ll long long long long zeroFilledSubarray(vector<int>& nums) { int n = nums.size(); ll res = 0; for (int i = 0; i < n; i++) { if(nums[i] == 0) { int j = i + 1; while(j < n && nums[j] == 0) j++; res += (ll)(j - i + 1) * (j - i) / 2; i = j; } } return res; } };
设计数字容器系统5
题目
思路
两个操作：
change：在（index，number）位置，插一个值
find：找出（number）值最小的下标
首先，数据范围 1e9，不可能是正常的数组维护，考虑用哈希map。
先看find，对于number最小下标，很容易想到，number值可能会在维护的结构种多次出现，所以这里我们map的key表示number的话，那么val应该存储所有的number的当前位置。
由由于我们需要快数的找到number的最小下标位置，而且得支持快速的修改（删除），那么结构map>会是一个很好的选择。
一：*mp[number].begin()：能直接取到number值存储的最小下标。
二：mp[number].erase(index)：可以直接log级在number被替换时，删除number存储的下标。
int find(int number) { if(mp[number].size() == 0) return -1; return *mp[number].begin(); }
再看change：即按题意，对于每一个下标存储的值，我们还得用map a模拟数组去存储。然后就是对其进行替换或是插入即可。
有点冗余，赛时代码就不修整了。
void change(int index, int number) { if(a.count(index) != 0) { mp[a[index]].erase(index); a[index] = number; mp[number].insert(index); } else { a[index] = number; mp[number].insert(index); } }
代码：
class NumberContainers { public: map<int, set<int>> mp; map<int, int> a; NumberContainers() { a.clear(), mp.clear(); } void change(int index, int number) { if(a.count(index) != 0) { mp[a[index]].erase(index); a[index] = number; mp[number].insert(index); } else { a[index] = number; mp[number].insert(index); } } int find(int number) { if(mp[number].size() == 0) return -1; return *mp[number].begin(); } };
不可能得到的最短骰子序列
题目
思路
这题其实我也算是猜的一个结论。（具体证明请移步官解）
对于len长度的序列，这里演示 rolls = [3,2,1,2,3,2,3,1]，k = 3：
len = 1：
【1】、【2】、【3】
len = 2：
【1、1】、【1、2】、【1、3】
【2、1】、【2、2】、【2、3】
【3、1】、【3、1】、【3、3】
len = 3：
【1、1、（无了）】 … 以下就不枚举了
就是可以大胆猜测，要满足len长度的序列，那么必然【1-k】【1-k】…【1-k】，得有len组，每一组里得包含（1-k）之间的所有数。只有这样才能满足 所有 的len长度序列。
那么代码该怎么实现？
其实不难，我们目的就是看最终能构成多少组。
所以只需要遍历一遍，res表示当前已经构成了多少组，pre表示在尝试构成第res+1组的当前已经有多少个值满足了（pre==k则会多一组）。我们可以利用res变量对数组a赋值，这样就不必每次清空数组去计算1的个数维护到等于k。
含含糊糊恍恍惚惚，加油加油，再接再厉！！！
代码
class Solution { public: static constexpr int N = 100010; int a[N]; int shortestSequence(vector<int>& rolls, int k) { int n = rolls.size(); int pre = 0, res = 1; for (int i = 0; i < n; i++) { if(a[rolls[i]] < res) { a[rolls[i]] = res; pre ++; } if(pre == k) { pre = 0; res += 1; } } return res; } };
