文章/答案/技术大牛

发布

社区首页 >专栏 >LeetCode周赛303，又见手速场……

LeetCode周赛303，又见手速场……

TechFlow-承志

发布于 2022-09-21 02:00:34

36400

代码可运行

文章被收录于专栏：TechFlowTechFlow

运行总次数：0

代码可运行

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

第303场的LeetCode周赛，由佳期投资赞助。前100名同学可以获得直通面试的机会。前10名还有机会获得飞盘等礼物。也算是紧扣热点了……

这一场总体来说难度也不大，和上一场一样比较简单，算是一个新人友好的手速场。评论区还有小伙伴记录自己的第一次周赛ak。老梁这次比赛前一晚没有睡好，虽然ak了，但排名不太好看，估计又要掉分了……

好了，回到正题，我们来看题吧。

第一个出现两次的字母

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

注意：

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

题解

很简单，我们只需要记录一下每个字母出现的次数，当遇到某个字母重复出现时即是答案。

class Solution {
public:
    char repeatedCharacter(string s) {
        set<char> st;
        for (auto c: s) {
            if (st.count(c)) return c;
            else st.insert(c);
        }
        return ' ';
    }
};

相等行列对

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

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

题解

数据范围很小，我们直接用

O(n^3)

的暴力枚举的法即可通过。

但我们还有其他办法可以搞定，我们可以设计一种hash算法，可以将每一行和列hash成一个整数值。如果某一行和某一列hash之后的值相等，说明它们对应的元素完全一样。

hash的方法比较简单，我们可以用利用质数幂不易碰撞的方式来计算，比如[1, 2, 3]映射成

1 * 7^2 + 2 * 7 + 3

。由于这个值可能很大，所以我们需要对另一个质数取模，这里我们可以用竞赛当中常用的模数

1e9+7

。

这样的话，我们可以在

O(n^2)

的时间之内将所有行和列完成hash。之后在对比每一个行列组合的hash值是否相等即可。这样的话，总体的复杂度为

O(n^2)

。

class Solution {
public:
    long long Mod = 1e9+7;
    long long row_hash(vector<vector<int>> &grid, int n, int r) {
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret = (ret + grid[r][i]) * 7 % Mod;
        }
        return ret;
    }
    
    long long col_hash(vector<vector<int>> &grid, int n, int c) {
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret = (ret + grid[i][c]) * 7 % Mod;
        }
        return ret;
    }
    
    int equalPairs(vector<vector<int>>& grid) {
        int ret = 0;
        int n = grid.size();
        vector<long long> rows, cols;
        
        for (int i = 0; i < n; i++) {
            auto rh = row_hash(grid, n, i);
            rows.push_back(rh);
            auto ch = col_hash(grid, n, i);
            cols.push_back(ch);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) 
                if (rows[i] == cols[j]) ret++;
        }
        return ret;
    }
};

设计食物评分系统

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

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

实现 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] 之前。

题解

这题题目有点长，读起来有点费劲，一定要有耐心好好读题，一旦错过一些关键信息会给之后的解题带来很大的麻烦，所以千万不能嫌麻烦跳读。

读完之后简单分析，会发现本题分为三个部分，分别是初始化、修改和查询。是一个非常经典的增改查的数据结构设计。

本题的难点在于每个菜的评分是会改变的，改变了之后会影响菜的排名。我们需要能高效地完成菜品分数的修改，又完成菜品排名的调整。我们先来分析一下本题涉及的结构，其实结构还是比较简单的，只有三块：菜系-菜品和评分。

我们要查询的是菜系下最高评分的菜品，我们可以使用一个map来存储所有菜系对应的菜品。这是一个一对多的映射关系，所以需要使用一个容器来存储菜品，最好能根据菜品的分数自动调整排序。这里可以使用优先队列，我们可以重定义优先队列的排序规则。但也可以有map嵌套来完成，map的key是分数，value是菜品名。由于可能会出现同分数对应多道菜的情况，所以我们又需要使用一个set来完成对菜品名的排序。

所以就是一个map<菜系, map<分数, set<菜品>>>的结构。我们在查询的时候，先找到对应的菜系的map，再找到最大键值对应的菜品set，再找到set当中的最小名称。好在map和set自带排序我们直接使用rbegin和begin这两个函数即可获得头尾元素。

代码如下：

class FoodRatings {
public:
    
    typedef pair<string, int> psi;
    map<string, string> food_cus;
    map<string, int> food_score;
    map<string, map<int, set<string>>> cus_score;
        
    FoodRatings(vector<string>& foods, vector<string>& cus, vector<int>& rat) {
        int n = foods.size();
        for (int i = 0; i < n; i++) {
            string name = foods[i];
            string c = cus[i];
            int score = rat[i];
            
            food_cus[name] = c;
            food_score[name] = score;
            if (!cus_score.count(c)) cus_score[c] = map<int, set<string>>();
            if (!cus_score[c].count(score)) cus_score[c][score] = set<string>();
            cus_score[c][score].insert(name);
        }
    }
    
    void changeRating(string food, int ns) {
        string c = food_cus[food];
        int score = food_score[food];
        cus_score[c][score].erase(food);
        if (cus_score[c][score].size() == 0) cus_score[c].erase(score);
        if (!cus_score[c].count(ns)) cus_score[c][ns] = set<string>();
        cus_score[c][ns].insert(food);
        food_score[food] = ns;
    }
    
    string highestRated(string c) {
        auto it = cus_score[c].rbegin();
        auto nit = it->second.begin();
        return *nit;
    }
};

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

优质数对的数目

给你一个下标从 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) 也可以是优质数对。

题解

这题表面上看很棘手，又是and操作又是or操作的。

但其实我们分析一下会简单很多，假设两个数x和y。x中有a个二进制1，y中有b个二进制1。x & y中有c个二进制1，x | y中有d个二进制1。我们根据and和or的计算规则可以发现a + b - c = d，即a + b = c + d。我们要求的是c + d，但现在我们只需要求a + b了，计算上简单了很多，解耦了两个数之间的影响。

把这个分析清楚之后，剩下的事情就简单很多了。首先对所有的数进行去重，去重之后算出每个数中二进制1的数量。假设某一个数二进制1的数量是x，可以和它组成优质数对的数它的二进制中1的个数就需要大于等于k-x。对于一个范围内求和的问题，我们可以使用前缀和来加速。

代码如下：

class Solution {
public:
    
    int cnt(long long x) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((1ll << i) & x) ret++;
        }
        return ret;
    }
        
    long long countExcellentPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int n = nums.size();
        
        vector<long long> bits(61, 0), sums(61, 0);
        map<int, long long> mp;
        
        for (int i = 0; i < n; i++) {
            long long x = cnt(nums[i]);
            mp[nums[i]] = x;
            bits[x]++;
        }
        
        // 前缀和
        for (int i = 1; i < 61; i++) {
            sums[i] = sums[i-1] + bits[i];
        }
        
        long long ret = 0;
        
        for (int i = 0; i < n; i++) {
            int x = mp[nums[i]];
            ret += sums[31] - sums[max(0, k-x-1)];
        }
        
        return ret;
    }
};