LeetCode Week 303

第 303 场周赛

自己选择的路,Go on happily

2351. 第一个出现两次的字母

第一个出现两次的字母

循环扫描字符串s,For each character encountered, the number of corresponding characters is incremented by one
If the first character counts 2That means the element appears first,直接返回.

复杂度o(n^3)

class Solution {
public:
    char repeatedCharacter(string s){
        char res;
        map<char,int> m;
        for(auto& c:s){
            ++m[c];
            if(m[c]==2){
                return c;}
            }
        return ' ';
        
    }
};

2352. 相等行列对

2352. 相等行列对

思路：

暴力枚举

1. n行n列的矩阵,Loop through the elements of each row and column,If the corresponding elements of the row and column are not equal then it cannot be the answer.
2. If the elements of the corresponding row and column are all equal,则答案加一.

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int row = grid[0].size();
        int col = grid.size();
        int cnt=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                 bool same = true;
                for(int k =0;k<col &&same;k++){
                    if(grid[i][k]!=grid[k][j]){
                        same = false;
                    }
                } 
                if(same){cnt++;}
            }
        }
        return cnt;
    }
};

思路二：

Transpose the matrix.

Compare the values ​​of the corresponding elements to see if they are equal

复杂度o(n^2)

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int row = grid[0].size();
        int col = grid.size();
        int cnt=0;
         bool same ;
        vector<vector<int>> Revsgrid(row,vector<int>(col));
       for(int i=0;i<row;i++){
           for(int j=0;j<col;j++){
               Revsgrid[i][j] =grid[j][i];
           }
       }
       //In fact, it is to know whether the corresponding positions are equal when comparing rows
         for(auto t:grid){
            for(auto p:Revsgrid){
        if(t==p) cnt++;
            }
             
        }
            return cnt;
       }
       
};

方法三：

hashmap

Store each row element of the matrix as a string（Because row elements can be many,不方便存储）,Then the elements of the matrix are followed“,”划分.Store each line of string in hashmap作为key,同时value加一

Transposes are stored in columns,If it is found that there is a corresponding value stored by row before,则将mp中的valueTake out and add to the result（mp中的key可能重复,So it can't just add one）

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int row = grid[0].size();
        int col = grid.size();
        int cnt=0;
         unordered_map<string, int> mp;
         bool same ;
       for(int i=0;i<row;i++){
            string s = "";
           for(int j=0;j<col;j++){
           s+=to_string(grid[i][j]);
           s+=",";
           }
           //Remove the last character,
           s.pop_back();
           mp[s]++;
       }
       //
          for(int i=0;i<row;i++){
            string s = "";
           for(int j=0;j<col;j++){
           s+=to_string(grid[j][i]);
           s+=",";
           }
           //Remove the last character,
           s.pop_back();
           if(mp.count(s)){
               cnt+=mp[s];
           }
       }
            return cnt;
       }
       
};

2353. 设计食物评分系统

2353. 设计食物评分系统

思路:

平衡树（有序集合）

我们可以用一个哈希表 \textit{fs}fs Record the food rating and cooking method for each food name,Another hash table sets a balanced tree cs Record the food score and food name set corresponding to each cooking method.

对于 changeRating 操作,先从cs[fs[food].cuisine]delete old data,然后将 newRating}newRating 和 food 记录到 cs 和fs 中.

这里pairUse negative for ratings in , 这里放入“negative rating”和字符串,这样“negative rating”小的,That is, the food with the highest rating will be ranked first

作者：endlesscheng
链接：https://leetcode.cn/problems/design-a-food-rating-system/solution/ha-xi-biao-tao-ping-heng-shu-by-endlessc-hzct/
来源：力扣（LeetCode）
著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明出处.

class FoodRatings {
    //set中pair这样设计是为了使得pairFood ratings are compared first by default,Then compare the following food name dictionary sorting
    unordered_map<string,set<pair<int,string>>> cs;;// 烹饪方式----> (食物评分,食物名字)
    unordered_map<string,pair<int,string>> fs;//食物 ---->(食物评分,烹饪方式)

public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for(int i = 0;i<foods.size();i++){
            auto& f = foods[i],&c = cuisines[i];
            //cout<<f<<":"<<c<<endl;
            int r = ratings[i];
            fs[f] = {r,c};
            //Creates an element before the element pointed to by the iterator,and returns an iterator of newly added elements;
            cs[c].emplace(-r,f);//Make sure the smallest corresponds to the highest rating
         
        }
    }
    
    void changeRating(string food, int newRating) {
        auto &[r,c] = fs[food];
        auto &s = cs[c];
        //Remove old elements
        s.erase({-r,food});
        //把新的添加进来
        s.emplace(-newRating,food);
        //Modify the rating（下一次再调用changeRatigThe value is guaranteed to be the value after the change）
        r = newRating;
    }
    
    string highestRated(string cuisine) {
        return cs[cuisine].begin()->second;
    }
};

2354. 优质数对的数目

2354. 优质数对的数目

思路：等价转换+脑筋急转弯

https://leetcode.cn/problems/number-of-excellent-pairs/solution/deng-jie-zhuan-huan-pythonjavacgo-by-end-2qzs/

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        long  res= 0L;
        unordered_map<int,int> mp;
        for(int x:unordered_set<int>(nums.begin(),nums.end())){
            mp[__builtin_popcount(x)]++;//A statistic will be performed on how many binary numbers are counted
        }
        for(auto&[cx,ccx]:mp){
            for(auto&[cy,ccy]:mp){
                if(cx+cy>=k){
                    res+=(long)ccx*ccy;
                }
            }
        }
        return res;
    }
};

总结：
This weekly competition is done through practice,并没有参加.
T1：属于一个hashmap存储,Priority is stored to2is the first letter that appears（不算难）
T2：The main underlying core is the information that can put the ranks in the question,Transpose the matrix and then compare the elements at the corresponding positions,主要有直接暴力枚举,矩阵转置,hashmap.But I feel that matrix transpose is better,hashmapThe idea is similar to matrix transpose,And don't even think about it,还有点麻烦.（个人感觉）
T3：The main thing is to set up a good data structure,be able to meet the needs of the final result.The difficulty lies in the design of the data structure.
T4：It belongs to the content related to brain teasers and collections,有点吃力.（Still don't seem to understand！）At the same time look at the analysis time,学到了__builtin_popcount(x)这一个函数.用于计算一个 32 位无符号整数有多少个位为1
The following process will continue to summarize the topics of the previous weekly competition,Do a consolidation.At the same time keep learningC++中stlSome commonly used knowledge points.