leetcode biweekly contest 90

leetcode biweekly contest 90

前三题都是水题，第四题想了半天没想出来简单的办法，直接单调栈加上线段树二分暴力，也没有想到更好的办法，除了菜没办法。

6225. 差值数组不同的字符串

题目

给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。

每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i]，其中对于 0 <= j <= n - 2有 difference[i][j] = words[i][j+1] - words[i][j] 。注意两个字母的差值定义为它们在字母表中 位置 之差，也就是说 'a' 的位置是 0，'b' 的位置是 1 ，'z' 的位置是 25 。

比方说，字符串 "acb" 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1]。
words 中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。

请你返回 words中 差值整数数组 不同的字符串。

示例 1：

1
2
3
4
5
6
7
输入：words = ["adc","wzy","abc"]
输出："abc"
解释：
- "adc" 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。
- "wzy" 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。
- "abc" 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。
不同的数组是 [1, 1]，所以返回对应的字符串，"abc"。

示例 2：
1
2
3
输入：words = ["aaa","bob","ccc","ddd"]
输出："bob"
解释：除了 "bob" 的差值整数数组是 [13, -13] 以外，其他字符串的差值整数数组都是 [0, 0] 。

提示：

  • 3 <= words.length <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i] 只含有小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-90/problems/odd-string-difference/

题意

直接模拟

思路

  1. 直接模拟了，没啥好说的，暴力循环然后找到出现次数最少的即可
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        string oddString(vector<string>& words) {
            map<vector<int>, int> cnt;
            vector<vector<int>> arr;
            for (int i = 0; i < words.size(); i++) {
                vector<int> curr;
                for (int j = 1; j < words[i].size(); j++) {
                    curr.emplace_back(words[i][j] - words[i][j-1]);
                }
                cnt[curr]++;
                arr.emplace_back(curr);
            }
            for (int i = 0; i < arr.size(); i++) {
                if (cnt[arr[i]] == 1) {
                    return words[i];
                }
            }
            return "";
        }
    };

6228. 距离字典两次编辑以内的单词

题目

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

示例 1：

1
2
3
4
5
6
7
8
输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。

示例 2：
1
2
3
4
5
输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：
"yes" 需要超过 2 次编辑才能得到 "not" 。
所以我们返回空数组。

提示：

  • 1 <= queries.length, dictionary.length <= 100
  • n == queries[i].length == dictionary[j].length
  • 1 <= n <= 100
  • 所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-90/problems/words-within-two-edits-of-dictionary/

题意

遍历

思路

  1. 这个题目也是暴力循环即可，直接计算两个字符串的编辑距离即可，非常简单的题目了。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(nm)$，其中 $n$ 表示给定的数组的长度,$m$ 表示字符串的长度。
  • 空间复杂度：空间复杂度为 $O(1)$。

    代码

    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
    class Solution {
    public:
        int diff(string &a, string &b) {
            int res = 0;
            for(int i = 0; i < a.size(); i++) {
                if(a[i] != b[i]) {
                    res++;
                }
            }    
            return res;
        }
        
        vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
            vector<string> ans;
            for (auto &a : queries) {
                for (auto &b : dictionary) {
                    if (diff(a, b) <= 2) {
                        ans.emplace_back(a);
                        break;
                    }
                }
            }
            return ans;
        }
    };

6226. 摧毁一系列目标

题目

给你一个下标从 0 开始的数组 nums ，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数 space 。

你有一台机器可以摧毁目标。给机器 输入 nums[i] ，这台机器会摧毁所有位置在 nums[i] + c * space 的目标，其中 c 是任意非负整数。你想摧毁 nums 中 尽可能多 的目标。

请你返回在摧毁数目最多的前提下，nums[i] 的 最小值 。

示例 1：

1
2
3
4
5
输入：nums = [3,7,8,1,1,5], space = 2
输出：1
解释：如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。
这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。
没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。

示例 2：
1
2
3
4
5
输入：nums = [1,3,5,2,4,6], space = 2
输出：1
解释：输入 nums[0] 或者 nums[3] 都会摧毁 3 个目标。
没有办法摧毁多于 3 个目标。
由于 nums[0] 是最小的可以摧毁 3 个目标的整数，所以我们返回 1 。

示例 3：
1
2
3
输入：nums = [6,2,5], space = 100
输出：2
解释：无论我们输入哪个数字，都只能摧毁 1 个目标。输入的最小整数是 nums[1] 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= space <= 109

地址

https://leetcode.cn/contest/biweekly-contest-90/problems/destroy-sequential-targets/

题意

数学问题

