拿师兄的号打的，最后一题脑筋急转弯，用了好长时间

6128. 最好的扑克手牌

给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。
下述是从好到坏你可能持有的 手牌类型 ：

  1. “Flush”：同花，五张相同花色的扑克牌。
  2. “Three of a Kind”：三条，有 3 张大小相同的扑克牌。
  3. “Pair”：对子，两张大小一样的扑克牌。
  4. “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’
  • 任意两张扑克牌不会同时有相同的大小和花色。

思路：
模拟

  1. class Solution {
  2.     public String bestHand(int[] r, char[] s) {
  3.         int[] c1 = new int[4];
  4.         int[] c2 = new int[14];
  5.         for (char c : s) {
  6.             c1[c - 'a']++;
  7.         }
  8.         for (int x : r)
  9.             c2[x]++;
  10.         for (int x : c1) if (x == 5) return "Flush";
  11.         for (int x : c2) if (x >= 3) return "Three of a Kind";
  12.         for (int x : c2) if (x >= 2) return "Pair";
  13.         return "High Card";
  14.     }
  15. }

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

思路：
遍历 + 计数
时间复杂度：O(n)

  1. class Solution {
  2.     public long zeroFilledSubarray(int[] nums) {
  3.         long res = 0;
  5.         int cnt = 0;
  6.         for (int x : nums) {
  7.             if (x == 0) cnt++;
  8.             else {
  9.                 res += (1L * cnt) * (cnt + 1L) / 2;
  10.                 cnt = 0;
  11.             }
  12.         }
  13.         res += (1L * cnt) * (cnt + 1L) / 2;
  14.         return res;
  15.     }
  17. }

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 次。

思路：
用Map + TreeSet模拟

  1. class NumberContainers {
  3.     Map<Integer, Integer> map = new HashMap<>();
  4.     Map<Integer, TreeSet<Integer>> cnt = new HashMap<>();
  5.     public NumberContainers() {
  7.     }
  9.     public void change(int index, int number) {
  10.         if (map.containsKey(index)) {
  11.             int x = map.get(index);
  12.             Set<Integer> set = cnt.get(x);
  13.             set.remove(index);
  14.             map.put(index, number);
  15.             cnt.computeIfAbsent(number, key -> new TreeSet<>()).add(index);
  16.         } else {
  17.             map.put(index, number);
  18.             cnt.computeIfAbsent(number, key -> new TreeSet<>()).add(index);
  19.         }
  20.     }
  22.     public int find(int number) {
  23.         TreeSet<Integer> res = cnt.getOrDefault(number, null);
  24.         if (res == null || res.isEmpty()) return -1;
  25.         return res.first();
  26.     }
  27. }
  29. /**
  30.  * Your NumberContainers object will be instantiated and called as such:
  31.  * NumberContainers obj = new NumberContainers();
  32.  * obj.change(index,number);
  33.  * int param_2 = obj.find(number);
  34.  */

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

思路：
脑筋急转弯
长度为len的全排列一定在原序列中全部出现的条件是: 原序列中存在有序的len个k的排列

  1. class Solution {
  2.     public int shortestSequence(int[] r, int k) {
  4.         Set<Integer> set = new HashSet<>();
  5.         int c = 0;
  6.         for (int x : r) {
  7.             set.add(x);
  8.             if (set.size() == k) {
  9.                 c++;
  10.                 set.clear();
  11.             }
  12.         }
  13.         return c + 1;
  14.     }
  15. }