Promoting practice with competition - Reflection on the 303th weekly match

Continue to play weekly matches from this week , Try to promote practice with competition , In the future, I also want to record some problems that I won't know about the weekly competition , And others' good ideas .

This time only AC The first two questions , Basically simulation , There's nothing to say . The third question was originally thought to be interval modification , Line segment tree , As a result, I can't even think about my line segment tree , So try HashMap<String,HashMap<String,Integer>> simulation , result TLE, After that 72/77, I. check that 2x10⁴xN It's really super , Time is running out ; At first glance, the fourth question is associated with the dictionary tree made before , The result has nothing to do with the number of high-quality pairs , Sorting first and then trying to dichotomy on the tree can't be achieved . To make a long story short , Or there are too few types of questions , The use of containers is also unskilled .

Big guy's hand speed field , My reflection field , Ah , The road of algorithm is still blocked and long .

T3.6126. Design food scoring system

Design a food scoring system that supports the following operations ：

Modify the score of a certain food listed in the system .
Return to the food with the highest score under a certain cooking method in the system . Realization FoodRatings class ：

FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initialize system . Food by foods、cuisines and ratings describe , The length is n.
foods[i] It's No i The name of the food .
cuisines[i] It's No i How to cook food .
ratings[i] It's No i The initial score of the food .
void changeRating(String food, int newRating) Change the name to food Score of food .
String highestRated(String cuisine) Return to the specified cooking method cuisine Name of the food with the highest score . If there is juxtaposition , Return names with smaller dictionary order . Be careful , character string x The dictionary order of is better than that of string y The smaller premise is ：x The position that appears in the dictionary is y Before , in other words , or x yes y The prefix of , Or meet x[i] != y[i] The first position i It's about ,x[i] The position appearing in the alphabet is y[i] Before .

Example ：

Input [“FoodRatings”, “highestRated”, “highestRated”, “changeRating”,
“highestRated”, “changeRating”, “highestRated”] [[[“kimchi”, “miso”,
“sushi”, “moussaka”, “ramen”, “bulgogi”], [“korean”, “japanese”,
“japanese”, “greek”, “japanese”, “korean”], [9, 12, 8, 15, 14, 7]],
[“korean”], [“japanese”], [“sushi”, 16], [“japanese”], [“ramen”, 16],
[“japanese”]] Output [null, “kimchi”, “ramen”, null, “sushi”, null,
“ramen”]

explain FoodRatings foodRatings = new FoodRatings([“kimchi”, “miso”,
“sushi”, “moussaka”, “ramen”, “bulgogi”], [“korean”, “japanese”,
“japanese”, “greek”, “japanese”, “korean”], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated(“korean”); // return “kimchi”
// “kimchi” Korean cuisine with the highest score , The score is 9 . foodRatings.highestRated(“japanese”); // return “ramen”
// “ramen” It is the Japanese cuisine with the highest score , The score is 14 . foodRatings.changeRating(“sushi”, 16); // “sushi” Now the score is changed to 16 .
foodRatings.highestRated(“japanese”); // return “sushi”
// “sushi” It is the Japanese cuisine with the highest score , The score is 16 . foodRatings.changeRating(“ramen”, 16); // “ramen” Now the score is changed to 16 .
foodRatings.highestRated(“japanese”); // return “ramen”
// “sushi” and “ramen” The scores are all 16 .
// however ,“ramen” The dictionary order of “sushi” smaller .

Tips ：

1 <= n <= 2 * 10⁴
n == foods.length == cuisines.length ==ratings.length
1 <= foods[i].length, cuisines[i].length <= 10
foods[i]、cuisines[i] It's made up of lowercase letters
1 <= ratings[i] <= 10⁸
foods All strings in are different from each other
In the face of changeRating In all calls of ,food Is the name of the food in the system .
In the face of highestRated In all calls of ,cuisine It's in the system At least one The way food is cooked .
Call at most changeRating and highestRated A total of 2 * 10⁴ Time

In my previous simulation ,String highestRated(String cuisine) Is to traverse all dish names , Find out how to cook and cuisine Compare the same dishes ,2x10⁴xN There is a timeout . Here we optimize , Due to the need to return to a cooking method rating The name of the tallest dish , Similar can be used TreeMap<Food> The data structure stores dishes of the same cooking method , And define its sorting rules , Although the total time to establish red and black trees is O(NlogN), But the sorted query only needs 2x10⁴ xO(1), Finally, the same kind of dishes are used HashMap<String,TreeMap<Food>> Storage .

class FoodRatings {
    
    public class Food{
    
        String foodname;
        String cuisine;
        int rating;
        public Food(String _foodname, String _cuisine, int _rating){
    
            this.foodname=_foodname;
            this.cuisine=_cuisine;
            this.rating=_rating;
        }
    }
    // Cooking methods and food Mapping , be used for String highestRated(String cuisine)
    HashMap<String,TreeSet<Food>> map;
    // Dish name and food Mapping , be used for void changeRating(String food, int newRating)
    HashMap<String,Food> objMap;
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
    
        int len=foods.length;
        map=new HashMap<>();
        objMap=new HashMap<>();
        for(int i=0;i<len;i++){
    
            Food food=new Food(foods[i],cuisines[i],ratings[i]);
            TreeSet<Food> cuiSet=map.getOrDefault(cuisines[i],new TreeSet<>(
                (o1,o2)->{
    
                    if(o1.rating==o2.rating){
    
                        // Dictionary order, ascending order ,o1->o2 Small minus large 
                        return o1.foodname.compareTo(o2.foodname);
                    }else{
    
                        return o2.rating-o1.rating;
                    }
                }
            ));
            cuiSet.add(food);
            map.put(cuisines[i],cuiSet);
            objMap.put(foods[i],food);
        }
    }
    
    public void changeRating(String foodname, int newRating) {
    
        Food foodObj=objMap.get(foodname);
        String _cuisine=foodObj.cuisine;
        Food newFood=new Food(foodname,_cuisine,newRating);
        TreeSet<Food> cuiSet=map.get(_cuisine);
        // The original TreeSet Delete old nodes 
        cuiSet.remove(foodObj);
        cuiSet.add(newFood);
        map.put(_cuisine,cuiSet);
        objMap.put(foodname,newFood);
    }
    
    public String highestRated(String cuisine) {
    
        TreeSet<Food> cuiSet=map.get(cuisine);
        Food food=cuiSet.first();
        return food.foodname;
    }
}

