企业官网建设流程全解析

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;
}
};