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 個查詢的答案。