2025年【英雄算法联盟】6月集训Day6.滑动窗口

【英雄算法联盟】6月集训Day6.滑动窗口一 今日练习题目 1984 学生分数的最小差值 给你一个 下标从 0 开始 的整数数组 nums 其中 nums i 表示第 i 名学生的分数 另给你一个整数 k 从数组中选出任意 k 名学生的分数 使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 返回可能的 最小差值 1763

大家好,我是讯享网,很高兴认识大家。

一、今日练习题目:

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]-- 即可。

小讯
上一篇 2025-01-10 12:21
下一篇 2025-04-10 08:52

相关推荐

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