1456. 定长子串中元音的最大数目
【链接】：1456. 定长子串中元音的最大数目 class Solution {public: int maxVowels(string s, int k) { int res = 0; // 记录整个过程中的最大值 int count = 0; // 记录当前滑动窗口内元音字母的数字 for(int l = 0, r = 0; r < s.size(); ++r) { // 右侧元素进入窗口 // 上来先判断是否是元音字母 if(s[r] == 'a' || s[r] == 'e' || s[r] == 'i' || s[r] == 'o' || s[r] == 'u') { count++; } res = max(count, res); ...
1343. 大小为 K 且平均值大于等于阈值的子数组数目
【题目】：1343. 大小为 K 且平均值大于等于阈值的子数组数目 class Solution {public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { int count = 0; // 计算满足条件的数 int curSum = 0; // 计算当前滑窗内的总数 int targetSum = k * threshold; // 当前滑窗内的总数满足条件的最小值 for(int l = 0, r = 0; r < arr.size(); ++r) { curSum += arr[r]; if(r - l + 1 == k) { // 条件1. 长度为k if(curSum >= targetSum) { // 条件2. 平均值大于等于threshold ...
1052. 爱生气的书店老板
【题目】：1052. 爱生气的书店老板 class Solution {public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) { int maxAddCount = 0; // 在minutes长度内，还能增加的最大顾客满意人数 int curAddCount = 0; // 当前窗口内还能增加的顾客满意数 int curCount = 0; // 原本有的顾客满意数 int n = customers.size(); for(int l = 0, r = 0; r < n; ++r) { if(grumpy[r] == 1) { // 把老板从生气变成不生气 curAddCount += customers[r]; ...
643. 子数组最大平均数 I
【链接】：643. 子数组最大平均数 I class Solution {public: double findMaxAverage(vector<int>& nums, int k) { int maxSum = INT_MIN, curSum = 0; for(int l = 0, r = 0; r < nums.size(); ++r) { curSum += nums[r]; // 更新curSum if(r - l + 1 == k) { maxSum = max(maxSum, curSum); // 更新maxSum(因为题目要求长度为k，所以需要在这里更新maxSum) curSum -= nums[l]; // 扣除左侧元素（保持一致） ++l; // 左侧元素离开 } } ...
15. 三数之和
【题目】：15. 三数之和 class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); ++i) { if(nums[i] > 0) { break;// 因为是升序排列，如果当前数>0，三数值和一定>0，后边的数字都可以做剪枝 } if(i != 0 && nums[i] == nums[i - 1]) { continue; // 去除重复的三元组 ...
49. 字母异位词分组
【题目】：49. 字母异位词分组 方法1：直接对字符串进行排序后使用map存储相同的字母异位词，再把map的value依次存放到结果中。 class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> mp; for(string str : strs) { string temp = str; sort(str.begin(), str.end()); mp[str].push_back(temp); } for(auto [key, value] : mp)...
283. 移动零
【题目】：283. 移动零 class Solution {public: void moveZeroes(vector<int>& nums) { for(int l = 0, r = 0; r < nums.size(); ++r) { if(nums[r] != 0) { swap(nums[l++], nums[r]); } } }}; 时间复杂度: O(n) 空间复杂度: O(1) 先把非0的元素移到前边，后边剩下的就是0了。l：非0元素的末尾r：0元素的开头
11. 盛最多水的容器
【题目】：11. 盛最多水的容器 class Solution {public: int maxArea(vector<int>& height) { int n = height.size(); int res = (n - 1) * min(height[0], height[n - 1]); for(int l = 0, r = n - 1; r > l;) { if(height[l] < height[r]) { // 移动更短的木棍 l++; }else { --r; } res = max(res, (r - l) * min(height[l], height[r])); // 每次记录当前遍历过的最大值 } return...
128. 最长连续序列
【题目】：128. 最长连续序列 class Solution {public: int longestConsecutive(vector<int>& nums) { unordered_set<int> ss(nums.begin(), nums.end()); int res = 0; for(int s : ss) { if(ss.find(s - 1) != ss.end()) { continue; // 说明s一定不是开头 } // s是开头 int y = s + 1; while(ss.find(y) != ss.end()) { y++; } res = max(y - s, res); ...
C++算法
algorithm库函数#include<algorithm>using namespace std; 排序：sort(beigin,end) 范围：[begin , end) //例1.vector<int> vec;//一顿操作后...sort(vec.begin(),vec.end());//例2.int num[20];sort(num,num+20); 设置排序的规则：sort(begin,end,comp) comp相当于函数的函数名 bool comp(lhs,rhs) lhs、rhs是待排序元素 不发生交换：返回真 发生交换：返回假 如果排序不是稳定的，但是题目要求定，可以加入int seq;用来记录录入的顺序，实现稳定排序 String 关于字符数据的两种输入： char buf[100];//1scanf("%s",buf);//只能读取一个单词（遇到空格停止）//2fgets(buf,100,stdin);//只能读取一整行（包括换行符）//去掉末尾换行符：string str =...
