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

5993. 将找到的值乘以 2
5981. 分组得分最高的所有下标
5994. 查找给定哈希值的子串
5995. 字符串分组

t3发现是倒着来的后改了，但没完全改，导致wrong了一发
t4自己压根没想清楚
"ab", "cd", "abc", "bcd"应该是在一个连通块中，但是按照我的处理方法，不可能将"ab", "cd"和在一起。。
别畏惧数据规模，不超1e8就大胆尝试！！！

5993. 将找到的值乘以 2

给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。
接下来，你需要按下述步骤操作：

如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。
否则，停止这一过程。
只要能在数组中找到新 original ，就对新 original 继续重复这一过程。

返回_ _original 的最终值。

示例 1：
输入：nums = [5,3,6,1,12], original = 3 输出：24 解释： - 3 能在 nums 中找到。3 2 = 6 。 - 6 能在 nums 中找到。6 2 = 12 。 - 12 能在 nums 中找到。12 2 = 24 。 - 24 不能在 nums 中找到。因此，返回 24 。
示例 2：
输入：nums = [2,7,9], original = 4 输出：4 *解释： - 4 不能在 nums 中找到。因此，返回 4 。

提示：

1 <= nums.length <= 1000
1 <= nums[i], original <= 1000

思路：
用哈希表即可
时间复杂度O(n)

class Solution {
    public int findFinalValue(int[] nums, int o) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums)
            set.add(x);
        while (set.contains(o))
            o *= 2;
        return o;
    }
}

5981. 分组得分最高的所有下标

给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。

numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
如果 i == 0 ，numsleft 为空，而 numsright 将包含 nums 中的所有元素。
如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为空。

下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之和。
返回 分组得分最高 的 所有不同下标 。你可以按 任意顺序 返回答案。

示例 1：
输入：nums = [0,0,1,0] 输出：[2,4] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。 - 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。下标 2 和 4 都可以得到最高的分组得分 3 。注意，答案 [4,2] 也被视为正确答案。
示例 2：
输入：nums = [0,0,0] 输出：[3] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。只有下标 3 可以得到最高的分组得分 3 。
示例 3：
输入：nums = [1,1] 输出：[0] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。 - 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。 - 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。只有下标 0 可以得到最高的分组得分 2 。

提示：

n == nums.length
1 <= n <= 105
nums[i] 为 0 或 1

思路：
前缀和
就是边界处理好恶心啊，还不如左右都多开点，更好处理！

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            pre[i] += pre[i - 1] + nums[i - 1];
        }
        pre[n + 1] = pre[n];
        List<Integer> res = new ArrayList<>();
        int max = 0;
        for (int i = 1; i <= n + 1; i++) {
            int l = i - pre[i - 1], r = pre[n] - pre[i - 1]; 
            int sum = l + r;
            if (sum == max) {
                res.add(i - 1);
            } else if (sum > max) {
                res.clear();
                max = sum;
                res.add(i - 1);
            }
        }
        return res;
    }
}

5994. 查找给定哈希值的子串

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：

hash(s, p, m) = (val(s[0]) p0 + val(s[1]) p1 + … + val(s[k-1]) * pk-1) mod m.

其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val(‘a’) = 1 到 val(‘z’) = 26 。
给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的子串 sub ，满足_ _hash(sub, power, modulo) == hashValue 。
测试数据保证一定存在至少一个这样的子串。
子串定义为一个字符串中连续非空字符组成的序列。

示例 1：
输入：s = “leetcode”, power = 7, modulo = 20, k = 2, hashValue = 0 输出：“ee” 解释：“ee” 的哈希值为 hash(“ee”, 7, 20) = (5 1 + 5 7) mod 20 = 40 mod 20 = 0 。 “ee” 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 “ee” 。
示例 2：
输入：s = “fbxzaad”, power = 31, modulo = 100, k = 3, hashValue = 32 输出：“fbx” 解释：“fbx” 的哈希值为 hash(“fbx”, 31, 100) = (6 1 + 2 31 + 24 312) mod 100 = 23132 mod 100 = 32 。 “bxz” 的哈希值为 hash(“bxz”, 31, 100) = (2 1 + 24 31 + 26 312) mod 100 = 25732 mod 100 = 32 。 “fbx” 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 “fbx” 。注意，”bxz” 的哈希值也为 32 ，但是它在字符串中比 “fbx” 更晚出现。

提示：

