Leetcode 双周赛（47）

5680. 找到最近的有相同 X 或 Y 坐标的点

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中

points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y

坐标时，我们称这个点是 有效的 。

请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小

的一个。如果没有有效点，请返回 -1 。

两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。

示例 1：
输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
输出：2
解释：所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。

示例 2：
输入：x = 3, y = 4, points = [[3,4]]
输出：0
提示：答案可以与你当前所在位置坐标相同。

示例 3：
输入：x = 3, y = 4, points = [[2,3]]
输出：-1
解释：没有有效点。
           

代码

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

5681. 判断一个数字是否可以表示成三的幂的和

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

示例 1：
输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：
输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：
输入：n = 21
输出：false
           

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

5682. 所有子字符串美丽值之和

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

比方说，“abaacc” 的美丽值为 3 - 1 = 2 。 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

示例 1：
输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：
输入：s = "aabcbaa"
输出：17
           

class Solution {
public:
    int cnt[26],ans=0;
    int beautySum(string s) {
        int n=s.size();
        
        for(int i=0;i<n;i++){
            for(int& k:cnt) k=0;
            for(int j=i;j<n;j++){
                cnt[s[j]-'a']++;
                int mi=1e9,ma=0;
                for(int &x:cnt) if(x){
                    ma=max(ma,x);
                    mi=min(x,mi);
                }
                ans+=ma-mi;
            }
        }
        return ans;
    }
};
           

5683. 统计点对的数目

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和

vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

a < b cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。 请你返回一个数组 answers

，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。