讨论/技术交流/🐱 第 47 场夜喵双周赛/
🐱 第 47 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 找到最近的有相同 X 或 Y 坐标的点
4 分 - 判断一个数字是否可以表示成三的幂的和
5 分 - 所有子字符串美丽值之和
6 分 - 统计点对的数目

2
共 52 个回复

Leetcode 第47场双周赛题解

Problem A - 找到最近的有相同 X 或 Y 坐标的点

模拟即可。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int ans = -1;
        int best = 100000;
        for (int i = 0;i < points.size(); ++i) {
            int xi = points[i][0], yi = points[i][1];
            if (xi == x && abs(yi - y) < best) {
                best = abs(yi - y);
                ans = i;
            }
            if (yi == y && abs(xi - x) < best) {
                best = abs(xi - x);
                ans = i;
            }
        }
        return ans;
    }
};

Problem B - 判断一个数字是否可以表示成三的幂的和

从最大的3的幂开始,如果大于等于剩余数字,就应当使用这一幂次(因为剩下的所有幂次加起来也比它小)。看最后是否能减到0。

  • 时间复杂度O(log3N)\mathcal{O}(\log_3N)
  • 空间复杂度O(log3N)\mathcal{O}(\log_3N)
class Solution {
public:
    bool checkPowersOfThree(int n) {
        vector<int> threes{1};
        while (threes.back() < n)
            threes.emplace_back(threes.back() * 3);
        for (int i = threes.size() - 1; i >= 0; --i) {
            if (n >= threes[i])
                n -= threes[i];
        }
        return n == 0;
    }
};

Problem C - 所有子字符串美丽值之和

枚举子串起点,用multiset维护不同字符的出现频次。

  • 时间复杂度O(N2log)\mathcal{O}(N^2\log|\sum|)
  • 空间复杂度O(N+)\mathcal{O}(N+|\sum|)
class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            multiset<int> st;
            vector<int> cnt(26);
            for (int j = i; j < n; ++j) {
                int c = s[j] - 'a';
                if (st.find(cnt[c]) != st.end())
                    st.erase(st.find(cnt[c]));
                st.insert(++cnt[c]);
                ans += *st.rbegin() - *st.begin();
            }
        }
        return ans;
    }
};

Problem D - 统计点对的数目

先假设(a,b)(a,b)的公共边可以计算两次,这时可以对度数排序后双指针求解。

再考虑删去无效点对。一个点对应该被删去,当且仅当:

  • deg[a]+deg[b]>targetdeg[a]+deg[b]>target

  • 同时deg[a]+deg[b]cnt[(a,b)]targetdeg[a]+deg[b]-cnt[(a,b)]\leq target

  • 时间复杂度O(VlogV+VQ+EQ)\mathcal{O}(V\log V+VQ+EQ)

  • 空间复杂度O(E+V+Q)\mathcal{O}(E+V+Q)

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        int q = queries.size();
        vector<int> deg(n + 1);
        unordered_map<int, int> cnt;
        for (auto &edge : edges) {
            int u = edge[0], v = edge[1];
            if (u > v)
                swap(u, v);
            cnt[u * (n + 1) + v]++;
            deg[u]++;
            deg[v]++;
        }
        vector<int> s(deg);
        sort(s.begin(), s.end());
        vector<int> ans(q);
        for (int i = 0; i < q; ++i) {
            int target = queries[i];
            int r = n;
            for (int l = 1; l < n; ++l) {
                r = max(r, l + 1);
                while (r - 1 > l && s[l] + s[r - 1] > target)
                    r--;
                if (s[l] + s[r] > target)
                    ans[i] += n - r + 1;
            }
            for (auto [key, val] : cnt) {
                int u = key / (n + 1), v = key % (n + 1);
                if (deg[u] + deg[v] > target && deg[u] + deg[v] - val <= target)
                    ans[i]--;
            }
        }
        return ans;
    }
};
27

第一次做出了3题 泪目了

7

wc...t3 Python的暴力方法t, 换C++ a了???
t4又是个什么鬼, 比赛结束后4min愣是做出来了...

4

都说了是无向边,(1,2)和(2,1)居然还是算两条不同的边,艹

2

知道我今天笔试挂了故意出三道简单题安慰我。力扣,你好温柔😭

2

第四道题的queries求的啥根本看不懂- -

2

0点结束的时候第三题通过用户数应该是破了1k的

1

我也是啊,老铁

1

谢谢大佬

1

我是菜逼,鉴定完毕

1