且听疯吟

leetcode conttest 303

2022-11-01

leetcode conttest 303

周赛这个难度，真心是质量下降太多了。

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

题目

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

注意：

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

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

提示：

  • 2 <= s.length <= 100
  • s 由小写英文字母组成
  • s 包含至少一个重复字母

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/best-poker-hand/

题意

直接遍历

思路

  1. 简单题目，直接尝试所有的可能即可
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
  • 空间复杂度：$O(\Sigma)$。

代码

class Solution {
public:
    char repeatedCharacter(string s) {
        vector<int> cnt(26);
        for (int i = 0; i < s.size(); i++) {
            cnt[s[i] - 'a']++;
            if (cnt[s[i] - 'a']> 1) {
                return s[i];
            }
        }
        return 'a';
    }
};

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]

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • 1 <= grid[i][j] <= 105

地址

https://leetcode.cn/contest/weekly-contest-303/problems/equal-row-and-column-pairs/

题意

直接遍历

思路

  1. 题目可以算是简单题目，直接遍历矩阵的每个元素 $(x,y)$，然后比较第 $x$ 行的元素与第 $j$ 列的元素是否相等。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n^3)$，$n$ 表示矩阵的行数。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                /* row i, col j */
                bool isValid = true;
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        isValid = false;
                        break;
                    }
                }
                if (isValid) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

6126. 设计食物评分系统

题目

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

修改 系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。
实现 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] 之前。

示例：

输入
["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" 更小。

提示：

  • 1 <= n <= 2 * 104
  • n == foods.length == cuisines.length == ratings.length
  • 1 <= foods[i].length, cuisines[i].length <= 10
  • foods[i]、cuisines[i] 由小写英文字母组成
  • 1 <= ratings[i] <= 108
  • foods 中的所有字符串 互不相同
  • 在对 changeRating 的所有调用中，food 是系统中食物的名字。
  • 在对 highestRated 的所有调用中，cuisine是系统中 至少一种 食物的烹饪方式。
  • 最多调用 changeRating 和 highestRated 总计 2 * 104 次

地址

https://leetcode.cn/contest/biweekly-contest-83/problems/design-a-number-container-system/

题意

hash

思路

  1. 简单的 hash，设两个 hash。 arr 中存放着食物名称对应的烹饪方式和评分，cnt 存储着食物烹饪方式对应着的食物和评分的排名。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$。
  • 空间复杂度：空间复杂度为 $O(n)$。

代码

struct cmp {  
    bool operator() (const pair<int,string> &s1, const pair<int,string> &s2) const{
        if (s1.first == s2.first) {
            return s1.second > s2.second;
        }
        return s1.first < s2.first;
    }
}; 

class FoodRatings {
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        int n = foods.size();
        for (int i = 0; i < n; i++) {
            arr[foods[i]] = make_pair(ratings[i], cuisines[i]);
            cnt[cuisines[i]].insert(make_pair(ratings[i], foods[i]));
        }
    }
    
    void changeRating(string food, int newRating) {
        auto [rate, cuisine] = arr[food];
        arr[food].first = newRating;
        cnt[cuisine].erase(make_pair(rate, food));
        cnt[cuisine].emplace(newRating, food);
    }
    
    string highestRated(string cuisine) {
        return cnt[cuisine].rbegin()->second;
    }
private:
    unordered_map<string, set<pair<int, string>, cmp>> cnt;
    unordered_map<string, pair<int, string>> arr;
};

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

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
解释：该数组中不存在优质数对。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 60

地址

https://leetcode.cn/contest/weekly-contest-303/problems/number-of-excellent-pairs/

题意

数学问题

思路

  1. 我们设 $bits(x)$ 表示 $x$ 的二进制位中含有 $1$ 的为数，此时我们数学推理可以知道 $bits(x|y) + bits(x \And y) = bits(x) + bits(y)$，知道以上推理后，则这个题目就转换成了求数组中的两个数之和大于等于给定值的不同数对有多少个，题目就变的非常简单了。
  2. 首先我们为了去重，首先把数组中的重复元素全部去掉，因为重复的元素对应的数对相同，然后将其中的元素 $x$ 全部转化为 $bits(x)$，然后再转化的数组中找到满足两个元素之和大于等于 $k$ 的数对有多少个。
  3. 复杂度分析：
  • 时间复杂度：$O(n \log n)$，$n$ 表示数组的长度。
  • 空间复杂度：$O(n)$，$n$ 表示数组的长度。

代码

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_set<int> cnt;
        for (int i = 0; i < n; i++) {
            cnt.emplace(nums[i]);
        }
        vector<int> arr;
        for (auto v : cnt) {
            arr.emplace_back(__builtin_popcount(v));
        }
        sort(arr.begin(), arr.end());
        long long ans = 0;
        int m = arr.size();
        for (int i = 0; i < m; i++) {
            int x = m - (lower_bound(arr.begin(), arr.end(), k - arr[i]) - arr.begin());
            ans += x;
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛
← leetcode conttest 304 leetcode biweekly conttest 83 →

扫描二维码，分享此文章