/** * 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); */

Among them lambda Expression creation TreeSet Your code is worth learning , The sorting rule is defined in multiple lines , need (o1,o2)->{ } There are brackets , And there is no semicolon at the end of the sorting statement ;：

TreeSet<Food> cuiSet=map.getOrDefault(cuisines[i],new TreeSet<>(
                (o1,o2)->{
    
                    if(o1.rating==o2.rating){
    
                        // Dictionary order, ascending order ,o1->o2 Small minus large 
                        return o1.foodname.compareTo(o2.foodname);
                    }else{
    
                        return o2.rating-o1.rating;
                    }
                }
            ));

use lambda Expression creation PriorityQueue The code of is also worth learning , The rule has only one line of definition ,(o1,o2)-> There is no need for brackets , And there is no semicolon at the end of the sorting statement ;

PriorityQueue<Integer> que=new PriorityQueue<>((o1,o2)->Math.abs(o1)-Math.abs(o2));

T4. 6127. The number of high-quality pairs

I'll give you a subscript from 0 Starting array of positive integers nums And a positive integer k .

If the following conditions are met , Then number pair (num1, num2) yes High quality pairs ：

num1 and num2 all In the array nums in . num1 OR num2 and num1 AND num2 The median value of the binary representation of is 1
The sum of digits of is greater than or equal to k , among OR It's bit by bit or operation , and AND It's bit by bit And operation . return Different The number of high-quality pairs .

If a != c perhaps b != d , Think (a, b) and (c, d) Are two different number pairs . for example ,(1, 2) and (2, 1)
Different .

Be careful ： If num1 At least... Appears in the array once , Then meet num1 == num2 The number of (num1, num2) It can also be a high-quality number pair .

Example 1：

Input ：nums = [1,2,3,1], k = 3 Output ：5 explain ： There are several high-quality pairs as follows ：

• (3, 3)：(3 AND 3) and (3 OR 3) The binary representation of is equal to (11) . The value is 1 The sum of digits of is equal to 2 + 2 = 4 , Greater than or equal to k = 3 .
• (2, 3) and (3, 2)： (2 AND 3) The binary representation of is equal to (10) ,(2 OR 3) The binary representation of is equal to (11) . The value is 1 The sum of digits of is equal to 1 + 2 = 3 .
• (1, 3) and (3, 1)： (1 AND 3) The binary representation of is equal to (01) ,(1 OR 3) The binary representation of is equal to (11) . The value is 1 The sum of digits of is equal to 1 + 2 = 3 . So the number of high-quality pairs is 5 .

Example 2：

Input ：nums = [5,1,1], k = 10 Output ：0 explain ： There are no good number pairs in this array .

Tips ：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 60

The reference solution of this problem Solution to the problem of spirit and God . To realize A or B + A and B yes A、B Binary of two numbers 1 The sum of is the key , Therefore, we can make statistics separately nums All digits in binary 1 The number of , Before Statistics , It is observed that number pairs can exchange orders , So consider weight removal . In a traverse nums In the process of , use HashMap<Integer,Integer> cnt Record ,key by nums[i] Binary system 1 The number of , No more than 30 individual ,Value Different records nums[i] The number of . Loop through twice cnt, According to the sum of digits >=k, Finally, accumulate the number of high-quality pairs .

//time:O(N)
class Solution {
    
    public long countExcellentPairs(int[] nums, int k) {
    
        long ans=0L;
        HashSet<Integer> vis=new HashSet<>();
        HashMap<Integer,Integer> cnt=new HashMap<>();
        for(int i:nums){
    
            // In the process of weight removal, statistics in binary 1 Number of digits 
            if(!vis.contains(i)){
    
                vis.add(i);
                int bitnum=Integer.bitCount(i);
                /**getOrDefault The positions cannot be interchanged at will  */
                cnt.put(bitnum,cnt.getOrDefault(bitnum,0)+1);
            }
        }

        for(Map.Entry<Integer,Integer> i:cnt.entrySet()){
    
            for(Map.Entry<Integer,Integer> j:cnt.entrySet()){
    
                if(i.getKey()+j.getKey()>=k){
    
                    ans+=(long)i.getValue()*j.getValue();
                }
            }
        }
        return ans;
    }   
}