Week303 of leetcode

LeetCode The first 303 Weekly match

Topic 1 6124. The first letter that appears twice

It's simple , According to the meaning , Use one map, Just check whether the array record has appeared .

Code ：

class Solution {
    
public:
    char repeatedCharacter(string s) {
    
        map<char,int> hash;
        for(auto x:s){
    
            if(hash.count(x)) return x;
            hash[x]++;
        }
        return 'a';
    }
};

Topic two 6125. Equal row and column pairs

Enumerate each format , Then judge the line , Whether the columns are equal . Time complexity $O(n^3)$

Code ：

class Solution {
    
public:
    int equalPairs(vector<vector<int>>& g) {
    
        int n=g.size();
        int ans=0;
        for(int i=0;i<n;i++){
    
            for(int j=0;j<n;j++){
    
                bool ok=true;
                for(int k=0;k<n;k++){
    
                    if(g[i][k]!=g[k][j]) {
    
                        ok=false;
                        break;
                    }

                }
                if(ok) ans++;
            }
        }
        return ans;
    }
};

Topic three 6126. Design food scoring system

Ideas ：

The title should realize the operation of checking the best value and changing , The first thing you can think of is the priority queue , But priority queue modification cannot be done . Then the topic is to find a certain way of cooking rating The highest value , So we can consider classification according to cooking methods , Use one map save , Then sort each category once , You can get the best value , When we think of sorting, we also think of using set Automatic sorting , Then according to the meaning of the topic , According to the first rating Sort , Press food Dictionary order , So I thought of pair Double keyword sort or , Structure overload sorting .

Then for each modification , Let's find this first food The way you cook , from map Of set Delete in , Rejoin a new rating and food

Code ：

class FoodRatings {
    
public:
    unordered_map<string,set<pair<int,string>>> h;
    map<string,string> cu;
    map<string,int> rat;
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
    
        int n=foods.size();
        for(int i=0;i<n;i++){
    
            h[cuisines[i]].insert({
    -ratings[i],foods[i]});
            cu[foods[i]]=cuisines[i];
            rat[foods[i]]=ratings[i];
        }
    }
    
    void changeRating(string food, int newRating) {
    
        string cui=cu[food];
        h[cui].erase({
    -rat[food],food});
        rat[food]=newRating;
        h[cui].insert({
    -newRating,food});
    }  
    
    string highestRated(string cuisine) {
    
        return h[cuisine].begin()->second;
    }
};

/** * Your FoodRatings object will be instantiated and called as such: * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings); * obj->changeRating(food,newRating); * string param_2 = obj->highestRated(cuisine); */

Topic four 6127. The number of high-quality pairs

Binary system , First, consider the relationship between binary bits .

We will a,b Take two numbers apart , Find out ,a|b+a&b Of 1 The number of is equal to a Of 1 The number of +b Of 1 The number of .

With this rule , Find each number 1 The number of , With arrays cnt This problem becomes to find an array , How many pairs? (i,j), bring cnt[i]+cnt[j]>=k.

take cnt After the array is sorted , There is monotony , You can use double pointer or bisection to find how many pairs .

The number of repetitions can be found not to affect the answer .

So before we do it, let's go to the heavy .

Code ：

class Solution {
    
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
    
        set<int> s;
        for(auto &x:nums) s.insert(x);//  duplicate removal 
        int n=s.size();
        vector<int> cnt;
        for(auto x:s){
    
            int sum=0;
            while(x) sum+=(x&1),x>>=1;// Get each number 1 The number of 
            cnt.push_back(sum);
        }
        long long ans=0;
        sort(cnt.begin(),cnt.end());// Sort the number , monotonous 
        int pos=-1;
        for(int i=0;i<n;i++){
    
            int l=i,r=n-1;
            while(l<=r){
    //  Find the first one that satisfies the sum of the two is greater than or equal to k The location of 
                int mid=l+r>>1;
                if(cnt[mid]+cnt[i]>=k) r=mid-1,pos=mid;
                else l=mid+1;
            }
            if(pos==-1) continue;
            if(pos!=i) ans+=(n-pos)*2ll;// because  cnt[i]+cnt[j] If meet , that （i,j)  and （j,i) There are two different answers 
            else ans+=(n-pos)*2ll-1;// If it's the same location , Only one answer 
        }
        return ans;
    }
};

After reading other people's practice , I found a simpler way , because cnt The maximum number of arrays is only 30, So we can use a bucket to record the number 1~30 How many are there in each , Then double loop enumeration is enough .