leetcode biweekly contest 88

只能说放水太严重的周赛题目了，最后一题就是线段树的模板题目。

6212. 删除字符使频率相同

题目

给你一个下标从 0 开始的字符串 word，字符串只包含小写英文字母。你需要选择一个下标并删除下标处的字符，使得 word 中剩余每个字母出现频率相同。

如果删除一个字母后，word 中剩余所有字母的出现频率都相同，那么返回 true ，否则返回 false 。

注意：

字母 x 的频率是这个字母在字符串中出现的次数。
你必须恰好删除一个字母，不能一个字母都不删除。

示例 1：

输入：word = "abcc"
输出：true
解释：选择下标 3 并删除该字母，word 变成 "abc" 且每个字母出现频率都为 1 。

示例 2：

输入：word = "aazz"
输出：false
解释：我们必须删除一个字母，所以要么 "a" 的频率变为 1 且 "z" 的频率为 2 ，要么两个字母频率反过来。所以不可能让剩余所有字母出现频率相同。

提示：

2 <= word.length <= 100
word 只包含小写英文字母。

地址

https://leetcode.cn/problems/remove-letter-to-equalize-frequency/

题意

直接模拟

思路

太容易出错的题目，因为数量较少，不如直接模拟，对所有的字符种类进行统计，依次尝试减少某一个字符后，所有的数据是否可以相等。
复杂度分析：

时间复杂度：$O(n + |\Sigma|)$，其中 $n$ 表示数组的长度，$|\Sigma|$ 表示字符集。
空间复杂度：$O(C)$。

代码

class Solution {
public:
    bool equalFrequency(string word) {
        vector<int> cnt(26);
        for (auto c : word) {
            cnt[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                cnt[i]--;
                int prev = 0;
                bool isEqual = true;
                for(int j = 0; j < 26; j++) {
                    if (cnt[j] > 0) {
                        if (prev == 0) {
                            prev = cnt[j];
                        } else if (prev != cnt[j]){
                            isEqual = false;
                            break;
                        }
                    }
                }
                cnt[i]++;
                if (isEqual) {
                    return true;
                }
            }
        }
        return false;
    }
};

6197. 最长上传前缀

题目

给你一个 n 个视频的上传序列，每个视频编号为 1 到 n 之间的不同数字，你需要依次将这些视频上传到服务器。请你实现一个数据结构，在上传的过程中计算最长上传前缀。

如果闭区间 1 到 i 之间的视频全部都已经被上传到服务器，那么我们称 i 是上传前缀。最长上传前缀指的是符合定义的 i 中的最大值。

请你实现 LUPrefix 类：

LUPrefix(int n) 初始化一个 n 个视频的流对象。
void upload(int video) 上传 video 到服务器。
int longest() 返回上述定义的最长上传前缀的长度。

示例 1：

输入：
["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]
[[4], [3], [], [1], [], [2], []]
输出：
[null, null, 0, null, 1, null, 3]

解释：
LUPrefix server = new LUPrefix(4);   // 初始化 4个视频的上传流
server.upload(3);                    // 上传视频 3 。
server.longest();                    // 由于视频 1 还没有被上传，最长上传前缀是 0 。
server.upload(1);                    // 上传视频 1 。
server.longest();                    // 前缀 [1] 是最长上传前缀，所以我们返回 1 。
server.upload(2);                    // 上传视频 2 。
server.longest();                    // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。

提示：

1 <= n <= 105
1 <= video <= 105
video 中所有值互不相同。
upload 和 longest 总调用次数至多不超过 2 * 105 次。
至少会调用 longest 一次。

地址

https://leetcode.cn/contest/cnunionpay2022/problems/6olJmJ/

题意

模拟

思路

我们用 $curr$ 指向当前已经上传完成的最大索引，并用哈希表记录当前所有已经上传的编号。

每次再查询时，我们依次往后查询 $curr + 1, curr + 2, \cdots$ 是否连续的编号是否都已经上传即可。

复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示已经上传的次数。
空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示已经上传的次数。

代码

class LUPrefix {
public:
    LUPrefix(int n) {
        flag = vector<int>(n + 1, false);
        flag[0] = true;
    }
    
    void upload(int video) {
        flag[video] = true;
        while(curr + 1 < flag.size() && flag[curr + 1]) {
            curr++;
        }
    }
    
    int longest() {
        return curr;
    }
private:
    int curr = 0;
    vector<int> flag;
};

6213. 所有数对的异或和

题目

给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含 nums1 和 nums2 中所有数对的异或和（nums1 中每个整数都跟 nums2 中每个整数恰好匹配一次）。

请你返回 nums3 中所有整数的异或和。

示例 1：

输入：nums1 = [2,1,3], nums2 = [10,2,5,0]
输出：13
解释：
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ，所以我们返回 13 。

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：0
解释：
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ，nums1[0] ^ nums2[1] ，nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以，一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。

提示：

1 <= nums1.length, nums2.length <= 105
0 <= nums1[i], nums2[j] <= 109

地址

https://leetcode.cn/problems/bitwise-xor-of-all-pairings/

题意

数学问题

思路

简单的数学模拟问题，我们设数组 $nums1,nums2$ 的长度分别为 $m,n$，根据题意可以知道最终异或的结果即为 $nums1$ 的每个元素要与 $nums2$ 中的每个元素异或，则可以知道 $nums1$ 中的每个元素在最终异或的等式中出现了 $n$ 次；$nums2$ 的每个元素要与 $nums1$ 中的每个元素异或，$nums2$ 中的每个元素在最终异或的等式中出现了 $m$ 次。
复杂度分析

时间复杂度：时间复杂度为 $O(n)$，$n$ 为数组的长度。
空间复杂度：时间复杂度为 $O(n)$，$n$ 为数组的长度。

代码

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int tot = 0;
        if (n & 1) {
            for (auto v : nums1) {
                tot ^= v;
            }
        }
        if (m & 1) {
            for (auto v : nums2) {
                tot ^= v;
            }
        }
        return tot;
    }
};

