【leetcode】滑动窗口

server/2025/2/22 3:15:27/

文章目录

  • 1.长度最小的子数组
    • 1.题目
    • 2.解题思路
    • 3.代码编写
  • 2.无重复字符的最长字串
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 3.最大连续1的个数Ⅲ
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 4.将x减到0的最小操作数
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 5.水果成篮
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 6.找到字符串中所有字母异位词
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 7.串联所有单词的字串
    • 1.题目
    • 2.解题思路
    • 3.解题代码
  • 8.最小覆盖字串
    • 1.题目
    • 2.解题思路
    • 3.解题代码

1.长度最小的子数组

1.题目

题目：长度最小的子数组
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述
在这里插入图片描述

3.代码编写

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, ret = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right];while(sum >= target){ret = min(ret, right - left + 1);sum -= nums[left++];}}return ret == INT_MAX ? 0 : ret;}
};

2.无重复字符的最长字串

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述
在这里插入图片描述

3.解题代码

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> ci;int ret = 0;for(int left = 0, right = 0; right < s.size(); right++){ci[s[right]]++;while(ci[s[right]] > 1)ci[s[left++]]--;ret = max(ret, right - left + 1);}return ret;}
};

3.最大连续1的个数Ⅲ

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述
在这里插入图片描述

3.解题代码

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0,ret0 = 0;for(int left = 0, right = 0; right < nums.size();){while(right < nums.size()){ret0 += 1 - nums[right++];if(ret0 > k)break;else ret = max(ret, right - left);}while(ret0 > k){ret0 -= 1 - nums[left++];}}return ret;}
};

4.将x减到0的最小操作数

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述

3.解题代码

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0, ret = -1, n = nums.size();for(int s : nums)sum += s;int target = sum - x;int sum1 = 0;//小细节，要注意if(target < 0) return -1;for(int left = 0, right = 0; right < n; right++){//1.进窗口sum1 += nums[right];//2.判断 出窗口while(sum1 > target)sum1 -= nums[left++];//3.判断 更新retif(sum1 == target) ret = max(ret, right - left + 1);}//输出时也要注意if(ret == -1) return ret;else return n - ret;}
};

5.水果成篮

1.题目

题目链接
在这里插入图片描述

2.解题思路

在这里插入图片描述

3.解题代码

class Solution {
public:int totalFruit(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size(), ret = 0;if(n == 0) return 0;for(int left = 0, right = 0; right < n; right++){hash[nums[right]]++;while(hash.size() > 2) {hash[nums[left]]--;if(hash[nums[left]] == 0)hash.erase(nums[left]);left++;}ret = max(ret, right - left + 1);}return ret;}
};

优化时间复杂度

class Solution {
public:int totalFruit(vector<int>& nums) {//unordered_map<int, int> hash;int hash[100001] = {0};int n = nums.size(), ret = 0;if(n == 0) return 0;for(int left = 0, right = 0,kinds = 0; right < n; right++){if(hash[nums[right]] == 0) kinds++;hash[nums[right]]++;while(kinds > 2) {hash[nums[left]]--;if(hash[nums[left]] == 0)kinds--;left++;}ret = max(ret, right - left + 1);}return ret;}
};

6.找到字符串中所有字母异位词

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述
在这里插入图片描述

3.解题代码

//完全理解题意和思路后 写出来的代码
class Solution {
public:vector<int> findAnagrams(string s, string p) {int m = p.size(), n = s.size(), hash1[26] = {0}, hash2[26] = {0};vector<int> ret;for(auto c : p) hash2[c - 'a']++;for(int left = 0, right = 0, count = 0; right < n; right++){hash1[s[right] - 'a']++;if(hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) count++;if(right - left + 1 > m){if(hash1[s[left] - 'a'] <= hash2[s[left] - 'a']) count--;hash1[s[left] - 'a']--;left++;}if(count == m) ret.push_back(left);}return ret;}
};

//第一次看题解写出来的代码，当时不是很懂
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;array<int, 26> cnt_s{};array<int, 26> cnt_p{};for (auto s : p){cnt_p[s - 'a']++;}int n = s.size();int left = 0;for(int right = 0; right < n; right++){cnt_s[s[right] - 'a']++;if (right - left + 1 < p.length())continue;if (cnt_s == cnt_p)ans.push_back(left);cnt_s[s[left] - 'a']--;left++;}return ans;}
};

7.串联所有单词的字串

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述

3.解题代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;int n = s.size(), m = words.size(), len = words[0].size();for(auto& ss : words){hash1[ss]++;}for(int i = 0; i < len; i++){unordered_map<string, int> hash2;for(int left = i, right = i, count = 0; right + len <= n; right += len){string in = s.substr(right, len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) count++;if(right - left + 1 > len * m) {string out = s.substr(left, len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;left += len;hash2[out]--;}if(count == m) ret.push_back(left);}}return ret;}
};

