专栏首页GiantPandaCVLeetCode 第47场双周赛题解

LeetCode 第47场双周赛题解

比赛链接

  • https://leetcode-cn.com/contest/biweekly-contest-47/

题目一:找到最近的有相同 X 或 Y 坐标的点

题解思路:直接枚举每一个点,如果这个点的x坐标或者y坐标与目标点的对应坐标相等,则与答案取最小值,并记录下最小值的下标。时间复杂度解题代码如下:

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        pair<int, int> ans(INT_MAX, -1);
        for (int i = 0; i < points.size(); i++)
            if (points[i][0] == x || points[i][1] == y)
                ans = min(ans, make_pair(abs(points[i][0] - x) + abs(points[i][1] - y), i));
        return ans.second;
    }
};

题目二:判断一个数字是否可以表示成三的幂的和

题解思路:首先,任何正整数,都可以表示为\sum_{i=0}^{\infty}3^ik_i,即三进制表示。题意即需要验证n的三进制表示中,是否每一位都是0或者1,直接模拟短除法即可。时间复杂度解题代码如下:

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            if (n % 3 > 1)
                return false;
            n /= 3;
        }
        return true;
    }
};

题目三:所有子字符串美丽值之和

题解思路:暴力枚举每一个子串并求其美丽值,但是需要注意枚举的顺序。外层枚举子串的起始坐标,内层枚举子串的长度,记录当前子串每个字母出现的次数,并计算出现次数的最大值减去出现次数最小值的差的和。时间复杂度解题代码如下:

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        for (int st = 0; st < s.size(); st++) {
            int cnt[26];
            memset(cnt, 0, sizeof(cnt));
            for (int len = 1; st + len <= s.size(); len++) {
                int idx = s[st + len - 1] - 'a';
                cnt[idx]++;
                int mx = 0;
                int mi = INT_MAX;
                for (int i = 0; i < 26; i++) {
                    if (cnt[i] > 0) {
                        mx = max(mx, cnt[i]);
                        mi = min(mi, cnt[i]);
                    }
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
};

题目四:统计点对的数目

题解思路

题意比较晦涩,需要仔细阅读。

首先,需要记录每个点的度du,然后记录每个点和他相邻的点的边的个数ecnt,为了方便,这里使用ecnt[u][v]表示点u和点v之间边的条数。

对于每一个点对(u,v),存在两种情况:

  1. u和v相邻,则此时连载u或v点上的边的条数为du[u]+du[v]-ecnt[u][v];
  2. u和v不相邻,则此时连载u或v点上的边的条数为du[u]+du[v]。

对这两类情况分开讨论即可。具体做法:

  1. 建立一个数组数组,将每个点u在树状数组下标为du[u]的地方+1;
  2. 枚举每一个点,再枚举每一个与之相邻的点,统计每个询问对于情况1的答案
  3. 在树状数组对应位置减去u以及和u相邻的点的度。
  4. 对于每一个询问queries[j],需要知道有多少个与u不相邻,且du[v]>queries[j]-du[u]的v点的个数,即当前树状数组下标从queries[j]-du[u]+1到结束的这段区间的和。
  5. 还原步骤3的操作,枚举下一个u点。

求出的答案还需要进行/2的操作。

时间复杂度**:

解题代码如下:

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<unordered_map <int, int> > ecnt(n + 1);
        vector<int> du(n + 1);
        for (auto& e : edges) {
            du[e[0]]++;
            du[e[1]]++;
            ecnt[e[0]][e[1]]++;
            ecnt[e[1]][e[0]]++;
        }
        int m = edges.size();
        int qSize = queries.size();
        vector<int> ans(qSize, 0);
        m_c = vector<int>(edges.size() + 1);
        for (int u = 1; u <= n; u++) {
            add(du[u], 1, m);
        }
        for (int u = 1; u <= n; u++) {
            add(du[u], -1, m);
            for (auto& p : ecnt[u]) {
                int v = p.first;
                add(du[v], -1, m);
                for (int i = 0; i < qSize; i++) {
                    int cnt = queries[i];
                    if (du[u] + du[v] - p.second > cnt) {
                        ans[i]++;
                    }
                }
            }
            for (int i = 0; i < qSize; i++) {
                int cnt = queries[i];
                ans[i] += sum(m) - sum(cnt - du[u]);
            }
            for (auto& p : ecnt[u]) {
                int v = p.first;
                add(du[v], 1, m);
            }
            add(du[u], 1, m);
        }
        for (auto& a : ans) a /= 2;
        return ans;
    }
private:
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int pos, int val, int m) {
        if (pos == 0) {
            m_c[0] += val;
            return;
        }
        for (int i = pos; i <= m; i += lowbit(i)) {
            m_c[i] += val;
        }
    }
    inline int sum(int pos) {
        if (pos < 0) {
            return 0;
        }
        int ans = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            ans += m_c[i];
        }
        return ans + m_c[0];
    }
    vector<int> m_c;
};

