周赛 - 🏆 第 303 场力扣周赛 - 《学习笔记》

6124. 第一个出现两次的字母
6125. 相等行列对
6126. 设计食物评分系统
6127. 优质数对的数目

掉大分的一场。

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 包含至少一个重复字母

思路：
模拟

class Solution {
    public char repeatedCharacter(String s) {
        int[] c = new int[26];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - 'a']++;
            if (c[s.charAt(i) - 'a'] > 1) return s.charAt(i);
        }
        return ' ';
    }
}

class Solution {
    public char repeatedCharacter(String s) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (!set.add(s.charAt(i)))
                return s.charAt(i);
        }
        return ' ';
    }
}

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

思路：
n的范围很小，直接暴力处理
时间复杂度：O(n3)

class Solution {
    public int equalPairs(int[][] g) {
        int n = g.length;
        int c = 0;
        // row
        for (int i = 0; i < n; i++) {
            // col
            for (int j = 0; j < n; j++) {
                boolean f = true;
                for (int k = 0; k < n; k++) {
                    if (g[i][k] != g[k][j]) {
                        f = false;
                        break;
                    }
                }
                if (f) c++;
            }
        }
        return c;
    }
}

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 次

思路：
方法1：Map + TreeMap + TreeSet
究极套娃

class FoodRatings {
    class Node {
        String c;
        int v;
        Node(String c, int v) {
            this.c = c;
            this.v = v;
        }
    }
    // 食物-{做法，分数}
    Map<String, Node> map = new HashMap<>();
    // 做法-(分数-食物集和)
    Map<String, TreeMap<Integer, TreeSet<String>>> m2 = new HashMap<>();
    public FoodRatings(String[] f, String[] c, int[] r) {
        for (int i = 0; i < f.length; i++) {
            map.put(f[i], new Node(c[i], r[i]));
            if (!m2.containsKey(c[i]))
                m2.put(c[i], new TreeMap<>());
            TreeMap<Integer, TreeSet<String>> t = m2.get(c[i]);
            if (!t.containsKey(r[i]))
                t.put(r[i], new TreeSet<>());
            t.get(r[i]).add(f[i]);
        }
    }
    public void changeRating(String food, int newRating) {
        if (!map.containsKey(food)) return;
        Node old = map.get(food);
        m2.get(old.c).get(old.v).remove(food);
        if (m2.get(old.c).get(old.v).size() == 0)
            m2.get(old.c).remove(old.v);
        if (!m2.get(old.c).containsKey(newRating))
            m2.get(old.c).put(newRating, new TreeSet<>());
        m2.get(old.c).get(newRating).add(food);
        old.v = newRating;
    }
    public String highestRated(String c) {
        Integer x = m2.get(c).lastKey();
        return m2.get(c).get(x).first();
    }
}
/**
 * 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);
 */

// 利用Java 9新特性 Map.entry() 生成 Map.Entry<key, value>
class FoodRatings {
    // 食物-{做法，分数}
    Map<String, Map.Entry<String, Integer>> map = new HashMap<>();
    // 做法-食物集
    Map<String, TreeSet<String>> m2 = new HashMap<>();
    public FoodRatings(String[] f, String[] c, int[] r) {
        for (int i = 0; i < f.length; i++) {
            map.put(f[i], Map.entry(c[i], r[i]));
            m2.computeIfAbsent(c[i], key -> new TreeSet<>((o1, o2) -> {
                return map.get(o1).getValue().equals(map.get(o2).getValue()) ? o1.compareTo(o2)
                    : map.get(o2).getValue() - map.get(o1).getValue();
            })).add(f[i]);
        }
    }
    public void changeRating(String food, int newRating) {
        String c = map.get(food).getKey();
        m2.get(c).remove(food);
        map.put(food, Map.entry(c, newRating));
        m2.get(c).add(food);
    }
    public String highestRated(String cuisine) {
        return m2.get(cuisine).first();
    }
}
/**
 * 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);
 */

方法2：Map + 优先队列

class FoodRatings {
    class Food {
        String f, s;
        int v;
        Food(String f, String s, int v) {
            this.f = f;
            this.s = s;
            this.v = v;
        }
    }
    Map<String, Map.Entry<String, Integer>> map = new HashMap<>();
    Map<String, PriorityQueue<Food>> m2 = new HashMap<>();
    public FoodRatings(String[] f, String[] c, int[] r) {
        for (int i = 0; i < f.length; i++) {
            map.put(f[i], Map.entry(c[i], r[i]));
        }
        for (int i = 0; i < f.length; i++) {
            m2.computeIfAbsent(c[i], key -> new PriorityQueue<>((o1, o2) -> {
                return o1.v == o2.v ? o1.f.compareTo(o2.f) : o2.v - o1.v;
            })).add(new Food(f[i], c[i], r[i]));
        }
    }
    public void changeRating(String food, int newRating) {
        String c = map.get(food).getKey();
        map.put(food, Map.entry(c, newRating));
        m2.get(c).add(new Food(food, c, newRating));
    }
    public String highestRated(String cuisine) {
        var t = m2.get(cuisine);
        while (!t.isEmpty()) {
            var a = t.peek();
            if (map.get(a.f).getValue() != a.v) {
                t.poll();
                continue;
            } else {
                return a.f;
            }
        }
        return null;
    }
}
/**
 * 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

思路：
方法1：统计+ 二分

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        long c = 0;
        int[][] a = new int[set.size()][2];
        int idx = 0;
        for (int x : set) {
            a[idx][0] = x;
            a[idx][1] = Integer.bitCount(x); 
            int len = a[idx++][1];
            if (len * 2 >= k)
                c++;
        }
        Arrays.sort(a, (o1, o2) -> (o1[1] - o2[1]));
        for (int i = 0; i < a.length; i++) {
            if (a[i][1] >= k) {
                c += (a.length - i - 1) * 2L;
                continue;
            }
            int l = i + 1, r = a.length - 1, target = k - a[i][1];
            if (a[a.length - 1][1] < target) continue;
            while (l < r) {
                int mid = l + r >> 1;
                if (a[mid][1] >= target)
                    r = mid;
                else
                    l = mid + 1;
            }
            c += (a.length - l) * 2L;
        }
        return c;
    }
}

方法2 按位数统计不同的数的个数，总共只有30种不同的位数，二分换成暴力搜索

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        long res = 0;
        int[] c = new int[31];
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            c[Integer.bitCount(x)] += set.add(x) ? 1 : 0;
        }
        for (int i = 0; i < 31; i++) {
            for (int j = Math.max(0, k - i); j < 31; j++) {
                res += 1L * c[i] * c[j];
            }
        }
        return res;
    }
}