6198. 满足不等式的数对数目

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff ，统计满足以下条件的数对 (i, j) ：

0 <= i < j <= n - 1 且
nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.
请你返回满足条件的数对数目。

示例 1：

输入：nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
输出：3
解释：
总共有 3 个满足条件的数对：
1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。因为 i < j 且 1 <= 1 ，这个数对满足条件。
2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。因为 i < j 且 -2 <= 2 ，这个数对满足条件。
3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。因为 i < j 且 -3 <= 2 ，这个数对满足条件。
所以，我们返回 3 。

示例 2：

输入：nums1 = [3,-1], nums2 = [-2,2], diff = -1
输出：0
解释：
没有满足条件的任何数对，所以我们返回 0 。

提示：

n == nums1.length == nums2.length
2 <= n <= 105
-104 <= nums1[i], nums2[i] <= 104
-104 <= diff <= 104

地址

https://leetcode.cn/problems/number-of-pairs-satisfying-inequality/

题意

线段树或者树状数组

思路

这个题目实在是太模板题目了，不好怎么平均这个题目，知道线段树之类的模板，题目就非常简单。题目给定的不等式装换为 $nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff$，我们令 $c[i] = nums1[i] - nums2[i]$，也就装换为 $c[i] <= c[j] + diff, \quad (i < j)$，非常模板的题目了，我们每次遍历到 $c[j]$ 时，求处在区间 $[-\infty,c[i] - diff]$ 的元素的数目有多少个，由于题目存在负数，我们加上一个常数 $C$ 使得 $c[i] - diff + C \ge 0$，此时即转换为了求 $[0, c[i] - diff + C]$ 可以取 $C = 40000$ 即可。
复杂度分析：

时间复杂度：$O(n \log \max(nums))$，其中 $n$ 表示数组的元素，$\max(nums)$ 表示给定的数组的最大值。
空间复杂度：$O(C)$，$C$ 表示给定的常数大小。

代码

#define CHL(x) (x * 2)
#define CHR(x) (x * 2 + 1)
const int MAXN = 4e5 + 7;

struct SegTreeNode {
    int l, r;
    int sum;
};

SegTreeNode tree[MAXN];

void pushUpTree(int idx) {
    tree[idx].sum = tree[CHL(idx)].sum + tree[CHR(idx)].sum;
}

void buildTree(int idx, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == r) {
        tree[idx].l = tree[idx].r = l;
        tree[idx].sum = 0;
        return;
    }
    tree[idx].l = l;
    tree[idx].r = r;
    
    int mid = (l + r) / 2;
    buildTree(CHL(idx), l, mid);
    buildTree(CHR(idx), mid + 1, r);
    pushUpTree(idx);
}

void updateTree(int x, int val, int idx) {
    if (x < tree[idx].l || x > tree[idx].r) {
        return;
    }
    if (x == tree[idx].l && x == tree[idx].r) {
        tree[idx].sum += val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (x <= mid) {
        updateTree(x, val, CHL(idx));
    } else {
        updateTree(x, val, CHR(idx));
    }
    pushUpTree(idx);
}

int queryTree(int l, int r, int idx) {
    if (r < tree[idx].l || l > tree[idx].r) {
        return 0;
    }
    if (l <= tree[idx].l && r >= tree[idx].r) {
        return tree[idx].sum;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (r <= mid) {
        return queryTree(l, r, CHL(idx));
    } else if (l > mid) {
        return queryTree(l, r, CHR(idx));
    } else {
        return queryTree(l, mid, CHL(idx)) + queryTree(mid + 1, r, CHR(idx));
    }
}

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
        int n = nums1.size();
        buildTree(1, 0, 80000);
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            int x = nums1[i] - nums2[i] + 40000;
            int y = diff;
            ans += queryTree(0, x + y, 1);
            updateTree(x, 1, 1);
        }
        return ans;
    }
};

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

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode contest 312 天堂硅谷·数字经济算法编程大赛 →

扫描二维码，分享此文章