1 <= k <= s.length <= 2 * 104
1 <= power, modulo <= 109
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定存在满足条件的子串。

思路：
注意读题，本题的字符串哈希是从后往前的

class Solution {
    public String subStrHash(String s, int p, int m, int k, int hashValue) {
        int n = s.length();
        long pow = 1;
        for (int i = 1; i <= k; i++)
            pow = (pow * p) % m;
        long[] pre = new long[n + 2];
        for (int i = n - 1; i >= 0; i--) {
            pre[i] = (pre[i + 1] * p + s.charAt(i) - 'a' + 1) % m;
        }
        for (int i = 0; i <= n - k; i++) {
            long hash = ((pre[i] - pre[i + k] * pow) % m + m) % m;
            if (hash == hashValue)
                return s.substring(i, i + k);
        }
        return null;
    }
}

5995. 字符串分组

给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。
如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：

往 s1 的字母集合中添加一个字母。
从 s1 的字母集合中删去一个字母。
将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

数组 words 可以分为一个或者多个无交集的组。一个字符串与一个组如果满足以下任一条件，它就属于这个组：

它与组内至少一个其他字符串关联。
它是这个组中唯一的字符串。

注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2 的数组 ans ：

ans[0] 是 words 分组后的 总组数 。
ans[1] 是字符串数目最多的组所包含的字符串数目。

示例 1：
输入：words = [“a”,”b”,”ab”,”cde”] 输出：[2,3] 解释： - words[0] 可以得到 words[1] （将 ‘a’ 替换为 ‘b’）和 words[2] （添加 ‘b’）。所以 words[0] 与 words[1] 和 words[2] 关联。 - words[1] 可以得到 words[0] （将 ‘b’ 替换为 ‘a’）和 words[2] （添加 ‘a’）。所以 words[1] 与 words[0] 和 words[2] 关联。 - words[2] 可以得到 words[0] （删去 ‘b’）和 words[1] （删去 ‘a’）。所以 words[2] 与 words[0] 和 words[1] 关联。 - words[3] 与 words 中其他字符串都不关联。所以，words 可以分成 2 个组 [“a”,”b”,”ab”] 和 [“cde”] 。最大的组大小为 3 。
示例 2：
输入：words = [“a”,”ab”,”abc”] 输出：[1,3] 解释： - words[0] 与 words[1] 关联。 - words[1] 与 words[0] 和 words[2] 关联。 - words[2] 与 words[1] 关联。由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。所以最大的组大小为 3 。

提示：

1 <= words.length <= 2 * 104
1 <= words[i].length <= 26
words[i] 只包含小写英文字母。
words[i] 中每个字母最多只出现一次。

思路：
并查集 + 位运算
时间复杂度：O(26 26 N)
空间复杂度：O(N)

class Solution {
    public int[] groupStrings(String[] words) {
        int n = words.length;
        int[] a = new int[n];
        var uf = new UnionFind();
        for (int i = 0; i < n; i++) {
            int x = 0;
            for (int j = 0; j < words[i].length(); j++) {
                x |= 1 << (words[i].charAt(j) - 'a');
            }
            a[i] = x;
        }
        for (int x : a) {
            if (uf.add(x)) {
                for (int i = 0; i < 26; i++) {
                    if ((x >> i & 1) == 1) {
                        int v = x ^ (1 << i);
                        for (int j = 0; j < 26; j++) {
                            if (i != j && (v >> j & 1) == 0)
                                uf.merge(x, v ^ (1 << j));
                        }
                    }
                }
                for (int i = 0; i < 26; i++)
                    uf.merge(x, x ^ (1 << i));
            }
        }
        int max = 0, cnt = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : a) {
            map.merge(uf.find(x), 1, Integer::sum);
            max = Math.max(max, map.get(uf.find(x)));
        }
        return new int[]{map.size(), max};
    }
}
class UnionFind {
    Map<Integer, Integer> fa = new HashMap<>();
    boolean add(int x) {
        if (fa.get(x) == null) {
            fa.put(x, x);
            return true;
        } else
            return false;
    }
    void merge(int a, int b) {
        if (fa.get(a) == null || fa.get(b) == null)
            return;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            fa.put(pa, pb);
        }
    }
    int find(int x) {
        if (fa.get(x) == x)
            return x;
        else {
            int p = find(fa.get(x));
            fa.put(x, p);
            return p;
        }
    }
}