学习笔记

Appearance

定长滑动窗口 ​

1456. 定长子串中元音的最大数目 已解决 ​

题意 ​

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的元音字母为（a, e, i, o, u）。

思路 ​

  • 右侧进入，更新答案，左侧离开,
  • 初始化右侧 开始循环
  • 右侧指针可以从0开始判断元音
  • 左侧根据长度来的 i - k + 1,注意小于0 的情况；
  • 更新答案
  • 删左侧

代码 ​

cpp
class Solution {
public:
    int maxVowels(string s, int k) {
        //思路：右侧进入，更新答案，左侧离开,
        //初始化右侧 开始循环
        //右侧指针可以从0开始判断元音
        //左侧根据长度来的 i - k + 1,注意小于0 的情况；
        //更新答案
        //删左侧
        int ans = 0, v = 0;
        for(int i = 0; i < s.size(); i++){
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') v++;

            int left = i - k + 1;
            if(left < 0) continue;

            ans = max(ans,v);

            if (s[left] == 'a' || s[left] == 'e' || s[left] == 'i' || s[left] == 'o' || s[left] == 'u') v--;

        }
        return ans;
    }
};

643. 子数组最大平均数 I 已解决 ​

题意 ​

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

思路 ​

  • 通过循环遍历，循环i作为右侧点r，l ，不满足就继续+，满足就取最大，最后减掉左边;可以先求出和再平均；
  • 当nums里面的数据为负，取max得到0;
  • 写完代码一定要在脑海里模拟
  • 根据gpt的建议，作如下修改，使得不需要定义极小值

代码 ​

cpp
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        //思路：通过循环遍历，循环i作为右侧点r，l ，不满足就继续+，满足就取最大，最后减掉左边;可以先求出和再平均；
        double tmp = 0, ans = -10000000;
        for(int i = 0; i < nums.size(); i++){
            tmp += nums[i];
            //tmp /= (double)k;
            int l = i - k + 1;
            if(l < 0) continue;
            ans = max(ans,tmp);
            tmp -= nums[l];
        }
        return ans / k;
    }
};

优化写法：

cpp
double tmp = 0;
for (int i = 0; i < k; i++) tmp += nums[i];
//初始化tmp和ans
double ans = tmp / k;

常量记忆：

cpp
//求最大
int:        INT_MIN（或-2e9）
long long:  LLONG_MIN（或-1e18）
double:     -1e18（或 -inf）
//求最小
int:        INT_MAX
long long:  LLONG_MAX
double:     1e18（或 +inf）

对于inf，在leetcode无法添加库，所以用double ans = -std::numeric_limits<double>::infinity();

2090. 半径为 k 的子数组平均值 已解决 ​

题意 ​

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：中心点是数组 nums 中某个下标 i 的子数组，并具有中心点 左边 k 个元素和 右边 k 个元素。

思路 ​

  • vector初始化为-1技巧
  • 看懂报错: runtime error: signed integer overflow -> 数据范围 2e10 超过 int 上限 2e9。
  • 窗口大小（window_size）: window_size = 2 * k + 1

代码 ​

cpp
// 略 (原文档未提供完整代码，建议补充)

2841. 几乎唯一子数组最大和 已解决 ​

题意 ​

给定整数数组 nums 及正整数 m、k（1 <= m <= k <= nums.length），求长度为 k 且至少含 m 个不同元素的子数组的最大和，无此类子数组则返回 0。

思路 ​

  • 此题涉及到哈希表！
  • 不知道怎么判断子数组至少有m个互不相同的元素，查了一下用unordered_map，这个是互异，无序的
  • 窗口先写好，然后判断的时候，用 .size()

代码 ​

cpp
class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        //不知道怎么判断子数组至少有m个互不相同的元素，查了一下用unordered_map，这个是互异，无序的
        //窗口先写好，然后判断的时候，用。size（）
        long long ans = 0, tmp = 0; // 注意这里改成long long
        unordered_map<int,int> cnt;
        for(int i = 0; i < nums.size(); i++){
            tmp += nums[i];
            cnt[nums[i]]++;

            int l = i - k + 1;
            if(l < 0) continue;
            if(cnt.size() >= m) ans = max(ans,tmp);

            tmp -= nums[l];
            cnt[nums[l]]--;
            if(cnt[nums[l]]==0) cnt.erase(nums[l]); // 修正：删掉键

        }
        return ans;
    }
};

2461. 长度为 K 子数组中的最大和 已解决 ​

题意 ​

给你一个整数数组 nums 和一个整数 k 。请你找出 nums 中满足下述条件的一个子数组：

  • 长度为 k
  • 所有元素各不相同

返回满足题意子数组的最大元素和。如果不存在这样的子数组，返回 0 。

思路 ​

  • 一是unordered_map.count(val)辨析
  • .size() can count the number of elements because of the uniqueness of map
  • 注意数据类型，滑动窗口，进i，更新答案，出l，注意边界

代码 ​

cpp
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        //思路：注意数据类型，滑动窗口，进i，更新答案，出l，注意边界
        //子数组中的所有元素 各不相同 。还是不熟悉map，搞一个无序map，利用互异性(元素各不相同），size函数，count函数erase函数
        long long ans = 0,  tmp = 0;
        unordered_map<int, int> cnt;

        for(int i = 0; i < nums.size(); i++){
            tmp += nums[i];
            cnt[nums[i]]++;
            int l = i - k + 1;
            if(l < 0) continue;
            if(cnt.size() == k)
                ans = max(ans,tmp); //ans > tmp ? ans : tmp;
            tmp -= nums[l];
            cnt[nums[l]]--;
            if(cnt[nums[l]] == 0)
                cnt.erase(nums[l]);
        }
        return ans;
    }
};

1423. 可获得的最大点数 已解决 ​

题意 ​

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动，你可以从行的开头或者末尾拿走一张卡牌，最终你必须正好拿走 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

思路 ​

  • 可以从左开始拿，从右边开始拿，拿到定长为k的数目的卡片，返回卡片点数可能的最大之和；痛点在于左右两边
  • C++17引入的 reduce函数 快速计算窗口和
  • 最多，想到对立面最少，转化为定长滑动窗口
  • 需要意识到，左右两边都可以随机拿一张，可以想到所有的可能有哪些
    • 左边0个 右边k个
    • 左边1个 右边k-1个

代码 ​

反面计算：

cpp
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        //两边最大，中间最小，从0滑到n - k，最后答案要用总和减一下，另外考虑特殊情况
        //当全部都是一样的元素的时候，同上
        int ans = 1e9, tmp = 0, j = cardPoints.size() - k;
        if(j == 0) return reduce(cardPoints.begin(),cardPoints.end());
        for(int i = 0; i < cardPoints.size();i++){
            tmp += cardPoints[i];

            int l = i - j + 1;
            if(l < 0) continue;
            ans = min(ans,tmp);

            tmp -= cardPoints[l];

        }
        return reduce(cardPoints.begin(),cardPoints.end()) - ans;
    }
};

正面计算：

cpp
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int s = reduce(cardPoints.begin(), cardPoints.begin() + k);
        int ans = s;
        for (int i = 1; i <= k; i++) {
            s += cardPoints[cardPoints.size() - i] - cardPoints[k - i];
            ans = max(ans, s);
        }
        return ans;
    }
};