LeetCode.195场周赛

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