On the shoulders of giants.

weekly-contest-195

判断路径是否相交

给你一个字符串 path,其中 path[i] 的值可以是 'N''S''E' 或者 'W',分别表示向北、向南、向东、向西移动一个单位。

机器人从二维平面上的原点 (0, 0) 处开始出发,按 path 所指示的路径行走。

如果路径在任何位置上出现相交的情况,也就是走到之前已经走过的位置,请返回 True ;否则,返回 False

示例 1:

输入:path = "NES"
输出:false 
解释:该路径没有在任何位置相交。

示例 2:

输入:path = "NESWW"
输出:true
解释:该路径经过原点两次。

提示:

  • 1 <= path.length <= 10^4
  • path 仅由 {'N', 'S', 'E', 'W} 中的字符组成
题解

直接模拟过程,判断是否经过访问过的节点。

时间复杂度:\(O(n\log (n!))\)

class Solution {
public:
    bool isPathCrossing(string path) {
        map<pair<int, int>, bool> vis;
        int x = 0, y = 0;
        vis[make_pair(x, y)] = true;
        for(auto c : path) {
            switch(c) {
                case 'N': y += 1; break;
                case 'S': y -= 1; break;
                case 'E': x += 1; break;
                case 'W': x -= 1; break;
            }
            if(vis[make_pair(x, y)] == true) return true;
            vis[make_pair(x, y)] = true;
        }
        return false;
    }
};

检查数组对是否可以被 k 整除

给你一个整数数组 arr 和一个整数 k ,其中数组长度是偶数,值为 n

现在需要把数组恰好分成 n / 2 对,以使每对数字的和都能够被 k 整除。

如果存在这样的分法,请返回 True ;否则,返回 False

示例 1:

输入:arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出:true
解释:划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。

示例 2:

输入:arr = [1,2,3,4,5,6], k = 7
输出:true
解释:划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。

示例 3:

输入:arr = [1,2,3,4,5,6], k = 10
输出:false
解释:无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。

示例 4:

输入:arr = [-10,10], k = 2
输出:true

示例 5:

输入:arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出:true

提示:

  • arr.length == n
  • 1 <= n <= 10^5
  • n 为偶数
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5
题解

统计出每个数对 k 的余数。

  • 如果 k 是偶数,那么可以成对消除则有解
  • 如果 k 是奇数,那么除成对消除外还要让余数为 \(k / 2\) 的个数为偶数个才有解
  • 其他情况为无解

时间复杂度:\(O(n)\)

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

满足条件的子序列数目

给你一个整数数组 nums 和一个整数 target

请你统计并返回 nums 中能满足其最小元素与最大元素的 小于或等于 target非空 子序列的数目。

由于答案可能很大,请将结果对 10^9 + 7 取余后返回。

示例 1:

输入:nums = [3,5,6,7], target = 9
输出:4
解释:有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2:

输入:nums = [3,3,6,8], target = 10
输出:6
解释:有 6 个子序列满足该条件。(nums 中可以有重复数字)
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3:

输入:nums = [2,3,3,4,6,7], target = 12
输出:61
解释:共有 63 个非空子序列,其中 2 个不满足条件([6,7], [7])
有效序列总数为(63 - 2 = 61)

示例 4:

输入:nums = [5,2,4,1,7,6,8], target = 16
输出:127
解释:所有非空子序列都满足条件 (2^7 - 1) = 127

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= target <= 10^6
题解

对原数组从小到大排序,枚举每个左端点 r,使用二分找出题意的右端点 l

左端点必选,所以有 \(2^{l-r}\) 个方案(使用快速幂)。

时间复杂度:\(O(n\log n)\)

const int MOD = 1E9 + 7;
class Solution {
public:
    int Pow(int a, int x) {
        int base = a, result = 1;
        while(x) {
            if(x & 1) result = 1ll * result * base % MOD;
            base = 1ll * base * base % MOD;
            x >>= 1;
        }
        return result % MOD;
    }
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int result = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] > target - nums[i]) break;
            int p = upper_bound(nums.begin(), nums.end(), target - nums[i]) - nums.begin() - 1;
            if(p == nums.size()) p = p - 1;
            result = (result + Pow(2, p - i)) % MOD;
        }
        return result;
    }
};

满足条件的子序列数目满足不等式的最大值

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标,并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ,并且在 1 <= i < j <= points.length 的前提下, xi < xj 总成立。

请你找出yi + yj + |xi - xj|最大值,其中 |xi - xj| <= k1 <= i < j <= points.length

题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

示例 1:

输入:points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出:4
解释:前两个点满足 |xi - xj| <= 1 ,带入方程计算,则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件,得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点,所以返回 4 和 1 中最大的那个。

示例 2:

输入:points = [[0,0],[3,0],[9,2]], k = 3
输出:3
解释:只有前两个点满足 |xi - xj| <= 3 ,带入方程后得到值 0 + 0 + |0 - 3| = 3 。

提示:

  • 2 <= points.length <= 10^5
  • points[i].length == 2
  • -10^8 <= points[i][0], points[i][1] <= 10^8
  • 0 <= k <= 2 * 10^8
  • 对于所有的1 <= i < j <= points.lengthpoints[i][0] < points[j][0] 都成立。也就是说,xi 是严格递增的。
题解

设 \(i<j,x_i<x_j\), 有 \(y_i+y_j+|x_i-x_j|=y_i-x_i+y_j+x_j\)

枚举左端点,然后二分找出右端点,最后在这区间内找出 \(y_j+x_j\)的最大值(线段树)。

时间复杂度:\(O(n\log n)\)

# define lefs rt << 1
# define rigs rt << 1 | 1
# define lson lef, mid, lefs
# define rson mid + 1, rig, rigs
const int INF = 1E9;
class Solution {
public:
    vector<vector<int>> tmp;
    vector<int> sum, nums;
    int n, result = -INF;
    void build_tree(int lef, int rig, int rt) {
        if(lef == rig) {
            sum[rt] = tmp[lef][1] + tmp[lef][0];
        } else {
            int mid = lef + rig >> 1;
            build_tree(lson), build_tree(rson);
            sum[rt] = max(sum[lefs], sum[rigs]);
        }
    }
    void init(vector<vector<int>>& points) {
        this->n = points.size();
        this->tmp = points;
        this->sum = vector<int> (n << 2, -INF);
        build_tree(0, n - 1, 1);
        for(auto point : points) nums.push_back(point[0]);
    }
    int ask(int lef, int rig, int rt, int x, int y) {
        if(x <= lef && rig <= y) return sum[rt];
        int mid = lef + rig >> 1, result = -INF;
        if(x <= mid) result = max(result, ask(lson, x, y));
        if(mid < y) result = max(result, ask(rson, x, y));
        return result;
    }
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        init(points);
        for(int x = 0; x < n; x++) {
            int y = upper_bound(nums.begin(), nums.end(), k + points[x][0]) - nums.begin() - 1;
            result = max(result, points[x][1] - points[x][0] + ask(0, n - 1, 1, x + 1, y));
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注