leetcode-weekly-contest-303

刷题

发布日期: 2022-07-24

Problem List

[1] 第一个出现两次的字母
[2] 相等行列对
[3] 设计食物评分系统
[4] 优质数对的数目

1 第一个出现两次的字母

1.1 题目描述

题目链接：6124. 第一个出现两次的字母

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现两次的字母。

注意：

如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
s 包含至少一个出现两次的字母。

示例1：

输入: s = “abccbaacz”
输出: “c”

示例2：

输入: s = “abcdd”
输出: “d”

1.2 思路

模拟，用哈希表计数，但下标对应哈希值为1直接返回即可。

class Solution {
public:
    char repeatedCharacter(string s) {
        int hash[26] = {0};
        for(char c: s) {
            ++hash[c-'a'];
            if(hash[c-'a'] ==2) return c;
        }
        return '0';
    }
};

2 相等行列对

2.1 题目描述

题目链接：6125. 相等行列对

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。

如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

示例1：

输入: grid = [[3,2,1],[1,7,6],[2,7,7]]
输出: 1
解释: 存在一对相等行列对：

(第 2 行，第 1 列)：[2,7,7]

示例2：

输入: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
输出: 3
解释: 存在三对相等行列对：

(第 0 行，第 0 列)：[3,1,2,2]

(第 2 行, 第 2 列)：[2,4,2,2]

(第 3 行, 第 2 列)：[2,4,2,2]

2.2 思路

直接模拟即可。

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size(), res = 0, k;
        for(int i = 0; i < n; ++i) 
            for(int j = 0; j < n; ++j)  
                for(k = 0; k < n; ++k) 
                    if(grid[i][k] != grid[k][j])
                            break;
                if(k == n)  ++res;
        return res;
    }
};

3 设计食物评分系统

3.1 题目描述

题目链接：2275. 按位与结果大于零的最长组合

设计一个支持下述操作的食物评分系统：

修改系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。
实现 FoodRatings 类：

FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。
- foods[i] 是第 i 种食物的名字。
- cuisines[i] 是第 i 种食物的烹饪方式。
- ratings[i] 是第 i 种食物的最初评分。
void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。
String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。

注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。

示例1：

输入: [“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”]]
输出: [null, “kimchi”, “ramen”, null, “sushi”, null, “ramen”]
解释:
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”); // 返回 “kimchi”
// “kimchi” 是分数最高的韩式料理，评分为 9 。
foodRatings.highestRated(“japanese”); // 返回 “ramen”
// “ramen” 是分数最高的日式料理，评分为 14 。
foodRatings.changeRating(“sushi”, 16); // “sushi” 现在评分变更为 16 。
foodRatings.highestRated(“japanese”); // 返回 “sushi”
// “sushi” 是分数最高的日式料理，评分为 16 。
foodRatings.changeRating(“ramen”, 16); // “ramen” 现在评分变更为 16 。
foodRatings.highestRated(“japanese”); // 返回 “ramen”
// “sushi” 和 “ramen” 的评分都是 16 。
// 但是，”ramen” 的字典序比 “sushi” 更小。

3.2 思路

4 优质数对的数目

4.1 题目描述

题目链接：6127. 优质数对的数目

给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。

如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：

num1 和 num2 都在数组 nums 中存在。
num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位或操作，而 AND 是按位与操作。
返回不同优质数对的数目。

如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2)和 (2, 1) 不同。

注意：如果 num1 在数组中至少出现一次，则满足 num1 == num2 的数对 (num1, num2) 也可以是优质数对。

示例1：

输入: nums = [1,2,3,1], k = 3
输出: 5
解释: 有如下几个优质数对：

(3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。

(2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。

(1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
所以优质数对的数目是 5 。

示例2：

输入: nums = [5,1,1], k = 10
输出: 0

4.2 思路

计算每一个数组的二进制表示中1的数量，然后用哈希表进行统计。注意, 这里需要进行去重，所以排序然后遍历，当当前遍历的数字与前一个一样，那么就跳过。然后从0开始遍历1的位数，由于int为占4个字节，所以要从0遍历到32. 而或和与的加和，实际上就是两个数的1的位数相加，所以两个for循环即可，当1的位数和大于等于k，那么1的位数为i和为j的数就可以组成优质数对，因此两个的个数相乘加到答案中。

class Solution {
    int get(int a) {
        int ans = 0;
        while(a) {
            if(a%2) ++ans;
            a /= 2;
        }
        return ans;
    }
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int hash[33]= {0};
        for(int i = 0; i < nums.size(); ++i) {
            if(i && nums[i]==nums[i-1]) continue;
            ++hash[get(nums[i])];
        }
        long long ans = 0;
        for(int i = 0; i < 33; ++i) 
            for(int j = 0; j < 33; ++j)
                if(i+j>=k)
                    ans += 1ll*hash[i]*hash[j];
        return ans;
    }
};