暑期算法打卡---第六天

落日映苍穹つ 2023-09-28 14:11 92阅读 0赞

### 1、学生分数的最小差值 ###

题目：

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums\[i\] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

示例 1：

输入：nums = \[90\], k = 1  
输出：0  
解释：选出 1 名学生的分数，仅有 1 种方法：  
\- \[90\] 最高分和最低分之间的差值是 90 - 90 = 0  
可能的最小差值是 0

示例 2：

输入：nums = \[9,4,1,7\], k = 2  
输出：2  
解释：选出 2 名学生的分数，有 6 种方法：  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 9 - 4 = 5  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 9 - 1 = 8  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 9 - 7 = 2  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 4 - 1 = 3  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 7 - 4 = 3  
\- \[9,4,1,7\] 最高分和最低分之间的差值是 7 - 1 = 6  
可能的最小差值是 2

提示：

1 <= k <= nums.length <= 1000  
0 <= nums\[i\] <= 105

题解：

![0787220864bc4e69a20c3b7d7aecaa51.png][]

### 2、乘积小于K的子数组 ###

题目：

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = \[10,5,2,6\], k = 100  
输出：8  
解释：8 个乘积小于 100 的子数组分别为：\[10\]、\[5\]、\[2\],、\[6\]、\[10,5\]、\[5,2\]、\[2,6\]、\[5,2,6\]。  
需要注意的是 \[10,5,2\] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = \[1,2,3\], k = 0  
输出：0

提示:

1 <= nums.length <= 3 \* 104  
1 <= nums\[i\] <= 1000  
0 <= k <= 106

题解：

![8c8eb003994d49e58f649b68c9cd04a4.png][]

### 3、考试的最大困扰度 ###

题目：

一位老师正在出一场由 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

题解：

![c099aab9841f4d0ab7d07a34f87c63c3.png][]

[0787220864bc4e69a20c3b7d7aecaa51.png]: https://img-blog.csdnimg.cn/0787220864bc4e69a20c3b7d7aecaa51.png
[8c8eb003994d49e58f649b68c9cd04a4.png]: https://img-blog.csdnimg.cn/8c8eb003994d49e58f649b68c9cd04a4.png
[c099aab9841f4d0ab7d07a34f87c63c3.png]: https://img-blog.csdnimg.cn/c099aab9841f4d0ab7d07a34f87c63c3.png