leetcode biweekly contest 88

leetcode biweekly contest 88

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

6212. 删除字符使频率相同

题目

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

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

注意：

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

示例 1：

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

示例 2：

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

提示：

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

地址

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

题意

直接模拟

思路

  1. 太容易出错的题目，因为数量较少，不如直接模拟，对所有的字符种类进行统计，依次尝试减少某一个字符后，所有的数据是否可以相等。
  2. 复杂度分析：
  • 时间复杂度：$O(n + |\Sigma|)$，其中 $n$ 表示数组的长度，$|\Sigma|$ 表示字符集。
  • 空间复杂度：$O(C)$。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    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：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
["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/

题意

模拟

思路

  1. 我们用 $curr$ 指向当前已经上传完成的最大索引，并用哈希表记录当前所有已经上传的编号。
  • 每次再查询时，我们依次往后查询 $curr + 1, curr + 2, \cdots$ 是否连续的编号是否都已经上传即可。
  1. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示已经上传的次数。
  • 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示已经上传的次数。

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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：

1
2
3
4
5
输入：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：
1
2
3
4
5
6
输入：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/

题意

数学问题

思路

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

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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：

1
2
3
4
5
6
7
8
输入：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：
1
2
3
4
输入：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/

题意

线段树或者树状数组

思路

  1. 这个题目实在是太模板题目了，不好怎么平均这个题目，知道线段树之类的模板，题目就非常简单。题目给定的不等式装换为 $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$ 即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n \log \max(nums))$，其中 $n$ 表示数组的元素，$\max(nums)$ 表示给定的数组的最大值。
  • 空间复杂度：$O(C)$，$C$ 表示给定的常数大小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
    }
};

#

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

力扣周赛
#力扣周赛
leetcode biweekly contest 88
http://example.com/2022/11/01/力扣周赛题解/40/
Author
Mike Meng
Posted on
November 2, 2022
Updated on
September 8, 2026
Licensed under