一、今日练习题目:
1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组 nums ,其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数,使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
1763. 最长的美好子字符串
2269. 找到一个数字的 K 美丽值
一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目:
- 子字符串长度为 k 。
- 子字符串能整除 num 。
给你整数 num 和 k ,请你返回 num 的 k 美丽值。
注意:- 允许有 前缀 0 。
- 0 不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。
995. K 连续位的最小翻转次数
给定一个二进制数组 nums 和一个整数 k 。
k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ,同时把子数组中的每一个 0 都改成 1 ,把子数组中的每一个 1 都改成 0 。
返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能,则返回 -1 。
子数组 是数组的 连续 部分。
二、源码分析
题目1:1984. 学生分数的最小差值
class Solution {
public int minimumDifference(int[] nums, int k) {
int len = nums.length; Arrays.sort(nums); int ans = Integer.MAX_VALUE; for (int i = 0; i + k - 1 < len; i++) {
ans = Math.min(ans, nums[i + k - 1] - nums[i]); } return ans; } }
讯享网
容易证明,对于k个数,求最大最小值的差值最小,必定是有序的连续k个数中求解,所以先排序,然后滑动窗口
题目2:1763. 最长的美好子字符串
讯享网 class Solution {
public String longestNiceSubstring(String s) {
int n = s.length(); String ans = ""; for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (j - i + 1 > ans.length() && check(s.substring(i, j + 1))) ans = s.substring(i, j + 1); } } return ans; } boolean check(String s) {
Set<Character> set = new HashSet<>(); for (char c : s.toCharArray()) set.add(c); for (char c : s.toCharArray()) {
char a = Character.toLowerCase(c), b = Character.toUpperCase(c); if (!set.contains(a) || !set.contains(b)) return false; } return true; } }
时间复杂度O(n3)的暴力解法,判断每个字符串是否符合要求。
题目3:2269. 找到一个数字的 K 美丽值
class Solution {
public int divisorSubstrings(int num, int k) {
String str = String.valueOf(num); int l = 0, r = k, len = str.length(); int cnt = 0; while (r <= len) {
String s = str.substring(l, r); int sub = Integer.parseInt(s); if (sub !=0 && num % sub == 0) {
cnt++; } l++; r++; } return cnt; } }
题目提示了子字符串是一个连续的一段字符序列,还给了长度k,直接使用滑动窗口截取字符串,然后转换为数字进行判断
题目4:995. K 连续位的最小翻转次数
讯享网class Solution {
public int minKBitFlips(int[] nums, int k) {
int n = nums.length; int ans = 0; int[] arr = new int[n + 1]; for (int i = 0, cnt = 0; i < n; i++) {
cnt += arr[i]; if ((nums[i] + cnt) % 2 == 0) {
if (i + k > n) return -1; arr[i + 1]++; arr[i + k]--; ans++; } } return ans; } }
直接暴力翻转会出现超时的情况,使用差分数组来进行优化:当需要对某一段 [l,r] 进行 +1 的时候,只需要 arr[l]++ 和 arr[r + 1]-- 即可。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79014.html