🌟欢迎来到 我的博客 —— 探索技术的无限可能！
2.考试的最大困扰度
题目链接：2024. 考试的最大困扰度
一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 ‘T’ 表示）或者 false （用 ‘F’ 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
每次操作中，将问题的正确答案改为 ‘T’ 或者 ‘F’ （也就是将 answerKey[i] 改为 ‘T’ 或者 ‘F’ ）。
请你返回在不超过 k 次操作的情况下，最大 连续 ‘T’ 或者 ‘F’ 的数目。
示例 1：
输入：answerKey = “TTFF”, k = 2
输出：4
解释：我们可以将两个 ‘F’ 都变为 ‘T’ ，得到 answerKey = “TTTT” 。
总共有四个连续的 ‘T’ 。
示例 2：
输入：answerKey = “TFFT”, k = 1
输出：3
解释：我们可以将最前面的 ‘T’ 换成 ‘F’ ，得到 answerKey = “FFFT” 。
或者，我们可以将第二个 ‘T’ 换成 ‘F’ ，得到 answerKey = “TFFF” 。
两种情况下，都有三个连续的 ‘F’ 。
示例 3：
输入：answerKey = “TTFTTFTT”, k = 1
输出：5
解释：我们可以将第一个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTTTTFTT” 。
或者我们可以将第二个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTFTTTTT” 。
两种情况下，都有五个连续的 ‘T’ 。
提示：
n == answerKey.length
1 <= n <= 5 * 104
answerKey[i] 要么是 ‘T’ ，要么是 ‘F’
1 <= k <= n
题解：
方法：滑动窗口
class Solution { public int maxConsecutiveAnswers(String answerKey, int k) { char[] s = answerKey.toCharArray(); int ans = 0; int left = 0; int[] cnt = new int[2]; for (int right = 0; right < s.length; right++) { cnt[s[right] >> 1 & 1]++; while (cnt[0] > k && cnt[1] > k) { cnt[s[left++] >> 1 & 1]--; } ans = Math.max(ans, right - left + 1); } return ans; } }
3.一个小组的最大实力值
题目链接：2708. 一个小组的最大实力值
给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, … , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * … * nums[ik] 。
请你返回老师创建的小组能得到的最大实力值为多少。
示例 1：
输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) =
1350 ，这是可以得到的最大实力值。
示例 2：
输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。
提示：
1 <= nums.length <= 13
-9 <= nums[i] <= 9
题解：
方法：动态规划
class Solution { public long maxStrength(int[] nums) { long mn = nums[0]; long mx = mn; for (int i = 1; i < nums.length; i++) { long x = nums[i]; long tmp = mn; mn = Math.min(Math.min(mn, x), Math.min(mn * x, mx * x)); mx = Math.max(Math.max(mx, x), Math.max(tmp * x, mx * x)); } return mx; } }
4.让所有学生保持开心的分组方法数
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：
如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：
这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。
返回能够满足让所有学生保持开心的分组方法的数目。
示例 1：
输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。
示例 2：
输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。
提示：
1 <= nums.length <= 105
0 <= nums[i] < nums.length
题解：
方法：排序
class Solution { public int countWays(List<Integer> nums) { int[] a = nums.stream().mapToInt(i -> i).toArray(); Arrays.sort(a); int ans = a[0] > 0 ? 1 : 0; // 一个学生都不选 for (int i = 1; i < a.length; i++) { if (a[i - 1] < i && i < a[i]) { ans++; } } return ans + 1; // 一定可以都选 } }
5.清除数字
题目链接：3174. 清除数字
给你一个字符串 s 。
你的任务是重复以下操作删除 所有 数字字符：
删除 第一个数字字符 以及它左边 最近 的 非数字 字符。
请你返回删除所有数字字符以后剩下的字符串。
示例 1：
输入：s = “abc”
输出：“abc”
解释：
字符串中没有数字。
示例 2：
输入：s = “cb34”
输出：“”
解释：
一开始，我们对 s[2] 执行操作，s 变为 “c4” 。
然后对 s[1] 执行操作，s 变为 “” 。
提示：
1 <= s.length <= 100
s 只包含小写英文字母和数字字符。
输入保证所有数字都可以按以上操作被删除。
题解：
方法：栈
class Solution { public String clearDigits(String s) { StringBuilder st = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { st.deleteCharAt(st.length() - 1); } else { st.append(c); } } return st.toString(); } }
6.求出最长好子序列 I
题目链接：3176. 求出最长好子序列 I
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好
子序列
的最长长度。
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 500
1 <= nums[i] <= 109
0 <= k <= min(nums.length, 25)
题解：
方法：动态规划
class Solution { public int maximumLength(int[] nums, int k) { int n = nums.length; int[][] f = new int[n][k + 1]; int ans = 0; for (int i = 0; i < n; ++i) { for (int h = 0; h <= k; ++h) { for (int j = 0; j < i; ++j) { if (nums[i] == nums[j]) { f[i][h] = Math.max(f[i][h], f[j][h]); } else if (h > 0) { f[i][h] = Math.max(f[i][h], f[j][h - 1]); } } ++f[i][h]; } ans = Math.max(ans, f[i][k]); } return ans; } }
7.求出最长好子序列 II
题目链接：3177. 求出最长好子序列 II
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 5 * 103
1 <= nums[i] <= 109
0 <= k <= min(50, nums.length)
题解：
方法：哈希表 动态规划
class Solution { public int maximumLength(int[] nums, int k) { Map<Integer, int[]> fs = new HashMap<>(); int[][] records = new int[k + 1][3]; for (int x : nums) { int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]); for (int j = k; j >= 0; j--) { f[j]++; if (j > 0) { int mx = records[j - 1][0], mx2 = records[j - 1][1], num = records[j - 1][2]; f[j] = Math.max(f[j], (x != num ? mx : mx2) + 1); } // records[j] 维护 fs[.][j] 的 mx, mx2, num int v = f[j]; int[] p = records[j]; if (v > p[0]) { if (x != p[2]) { p[2] = x; p[1] = p[0]; } p[0] = v; } else if (x != p[2] && v > p[1]) { p[1] = v; } } } return records[k][0]; } }
8.有序数组的平方
题目链接：977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
题解：
方法：双指针
class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] ans = new int[n]; int i = 0; int j = n - 1; for (int p = n - 1; p >= 0; p--) { int x = nums[i] * nums[i]; int y = nums[j] * nums[j]; if (x > y) { ans[p] = x; i++; } else { ans[p] = y; j--; } } return ans; } }