题解思路2:其实本题统计du[u]+du[v]-ecnt[u][v]>queries[j]的点的数目,可以先统计du[u]+du[v]>queries[j]的数目,这个可以将du数组排序后使用二指针的方法求得。然后在遍历ecnt,从总数中减去du[u]+du[v]-ecnt[u][v]<=queries[j]的数目即可。

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> du(n);
        unordered_map<int, int> cnt;
        vector<pair<int, int>> uedge;
        for (auto& e : edges) {
            e[0]--;
            e[1]--;
            du[e[0]]++;
            du[e[1]]++;
            int code = _getCode(e[0], e[1]);
            if (!cnt.count(code)) {
                uedge.emplace_back(e[0], e[1]);
            }
            cnt[code]++;
        }
        vector<int> sortDu = du;
        sort(sortDu.begin(), sortDu.end());
        vector<int> ans;
        for (int q : queries) {
            int sum = 0;
            int r = n - 1;
            for (int l = 0; l < n; l++) {
                while (r > l && sortDu[l] + sortDu[r] > q) r--;
                sum += n - max(l, r) - 1;
            }
            for (auto& e : uedge) {
                if (du[e.first] + du[e.second] > q &&
                    du[e.first] + du[e.second] - cnt[_getCode(e.first, e.second)] <= q) {
                    sum--;
                }
            }
            ans.emplace_back(sum);
        }
        return ans;
    }
private:
    int _getCode(int x, int y) {
        if (x > y)
            swap(x, y);
        return x << 16 | y;
    }
};

本文分享自微信公众号 - GiantPandaCV(BBuf233),作者:上决╇ф

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode第166场周赛题解

    这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接1...

    BBuf
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • OpenCV图像处理专栏十一 | IEEE Xplore 2015的图像白平衡处理之动态阈值法

    这是OpenCV图像处理专栏的第十一篇文章,之前介绍过两种处理白平衡的算法,分别为灰度世界算法和完美反射算法。今天来介绍另外一个自动白平衡的算法,即动态阈值法,...

    BBuf
  • 挑战程序竞赛系列(66):4.7字符串匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode第166场周赛题解

    这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接1...

    BBuf
  • 图论--双连通E-DCC缩点模板

    风骨散人Chiam
  • 模拟战役(DFS||并查集解法)

    题目描述 齐齐和司机在玩单机游戏《红色警戒IV》,现在他们的游戏地图被划分成一个nm的方格地图。齐齐的基地在最上方的4行格内,司机的基地在最下方的4行格内。他...

    杨鹏伟
  • 【奶昔队ROUND#1】

    模拟,不过我做的时候不是模拟,是计算...(写了好久,还wa了几次),现在看了别人的代码写过一份。

    饶文津
  • light oj 1011 - Marriage Ceremonies (状态压缩+记忆化搜索)

    大概题意是有n个男的n个女的(原谅我这么说,我是粗人),给你一个n*n的矩阵,第i行第j列表示第i个女(男)对第j个男(女)的好感度,然后要安排n对相...

    xindoo
  • 【POJ1456】Supermarket(贪心)

    每个商品有过期日期和价格,每天可以卖一个商品,必须在过期前出售才能收益,求最大收益。

    饶文津

扫码关注云+社区

领取腾讯云代金券