✨今日算法三题

1.学生分数的最小差值

2.乘积小于k的子数组

3.考试的最大困扰度

文章目录

• ✨今日算法三题
• 一、学生分数的最小差值

• 题目描述
• 思路详解
• 代码与结果

• 二、乘积小于k的子数组

• 题目描述
• 思路详解
• 代码与结果

• 三、考试的最大困扰度

• 题目描述
• 思路详解
• 代码与结果

• ✨总结

一、学生分数的最小差值

题目描述

思路详解

首先对数组nums 进行升序排序，随后使用一个大小固定为 k 的滑动窗口在nums 上进行遍历。记滑动窗口的左边界为i，那么右边界即为i+k−1，窗口中的 k 名学生最高分和最低分的差值即为 nums[i+k−1]−nums[i]。

因为已经排过序，最右边的减去最左边的就为最高分与最低分差值，窗口长度固定，矿口在数组上滑动找出最小值。

代码与结果

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

二、乘积小于k的子数组

题目描述

思路详解

我们利用滑动窗口，当我们固定右边界之后，随着左边界的右移，滑动窗口的元素就会越来越少，乘积越来越小，当左窗口右移到一定程度就不需要右移了，因为滑动窗口乘积值越右移越小嘛。

我们先遍历固定右边界，左边界第一次从0开始遍历，之后就可以从上一次的位置直接进行遍历了。

代码与结果

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length, ret = 0;
        int prod = 1, i = 0;
        for (int j = 0; j < n; j++) {
            prod *= nums[j];
            while (i <= j && prod >= k) {
                prod /= nums[i];
                i++;
            }
            ret += j - i + 1;
        }
        return ret;
    }
}

三、考试的最大困扰度

题目描述

思路详解

首先想到是就是 把每一种的字符的最大连续个数算出来取最大就可以。

使用滑动窗口的方法，从左到右枚举右端点，维护区间中另一种字符的数量为sum，当sum 超过 k，我们需要让左端点右移，直到sum≤k。移动过程中，我们记录滑动窗口的最大长度，即为指定字符的最大连续数目。

代码与结果

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }
    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

✨总结

今天的算法主要滑动窗口为主，滑动窗口用来求连续子序列很方便，还需要多练习。

来个三连吧，小伙伴们。

😎The man who fears losing has already lost.

怕输的人已经输了。 - 《权力的游戏》😎