leetcode(c++)(滑动窗口)
2022/5/10 22:00:28
本文主要是介绍leetcode(c++)(滑动窗口),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream> #include <vector> #include <string> #include <unordered_map> #include <unordered_set> using namespace std; int lengthofLongestSubString(string s) { int n = s.size(),left = -1, res = 0; unordered_set<char>set; for(int i = 0; i < n ; ++i) { if(i != 0) { set.erase(s[i-1]); } while(left+1 < n && !set.count(s[left+1])) { set.insert(s[left+1]); ++left; } res = max(res,left - i + 1); } return res; } int lengthOfLongestSubstringDistinct(string s) { unordered_map<char,int>map; int left = 0, res = 0; for(int i = 0; i < s.size(); ++i) { char cur = s[i]; ++map[cur]; while(map.size() > 2) { char c = s[left]; --map[c]; if(map.at(c)==0)map.erase(c); ++left; } res = max(res, i - left + 1); } return res; } int lengthOfLongestSubstringDistinctK(string s,int k) { int left = 0, res = 0; unordered_map<char,int>map; for(int i = 0; i < s.size(); ++i) { char cur = s[i]; ++map[cur]; while(map.size() > k) { char c = s[left]; --map[c]; if(map[c] == 0)map.erase(c); ++left; } res = max(res, i - left + 1); } return res; } string minWindow(string s, string t) { unordered_map<char,int>map; for(char c:t) { ++map[c]; } int left = 0, minStart = 0, minLen = INT_MAX, cnt = 0; for(int i = 0; i < s.size(); ++i) { char c = s[i]; if(map.count(c)) { if(map[c]>0)++cnt; --map[c]; } while(cnt == t.size()) { if(i - left + 1 < minLen) { minLen = i - left + 1; minStart = left; } char leftChar = s[left]; if(map.count(leftChar)) { ++map[leftChar]; if(map[leftChar] > 0) --cnt; } ++left; } } if(minLen == INT_MAX)return ""; return s.substr(minStart,minLen); } int longestSubstring(string s, int k) { int res = 0; for(int unique = 1; unique <= 26; ++unique) { unordered_map<char,int>map; int left = 0,cnt = 0; for(int i = 0; i < s.size(); ++i) { char c = s[i]; ++map[c]; if(map[c] == k)++cnt; while(map.size() > unique) { char leftChar = s[left]; if(map[leftChar]==k)--cnt; --map[leftChar]; if(map[leftChar] == 0)map.erase(leftChar); ++left; } int count = map.size(); if(count == unique && count == cnt)res = max(res,i-left+1); } } return res; } int minSubArrayLen(int target,const vector<int>& nums) { int left = 0, n = nums.size(),res = INT_MAX, sum = 0; for(int i = 0; i < n; ++i) { sum += nums[i]; while(sum >= target) { res = min(res,i - left + 1); sum -= nums[left++]; } } return res == INT_MAX ? 0 : res; } int characterReplace(string s, int k) { int n = s.size(); vector<int>cnt(26); int left = 0, res = 0; for(int i = 0; i < n ;++i) { ++cnt[s[i]-'A']; while(i - left + 1 - *max_element(cnt.begin(),cnt.end()) > k) { --cnt[s[i]-'A']; ++left; } res = max(res,i-left+1); } return res; } int atMost(const vector<int>& nums,int k) { int left = 0, res = 0; unordered_map<int,int>map; for(int i = 0; i < nums.size(); ++i) { if(!map.count(nums[i]) || map[nums[i]] == 0)--k; ++map[nums[i]]; while(k < 0) { --map[nums[left]]; if(map[nums[left]]== 0) ++k; ++left; } res += i - left + 1; } return res; } int subArraysWithDistinct(const vector<int>&nums,int k) { return atMost(nums,k) - atMost(nums,k-1); } int atMost1(const vector<int>&nums,int k) { int res = 0, left = 0, n = nums.size(); for(int i = 0; i < n; ++i) { k -= nums[i] % 2; while(k < 0) k += nums[left++]%2; res += i - left + 1; } return res; } int numberofNiceNumber(const vector<int>& nums,int k) { return atMost1(nums,k) - atMost1(nums,k-1); } int main() { //LeetCode3 string s = "abcabcbb"; cout << lengthofLongestSubString(s) << endl; //LeetCode159 s = "ccaabbb"; cout << lengthOfLongestSubstringDistinct(s) << endl; //LeetCode340 s = "aa"; int k = 1; cout << lengthOfLongestSubstringDistinctK(s,k) << endl; //LeetCode76 s = "ADOBECODEBANC"; string t = "ABC"; cout << minWindow(s,t) << endl; //LeetCode395 s = "aaabb"; k = 3; cout << longestSubstring(s,k) << endl; //LeetCode209 vector<int>nums{2,3,1,2,4,3}; int target = 7; cout << minSubArrayLen(target,nums) << endl; //LeetCode424 s = "ABAB"; k = 2; cout << characterReplace(s,k) << endl; //LeetCode992 nums = {1,2,1,2,3}; k = 2; cout << subArraysWithDistinct(nums,k) << endl; //LeetCode1248 nums = {1,1,2,1,1}; k = 3; cout << numberofNiceNumber(nums,k) << endl; return 0; }
这篇关于leetcode(c++)(滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!