思路

  1. 通过分析可以知道如果 $x$ 与 $y$ 按照题目要求可以变换，则一定满足 $x \mod space = y \mod space$。此时我们对于每个 $nums[i]$ 只需要统计出 $nums[i] \mod space$ 的个数即可。
  2. 最后我们按照题目要做只需要找到 $nums[i] \mod space$ 的最大数目，且满足 $nums[i]$ 最小即可。
  3. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 为数组的长度。
  • 空间复杂度：时间复杂度为 $O(n)$。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int destroyTargets(vector<int>& nums, int space) {
            int n = nums.size();
            unordered_map<int, int> cnt;
            for (int i = 0; i < n; i++) {
                cnt[nums[i] % space]++;
            }
            int ans = 0, freq = 0;
            for (int i = 0; i < n; i++) {
                int x = nums[i] % space;
                if (cnt[x] > freq || (cnt[x] == freq && nums[i] < ans)) {
                    ans = nums[i];
                    freq = cnt[x];
                }
            }
            return ans;
        }
    };

6227. 下一个更大元素 IV

题目

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

  • j > i
  • nums[j] > nums[i]
    恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。
    如果不存在 nums[j] ，那么第二大整数为 -1 。

比方说，数组 [1, 2, 4, 3]中，1 的第二大整数是 4，2 的第二大整数是 3 ，3 和 4的第二大整数是 -1 。
请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。

示例 1：

1
2
3
4
5
6
7
8
9
输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：
1
2
3
4
输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-90/problems/next-greater-element-iv/

题意

数学问题

思路

  1. 我们将本题拆分成两个子问题：
  • 下一个更大的元素；
  • 从 $i$ 开始找到第一个比 $x$ 大的数；
    如果上面两个子问题都可以解决，那么本题就是一个常规题目了。
  1. 首先我们找到每个元素 $nums[i]$ 下一个更大元素的位置为 $j$，然后从 $j + 1$ 处开始查找第一个比 $nums[i]$ 大的元素，此时我们可以利用线段树上二分查找。
  2. 排序也非常简单的问题，排序也是非常好的思路来解决该问题，我们将所有的元素按照从大道小的顺序进行排序，同时对于相同的元素按照索引的小到大的顺序来进行排序，此时我们从大到小依次将元素的索引加入到有序集合中，保证每次加入 $nums[i]$ 时，集合中只保存大于 $nums[i]$ 的元素，每次我们查询有序集合中第一个大于 $i$ 的索引为 $j$ 即可，再往后移动一个元素即可。
  4. 复杂度分析：
  • 时间复杂度：$O(n \log 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
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
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> right(n, -1);
        vector<int> ans(n, -1);
        stack<int> st;
        st.emplace(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] <= nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                right[i] = st.top();
            }
            st.emplace(i);
        }
        this->tmax = vector<int>(n * 4 + 10);
        this->nums = nums;
        buildTree(0, n - 1, 1);
        for (int i = 0; i < n; i++) {
            if (right[i] != -1) {
                int x = queryRight(right[i] + 1, nums[i], 0, n - 1, 1);
                ans[i] = x;
            }
        }        
        return ans;
    }
    
    void buildTree(int l, int r, int idx) {
        if (l == r) {
            tmax[idx] = nums[l];
        } else {
            int mid = (l + r) >> 1;
            buildTree(l, mid, idx * 2);
            buildTree(mid + 1, r, idx * 2 + 1);
            tmax[idx] = max(tmax[idx * 2], tmax[idx * 2 + 1]);
        }
    }

    int queryRight(int start, int val, int l, int r, int idx) {
        if (r < start) {
            return -1;
        }
        if (tmax[idx] <= val) {
            return -1;
        }
        if (l == r) {
            return nums[l];
        } else {
            int mid = (l + r) >> 1;
            int ret = -1;
            if (tmax[idx * 2] > val) {
                ret = queryRight(start, val, l, mid, idx * 2);
            } 
            if (ret == -1) {
                ret = queryRight(start, val, mid + 1, r, idx * 2 + 1);
            }
            return ret;
        }
    } 
private:
    vector<int> tmax;
    vector<int> nums;
};
  • 排序 + 二分查找
    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
    class Solution {
    public:
        vector<int> secondGreaterElement(vector<int>& nums) {
            int n = nums.size();
            vector<pair<int, int>> arr;
            for (int i = 0; i < nums.size(); i++) {
                arr.emplace_back(nums[i], i);
            }
            sort(arr.begin(), arr.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
                if (a.first == b.first) {
                    return a.second < b.second;
                } 
                return a.first > b.first;
            });
            set<int> cnt;
            vector<int> ans(n, -1);
            for (auto [x, i] : arr) {
                auto it = cnt.lower_bound(i);
                if (it != cnt.end() && (++it) != cnt.end()) {
                    ans[i] = nums[*it];
                }
                cnt.emplace(i);
            }
            return ans;
        }
    };

#

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

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