🌟欢迎来到 我的博客 —— 探索技术的无限可能！
27.找出缺失的观测数据
题目链接：2028. 找出缺失的观测数据
现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。
给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。
返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。
k 个数字的 平均值 为这些数字求和后再除以 k 。
注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。
示例 1：
输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。
示例 2：
输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。
示例 3：
输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。
示例 4：
输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。
提示：
m == rolls.length
1 <= n, m <= 105
1 <= rolls[i], mean <= 6
题解：
方法：构造
class Solution {
public int[] missingRolls(int[] rolls, int mean, int n) {
int m = rolls.length;
int s = (n + m) * mean;
for (int v : rolls) {
s -= v;
}
if (s > n * 6 || s < n) {
return new int[0];
}
int[] ans = new int[n];
Arrays.fill(ans, s / n);
for (int i = 0; i < s % n; ++i) {
++ans[i];
}
return ans;
}
}
28.找出峰值
题目链接：2951. 找出峰值
给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。
以数组形式返回给定数组中 峰值 的下标，顺序不限 。
注意：
峰值 是指一个严格大于其相邻元素的元素。
数组的第一个和最后一个元素 不 是峰值。
示例 1：
输入：mountain = [2,4,4]
输出：[]
解释：
mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。
因此，答案为 [] 。
示例 2：
输入：mountain = [1,4,3,8,5]
输出：[1,3]
解释：
mountain[0] 和 mountain[4] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
mountain[2] 也不可能是峰值，因为它不严格大于 mountain[3] 和 mountain[1] 。
但是 mountain[1] 和 mountain[3] 严格大于它们的相邻元素。
因此，答案是 [1,3] 。
提示：
3 <= mountain.length <= 100
1 <= mountain[i] <= 100
题解：
方法：遍历
class Solution {
public List<Integer> findPeaks(int[] mountain) {
List<Integer> ans = new ArrayList<>();
for (int i = 1; i < mountain.length - 1; ++i) {
if (mountain[i - 1] < mountain[i] && mountain[i + 1] < mountain[i]) {
ans.add(i);
}
}
return ans;
}
}
29.找出出现至少三次的最长特殊子字符串 I
题目链接：2981. 找出出现至少三次的最长特殊子字符串 I
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1：
输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。 可以证明最大长度是 2 。
示例 2：
输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3：
输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。
提示：
3 <= s.length <= 50
s 仅由小写英文字母组成。
题解：
方法：二分查找 计数 滑动窗
class Solution {
private String s;
private int n;
public int maximumLength(String s) {
this.s = s;
n = s.length();
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}
private boolean check(int x) {
int[] cnt = new int[26];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int k = s.charAt(i) - 'a';
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
}
}
30.找出出现至少三次的最长特殊子字符串 II
题目链接：2982. 找出出现至少三次的最长特殊子字符串 II
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1：
输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。
示例 2：
输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3：
输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。 可以证明最大长度是 1
。
提示：
3 <= s.length <= 5 * 105
s 仅由小写英文字母组成。
题解：
方法：二分查找 滑动窗口 计数
class Solution {
private String s;
private int n;
public int maximumLength(String s) {
this.s = s;
n = s.length();
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}
private boolean check(int x) {
int[] cnt = new int[26];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int k = s.charAt(i) - 'a';
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
}
}
31.找出缺失和重复的数字
题目链接：2965. 找出缺失和重复的数字
给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。
任务是找出重复的数字a 和缺失的数字 b 。
返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。
示例 1：
输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。
示例 2：
输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。
提示：
2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1
且 grid[i][j] == x 。
题解：
方法：计数
class Solution {
public int[] findMissingAndRepeatedValues(int[][] grid) {
int n = grid.length;
int[] cnt = new int[n * n + 1];
int[] ans = new int[2];
for (int[] row : grid) {
for (int x : row) {
if (++cnt[x] == 2) {
ans[0] = x;
}
}
}
for (int x = 1;; ++x) {
if (cnt[x] == 0) {
ans[1] = x;
return ans;
}
}
}
}
2024.6
1.给小朋友们分糖果 I
题目链接：2928. 给小朋友们分糖果 I
给你两个正整数 n 和 limit 。
请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。
示例 1：
输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1)
。
示例 2：
输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1)
，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和
(3, 0, 0) 。
提示：
1 <= n <= 50
1 <= limit <= 50
题解：
方法：组合数学 枚举
容斥原理
class Solution {
public int distributeCandies(int n, int limit) {
if (n > 3 * limit) {
return 0;
}
long ans = comb2(n + 2);
if (n > limit) {
ans -= 3 * comb2(n - limit + 1);
}
if (n - 2 >= 2 * limit) {
ans += 3 * comb2(n - 2 * limit);
}
return (int) ans;
}
private long comb2(int n) {
return 1L * n * (n - 1) / 2;
}
}
数学题单
==数学题单==
2.分糖果
题目链接：575. 分糖果
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
示例 1：
输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。
示例 2：
输入：candyType = [1,1,2,3]
输出：2
解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是
[2,3]，她只能吃到两种不同类的糖。
示例 3：
输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。
提示：
n == candyType.length
2 <= n <= 104
n 是一个偶数
-105 <= candyType[i] <= 105
题解：
方法：哈希表
class Solution {
public int distributeCandies(int[] candyType) {
Set<Integer> s = new HashSet<>();
for (int c : candyType) {
s.add(c);
}
return Math.min(candyType.length >> 1, s.size());
}
}
