First Letter to Appear Twice3

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Note:

• A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
• s will contain at least one letter that appears twice.

Example 1:

Input: s = "abccbaacz"
Output: "c"
Explanation:
The letter 'a' appears on the indexes 0, 5 and 6.
The letter 'b' appears on the indexes 1 and 4.
The letter 'c' appears on the indexes 2, 3 and 7.
The letter 'z' appears on the index 8.
The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.

Example 2:

Input: s = "abcdd"
Output: "d"
Explanation:
The only letter that appears twice is 'd' so we return 'd'.

没啥可说的，读完题就会了

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

Equal Row and Column Pairs4

Given a 0-indexed n x n integer matrix grid, return the number of pairs (Ri, Cj) such that row Ri and column Cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e. an equal array).

Example 1:

Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]

分别把行列出现的记录次数，然后哈希表乘积求和

class Solution {
public:
    int equalPairs(vector<vector<int>> &grid) {
        map<string, int> h;
        map<string, int> l;
        for (int i = 0; i < grid.size(); i++) {
            string s, t;
            for (int j = 0; j < grid.size(); j++) {
                s += grid[i][j] + '0';
                t += grid[j][i] + '0';
            }
            h[s]++;
            l[t]++;
        }
        int ans = 0;
        for (auto&[s, n]: h) {
            ans += n * l[s];
        }
        return ans;
    }
};

Design a Food Rating System

Design a food rating system that can do the following:

• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.

Implement the FoodRatings class: Initializes the system. The food items are described by , and , all of which have a length of .

• • foods[i] is the name of the ith food,
  • cuisines[i] is the type of cuisine of the ith food, and
  • ratings[i] is the initial rating of the ith food.
• void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
• String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

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"]

Explanation
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" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
                                      // "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // Both "sushi" and "ramen" have a rating of 16.
                                      // However, "ramen" is lexicographically smaller than "sushi".

跟刚才做的T3基本一样？我是sb

class FoodRatings {
public:
    map<string, pair<int, string>> m;
    map<string, map<int, set<string>>> as;

    FoodRatings(vector<string> &foods, vector<string> &cuisines, vector<int> &ratings) {
        int n = foods.size();
        for (int i = 0; i < n; i++) {
            m[foods[i]] = {ratings[i], cuisines[i]};
            as[cuisines[i]][ratings[i]].insert(foods[i]);
        }
    }

    void changeRating(string food, int newRating) {
        int oR = m[food].first;
        string type = m[food].second;
        as[type][oR].erase(food);
        if (as[type][oR].size() == 0) {
            as[type].erase(oR);
        }
        as[type][newRating].insert(food);
        m[food].first = newRating;
    }

    string highestRated(string cuisine) {
        auto end = as[cuisine].end();
        end--;
        return *end->second.begin();

    }
};

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

Number of Excellent Pairs

You are given a 0-indexed positive integer array nums and a positive integer k.

A pair of numbers (num1, num2) is called excellent if the following conditions are satisfied:

• Both the numbers num1 and num2 exist in the array nums.
• The sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k, where OR is the bitwise OR operation and AND is the bitwise AND operation.

Return the number of distinct excellent pairs.

Two pairs (a, b) and (c, d) are considered distinct if either a != c or b != d. For example, (1, 2) and (2, 1) are distinct.

Note that a pair (num1, num2) such that num1 == num2 can also be excellent if you have at least one occurrence of num1 in the array.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: 5
Explanation: The excellent pairs are the following:
- (3, 3). (3 AND 3) and (3 OR 3) are both equal to (11) in binary. The total number of set bits is 2 + 2 = 4, which is greater than or equal to k = 3.
- (2, 3) and (3, 2). (2 AND 3) is equal to (10) in binary, and (2 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
- (1, 3) and (3, 1). (1 AND 3) is equal to (01) in binary, and (1 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
So the number of excellent pairs is 5.

就是要找两个数xor和and中1的个数大于等于k的数对个数。

a^b+a|b==a+b

对，就这个玩意，xor+and=or

class Solution {
public:
    long long countExcellentPairs(vector<int> &nums, int k) {
        map<int, int> m;
        map<int, bool> c;
        for (auto &n: nums) {
            if (c[n]) {
                continue;
            }
            m[__builtin_popcount(n)]++;
            c[n] = 1;
        }
        long long ans = 0;
        for (auto&[n, y]: m) {
            for (auto&[n1, y1]: m) {
                if (n + n1 >= k) {
                    ans += 1ll * y1 * y;
                }
            }
        }
        return ans;

    }
};