1496. 判断路径是否相交
给你一个字符串 path，其中 path[i] 的值可以是'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。
机器人从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。
如果路径在任何位置上出现相交的情况，也就是走到之前已经走过的位置，请返回 True ；否则，返回 False 。
分析
用map标记当前点是否已经走到，然后模拟走的过程，每走一步判断一下即可。
class Solution {
public:
bool isPathCrossing(string path) {
map<pair<int,int>,bool> st;
st.clear();
int x = 0, y = 0;
int n = path.length();
st[{0,0}] = true;
for(int i = 0; i<n; i++){
if(path[i] == 'N') x--;
else if(path[i] == 'S') x++;
else if(path[i] == 'E') y++;
else y--;
if(st[{x,y}]) return true;
else st[{x,y}] = true;
}
return false;
}
};
1497. 检查数组对是否可以被 k 整除
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成n / 2对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
分析
统计余数的个数，对于余数x，如果x和k-x个数相同，就满足上述条件，注意判断余数为0的个数的奇偶性。
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
vector<int> h(k,0); //统计余数个数
for(auto &x:arr){
int t = (x%k+k)%k;
h[t]++;
}
if(h[0]&1) return 0;
for(int i = 1; i<k; i++){
//cout<<h[i] <<" "<<h[k-1]<<endl;
if(h[i] != h[k-i]) return false;
}
return true;
}
};
1498. 满足条件的子序列数目
给你一个整数数组 nums 和一个整数target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
分析
子序列不要求连续的，所有我们可以将数组排序，然后利用双指针i和j，对一个i来说，j从右边走，找到满足i + j <= target的最大的j，这样，i个j之间每多一个数，就会对答案贡献2^1。
typedef long long LL;
const int mod = 1e9+7;
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int b[100100];
memset(b,0,sizeof b);
sort(nums.begin(),nums.end());
int n = nums.size();
int ans = 0;
//预处理出2^i的值
b[0] = 1;
for(int i = 1; i<=n; i++){
b[i] = (b[i-1]+b[i-1])%mod;
}
for(int i = 0,j=n-1; i<n; i++){
while(j>=i && nums[i]+nums[j]>target) j--;
int k = j-i;
if(k>=0) ans = (ans+b[k])%mod;
}
return ans;
}
};
1499. 满足不等式的最大值
给你一个数组points和一个整数k。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi]，并且在 1 <= i < j <= points.length的前提下，xi < xj总成立。
请你找出yi + yj + |xi - xj|的 最大值，其中|xi - xj| <= k 且 1 <= i < j <= points.length。
题目测试数据保证至少存在一对能够满足|xi - xj| <= k 的点。
分析
有个很好的性质，在 1 <= i < j <= points.length的前提下，xi < xj总成立。
所以yi + yj + |xi - xj|，可转化为yj + xj + yi - xi，那么我们可以用大根堆来维护yi + yj，每次对于i，只要堆顶元素是在i之后的，就可以更新答案。
class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
//先写暴力
long long ans = -2e9;
int n = points.size();
priority_queue<pair<int,int> > h;
for(int i = 0,j = 0; i<n; i++){
int now = points[i][1]-points[i][0];
while(j<n && points[j][0]-points[i][0]<=k){
h.push({points[j][0]+points[j][1],points[j][0]});
++j;
}
//cout<<"j"<<" "<<j<<endl;
while(h.size() && h.top().second<=points[i][0]) {
//cout<<h.top().second<<endl;
h.pop();
}
if(h.size()){
//cout<<h.top().first<<endl;
ans = max(ans,(long long)h.top().first+now);
//cout<<"ans "<<ans<<endl;
}
}
return ans;
}
};