8.最小覆盖字串

1.题目

题目链接
在这里插入图片描述
在这里插入图片描述

2.解题思路

在这里插入图片描述

3.解题代码

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> hash1, hash2;int n = s.size();for(auto ss : t) hash1[ss]++;int m = hash1.size(), pos = 0, length = 100001;for(int left = 0, right = 0, count = 0; right < n; right++){char in = s[right];hash2[in]++;if(hash1.count(in) && hash2[in] == hash1[in]) count++;while(count == m) {if(length > right - left + 1){length = right - left + 1;pos = left;}char out = s[left];if(hash1.count(out) && hash2[out] == hash1[out]) count--;hash2[out]--;left++;}}string ret = s.substr(pos, length);if(length == 100001) ret = "";return ret;}
};

http://www.ppmy.cn/server/169731.html

相关文章

前端面试题---vite和webpack的区别

前端面试题---vite和webpack的区别

Vite 和 Webpack 的 简短对比&#xff0c;突出最重要的区别&#xff1a; 1. 构建速度 Vite&#xff1a;开发时极速&#xff0c;按需构建和热更新&#xff0c;启动非常快。 Webpack&#xff1a;构建较慢&#xff0c;尤其在大项目中需要全量打包。 2. 开发体验 Vite&#xff…
阅读更多...
单片机的原理

单片机的原理

单片机的原理 处理器与存储器 单片机的核心是处理器&#xff0c;通常是一个 8、16 或 32 位的微处理器&#xff0c;它负责执行存储在存储器中的程序指令。存储器分为程序存储器和数据存储器&#xff0c;程序存储器通常使用 Flash 或 EPROM 存储程序代码&#xff0c;而数据存储器…
阅读更多...
MySQL中 undolog和redolog区别

MySQL中 undolog和redolog区别

MySQL&#xff0c;**Undo Log&#xff08;撤销日志&#xff09;和Redo Log&#xff08;重做日志&#xff09;**是两种非常重要的日志机制&#xff0c;它们用于保证事务的原子性、一致性、隔离性和持久性&#xff08;ACID特性&#xff09;&#xff0c;并在数据库恢复过程中发挥关…
阅读更多...
unity学习50：NavMeshAgent 区域Areas和cost

unity学习50：NavMeshAgent 区域Areas和cost

目录 1 NavMeshAgent 区域和成本的问题 2 区域Areas 2.1 区域和颜色 2.2 区域和成本 2.3 区域成本的作用 2.4 地图测试准备 2.5 如何实现 2.5.1 unity的2022之前的老版本 2.5.2 unity的2022之后的新版本 2.6 如果测试失败&#xff0c;是因为没有bake 2.7 测试前&…
阅读更多...
Redis- 对象专辑

Redis- 对象专辑

Redis-常见数据类型和应用 前言什么是对象Redis ObjectString对象常用操作写操作读操作删除操作 底层实现源码解释embstr和raw 比较 什么是SDS 使用场景常规计数分布式锁 List对象元素限制常用操作创建更新删除 编码方式ZIPLISTLINKEDLISTQUICKLISTLISTPACK编码 压缩列表什么是…
阅读更多...
python-leetcode-编辑距离

python-leetcode-编辑距离

72. 编辑距离 - 力扣&#xff08;LeetCode&#xff09; class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n len(word1), len(word2)dp [[0] * (n 1) for _ in range(m 1)]# 初始化for i in range(m 1):dp[i][0] i # 只能删除for j in range…
阅读更多...
Linux系统中常见的词GNU是什么意思？

Linux系统中常见的词GNU是什么意思？

GNU 是 “GNU’s Not Unix” 的递归缩写&#xff0c;它是一个自由软件项目&#xff0c;旨在创建一个完全自由的操作系统。这个名字反映了GNU项目的核心理念&#xff1a;它试图创建一个类Unix的系统&#xff0c;但不是Unix本身。 GNU 项目由 理查德斯托曼&#xff08;Richard S…
阅读更多...
【数据挖掘】ARFF格式与数据收集

【数据挖掘】ARFF格式与数据收集

【数据挖掘】ARFF格式与数据收集 三级目录1. ARFF格式与数据收集2. 稀疏数据3. 属性类型4. 缺失值与不正确的值5. 了解数据6. 知识表达7. 聚类机器学习算法训练数据挖掘分析数据共享与交换 三级目录 1. ARFF格式与数据收集 ARFF&#xff08;Attribute - Relation File Format…
阅读更多...
最新文章

Copyright @ 2022~2023