presum|二分try+滑窗cnt
lc1198
hash统计二维矩阵中所有数字的出现次数，找出出现次数等于矩阵行数的最小数字，无则返回 -1
class Solution {
/*
输入：mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出：5
*/
public:
int smallestCommonElement(vector<vector<int>>& mat)
{
int m=mat.size(),n=mat[0].size();
unordered_map<int,int> hash;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
hash[mat[i][j]]++;
}
}
int mn=INT_MAX;
for(auto& [a,b]:hash)
{
if(b==m) mn=min(mn,a);
}
return mn==INT_MAX?-1:mn;
}
};
lc1918
堆tle...
二分try答案 + 越短越合法-滑窗_计数check vs k典题
二分猜子数组和的大小
滑窗 数出“和不超过这个数”的子数组有多少个
不断缩小范围，最终找到第k小的和
class Solution {
typedef long long ll;
public:
int kthSmallestSubarraySum(vector<int>& nums, int k)
{
int n = nums.size();
int l = *min_element(nums.begin(), nums.end());
int r = accumulate(nums.begin(), nums.end(), 0);
while (l <= r) {
int m = l + (r - l) / 2;
int c = cnt(nums, m);
if (c < k) l = m + 1;
else r = m-1;
}
return l;
}
private:
//越短越合法滑窗
int cnt(vector<int>& nums, int t)
{
int n = nums.size(), c = 0, s = 0, l = 0;
for (int r = 0; r < n; ++r) {
s += nums[r];
while (s > t) {
s -= nums[l];
l++;
}
c += r - l + 1; //不超过的子数组个数
}
return c;
}
};
lc2743
越短越合法 滑窗
ret += (r - l + 1);
class Solution {
public:
int numberOfSpecialSubstrings(string s) {
int n = s.size();
int l = 0, ret = 0;
unordered_map<char, int> hash;
for (int r = 0; r < n; r++) {
while (hash.count(s[r]) && hash[s[r]] >= 1) {
hash[s[l]]--;
l++;
}
hash[s[r]] = 1;
ret += (r - l + 1);//cal
}
return ret;
}
};
lc3652
前缀和_分为了3部分
预处理两个前缀和(ps_sum, p_sum)
枚举修改的子数组，改后利润=改前两边利润(ps_sum)+改后子数组的部分售价和(按照题目规则可知: 为k/2后半部分p_sum)，取最大利润。
class Solution {
public:
long long maxProfit(vector<int>& prices, vector<int>& strategy, int k)
{
int n = prices.size();
vector<long long> sum(n + 1), sum_sell(n + 1);
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] +prices[i] * strategy[i];
sum_sell[i + 1] = sum_sell[i] +prices[i];
}
long long ans = sum[n]; // 不修改
for (int i = k; i <= n; i++) {
long long res = sum[i - k] + sum[n] - sum[i] + sum_sell[i] - sum_sell[i - k / 2];
ans = max(ans, res);
}
return ans;
}
};