卫生室可以做网站吗/品牌词优化

1493. 删掉一个元素以后全为 1 的最长子数组
题意：
给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

• 巧解

class Solution {
public:int longestSubarray(vector<int>& a) {int ans = 0, n = a.size();vector<int> a1,a2;a1.resize(n);a1[0] = a[0]; a2.resize(n);a2[n-1] = a[n-1];for(int i=1;i<n;i++){if(a[i]) a1[i] = a1[i-1]+1;}for(int i=n-2;i>=0;i--){if(a[i]) a2[i] = a2[i+1]+1;}for(int i=0;i<n;i++){int s1,s2;if(i==0) s1 = 0;else s1 = a1[i-1];if(i==n-1) s2 = 0;else s2 = a2[i+1];ans = max(ans,s1+s2);}return ans;}
};

• 滑动窗口：维护一个最多只有一个0的窗口。

class Solution {
public:int longestSubarray(vector<int>& a) {int l=0,r=0,n=a.size(),cnt=0,ans = 0;while(l<n){while(r<n && (a[r] || cnt==0)){if(a[r]==0) cnt++;r++;}ans = max(ans,r-l-1); //必须要删除一个元素if(a[l++]==0) cnt--;}return ans;}
};

1496. 判断路径是否相交
按题目意思模拟即可。

class Solution {
public:typedef pair<int,int> P;set<P> vis;bool isPathCrossing(string path) {vis.insert(make_pair(0,0));int x =0,y = 0;for(char c:path){if(c=='N'){y++;}else if(c=='E'){x++;}else if(c=='S'){y--;}else{x--;}P nP = make_pair(x,y);if(vis.count(nP)){return 1;}vis.insert(nP);}return 0;}
};

1497. 检查数组对是否可以被 k 整除
题意：
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。

考察离散数学里的模n剩余类集合，即
Zk={[0],[1],……,[k−1]}Z_k = \{[0],[1],……,[k-1]\}Zk​={[0],[1],……,[k−1]}其中$[x{]}_k$表示和$x$模$k$同余的元素的个集合。按照这个思路，去统计即可各个剩余类的个数即可，然后一一配对。

class Solution {
public:bool canArrange(vector<int>& arr, int k) {vector<int> m(k,0);for(int x:arr){m[ (x%k+k)%k ]++;}if(m[0]&1){return false;}for(int i=1;i<=k/2;i++){if(m[i]!=m[k-i]){return false;}}return true;}
};

1498. 满足条件的子序列数目
题意：
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

一个序列一共有$2^n$个子序列。但是每个子序列最大值与最小值之和有个限制，明显这具有单调性。
先排个序（虽说序列是有序的，但是题目的意思实际上取出一个子集），
而后用双指针（$l,r$）的思想，$l$从小到大进行枚举，因为是非空的，所以$l$对应的元素必须选，然后要调出一个满足题目要求的最大的$r$,这一块子集都是满足要求的，个数为$2^{r-l}$。
值得提出的是，由于单调性，$r$不需要也不能每次从$n-1$开始往左移动，否则时间复杂度就不是线性的了。

class Solution {
public:int numSubseq(vector<int>& nums, int target) {int MO = 1e9+7,n = nums.size();vector<int> mi(n+1,0);mi[0] = 1;for(int i=1;i<=n;i++){mi[i] = (mi[i-1]<<1) % MO;}sort(nums.begin(),nums.end());int l,r = n-1,ans = 0;for(l=0;l<n;l++){while(l<=r  && nums[l]+nums[r]>target ) r--;if(l>r) break;ans = (ans+mi[r-l])%MO;}return ans;}
};

1499. 满足不等式的最大值
滑动窗口+set 维护窗口内的最大值。
由于坐标x的单调性，实际上就是去找满足条件的窗口内的最大值。

class Solution {
public:int findMaxValueOfEquation(vector<vector<int>>& a, int k) {int ans = -1e9,l = 0,r = 0,n = a.size();multiset<int> vis;while(l<n){while(r<n && a[r][0]-a[l][0]<=k){vis.insert(a[r][0]+a[r][1]);r++;}vis.erase(vis.find(a[l][0]+a[l][1]));if(vis.size()) ans = max(ans,*vis.rbegin()+a[l][1]-a[l][0]); l++;}return ans;}
};

滑动窗口最大值可以使用单调队列解决，时间复杂度$O(n)$。
由于问题的相似性，自然也可以用单调队列解决。

class Solution {
public:int findMaxValueOfEquation(vector<vector<int>>& points, int k) {deque<int> dq;int ans = -1e9,n = points.size(),l=0,r=0;while(l<n){while(r<n && points[r][0]-points[l][0]<=k){int val = points[r][0]+points[r][1];while(dq.size() && dq.back()<val) dq.pop_back();dq.push_back(val);r++;}if(dq.front() == points[l][1]+points[l][0]) dq.pop_front();if(dq.size()) ans = max(ans,points[l][1]-points[l][0]+dq.front());l++;}return ans;}
};