leetcode weekly contes 354

leetcode weekly contes 354

本周的题目质量还可以，都不算太难，但是有不少值得深思的地方，需要仔细去思考，很多有可以优化的解法或者可以将其进行扩展的解法。

2778. 特殊元素平方和

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个 特殊元素 。

返回 nums 中所有 特殊元素 的 平方和 。

示例 1：

输入：nums = [1,2,3,4]
输出：21
解释：nums 中共有 3 个特殊元素：nums[1] ，因为 4 被 1 整除；nums[2] ，因为 4 被 2 整除；以及 nums[4] ，因为 4 被 4 整除。 
因此，nums 中所有元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21 。  

示例 2：

输入：nums = [2,7,1,19,18,3]
输出：63
解释：nums 中共有 4 个特殊元素：nums[1] ，因为 6 被 1 整除；nums[2] ，因为 6 被 2 整除；nums[3] ，因为 6 被 3 整除；以及 nums[6] ，因为 6 被 6 整除。 
因此，nums 中所有元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63 。 

提示：

• 1 <= nums.length == n <= 50
• 1 <= nums[i] <= 50

地址

https://leetcode.cn/contest/weekly-contest-354/problems/sum-of-squares-of-special-elements/

题意

直接模拟

思路

1. 直接模拟即可，比较坑的不要看错题目，数组的长度对每个 $i$ 取模；
2. 复杂度分析：

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

代码

[sol1-C++]

class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (n % (i + 1) == 0) {
                res += nums[i] * nums[i];
            }
        }
        return res;
    }
}; 

---

2779. 数组的最大美丽值

给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中，你可以执行下述指令：

• 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
• 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。

注意：你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

示例 1：

输入：nums = [4,6,1,2], k = 2
输出：3
解释：在这个示例中，我们执行下述操作：
- 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
- 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：

输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-354/problems/maximum-beauty-of-an-array-after-applying-operation/

题意

排序 + 二分查找或者双指针

思路

1. 由于子数组可以不连续，因此我们首先要对整个数组进行排序，从中选择合适的部分数据即可。如使得 $[nums[i] - k,nums[i] + k]$ 能够满足题目要求，这就要求数组中的最大值与最小值的差不超过 $2k$，此时我们依次模拟即可，找到连续的窗口使得最大值与最小值的差值小于 $2k$。

2. 复杂度分析：

• 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
• 空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i <= maxVal; i++) {
            int l = i - k;
            int r = i + k;
            auto it1 = upper_bound(nums.begin(), nums.end(), r);
            auto it2 = lower_bound(nums.begin(), nums.end(), l);
            int d = it1 - it2;
            res = max(res, d);
        }
        return res;
       
    }
};


class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0, j = 0; i < nums.size(); i++) {
            while (i < nums.size() && nums[i] - nums[j] > 2 * k) {
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

---

2780. 合法分割的最小下标

如果元素 x 在长度为 m 的整数数组 arr 中满足 freq(x) * 2 > m ，那么我们称 x 是 支配元素 。其中 freq(x) 是 x 在数组 arr 中出现的次数。注意，根据这个定义，数组 arr 最多 只会有 一个 支配元素。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。

你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i + 1, ..., n - 1] ，如果一个分割满足以下条件，我们称它是 合法 的：

• 0 <= i < n - 1
• nums[0, ..., i] 和 nums[i + 1, ..., n - 1] 的支配元素相同。

这里， nums[i, ..., j] 表示 nums 的一个子数组，它开始于下标 i ，结束于下标 j ，两个端点都包含在子数组内。特别地，如果 j < i ，那么 nums[i, ..., j] 表示一个空数组。

请你返回一个 合法分割 的 最小 下标。如果合法分割不存在，返回 -1 。

示例 1：

输入：nums = [1,2,2,2]
输出：2
解释：我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。
数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 > 3 。
数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 > 1 。
两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 2 是合法分割中的最小下标。

示例 2：

输入：nums = [2,1,3,1,1,1,7,1,2,1]
输出：4
解释：我们将数组在下标 4 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。
数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 4 是所有合法分割中的最小下标。

示例 3：

输入：nums = [3,3,3,3,7,2,2]
输出：-1
解释：没有合法分割。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• nums 有且只有一个支配元素。

地址

https://leetcode.cn/contest/weekly-contest-354/problems/minimum-index-of-a-valid-split/

题意

哈希统计

思路

1. 根据题意本质为众数问题，我们知道如果一个数组的众数为 $x$ ，则将数组分割为两个子数组，则子数组中至少有一个子数组的众数一定也为 $x$，这可以用反证法来证明。因此本题目就非常简单了，由于可以知道合法的分割中的支配元素与分割前的支配元素相同，因此我们首先找到数组中的支配元素为 $x$，此时我们可以找到数组的某个分割点 $i$, 统计前后两个子数组中含有 $x$ 的统计次数即可，是否满足如下两个条件：

   $$cnt_1[x] > \dfrac{i +1}{2} \\ cnt[x] - cnt_1[x] > \dfrac{n - i -1}{2}$$

2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        int n = nums.size();
        int val = 0;
        int total = 0;
        unordered_map<int, int> cnt;
        for (auto v : nums) cnt[v]++;
        for (auto [x, freq] : cnt) {
            if (freq * 2 > n) {
                val = x;
                total = freq;
            }
        }
        int curr = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == val) {
                curr++;
            }
            if (curr * 2 > (i + 1) && (total - curr) * 2 > (n - i - 1)) {
                return i;
            }
        }
        return -1;
    }
};

---

2781. 最长合法子字符串的长度

给你一个字符串 word 和一个字符串数组 forbidden 。

如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。

请你返回字符串 word 的一个 最长合法子字符串 的长度。

子字符串 指的是一个字符串中一段连续的字符，它可以为空。

示例 1：

输入：word = "cbaaaabc", forbidden = ["aaa","cb"]
输出：4
解释：总共有 9 个合法子字符串："c" ，"b" ，"a" ，"ba" ，"aa" ，"bc" ，"baa" ，"aab" 和 "aabc" 。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 "aaa" ，要么包含 "cb" 。

示例 2：

输入：word = "leetcode", forbidden = ["de","le","e"]
输出：4
解释：总共有 11 个合法子字符串："l" ，"t" ，"c" ，"o" ，"d" ，"tc" ，"co" ，"od" ，"tco" ，"cod" 和 "tcod" 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 "de" ，"le" 和 "e" 之一。

提示：

• 1 <= word.length <= 105
• word 只包含小写英文字母。
• 1 <= forbidden.length <= 105
• 1 <= forbidden[i].length <= 10
• forbidden[i] 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-354/problems/length-of-the-longest-valid-substring/

题意

$trie$ + 双指针

思路

1. 题目的关键在于所有 $forbidden$ 的字符串的长度小于 $10$，此时我们每次将字符串左端点移动一步，此时检测当前字符串是否含有 $forbidden$ 中的字符串，如果含有被禁止的字符，假设当前字符串的起点为 $i$，所有含有 $s[i]$ 为起点的 $forbidden$ 字符串分别为 $s[i\cdots k_0], s[i\cdots k_1], s[i\cdots k_2], \cdots$，此时我们知道以 $i$ 开始且不含有 $forbidden$ 的字符串的最长长度一定为 $s[i\cdots \min(k_j)-1]$。如果能够快速的搜索当前字符串是否包含指定字符串的前缀呢？此时我们想到了利用 $trie$ 树，则利用 $trie$ 树快速的搜索出最短长度，然后将字符串的终点位置进行移动，假设当前字符的起点为 $l$, 终点为 $r$，此时我们只需要检测 $s[l\cdots r]$ 是否含有 $forbidden$ 的前缀即可。
2. 复杂度分析：

• 时间复杂度：$O(nU)$，其中 $n$ 表示字符串的长度，$U$ 表示 $forbidden$ 数组中控字符串的最大长度。
• 空间复杂度：$O(mU)$，其中 $m$ 表示字符串 $forbidden$ 数组的长度，$U$ 表示 $forbidden$ 数组中字符串的最大长度。。

代码

struct Trie{
    bool isWord;
    int len;
    vector<Trie *> next;
    Trie() {
        this->isWord = false;
        this->len = 0;
        this->next = vector<Trie *>(26, nullptr);
    }
};

bool insertTrie(struct Trie *trie, string &word) {
    struct Trie *node = trie;
    for (auto c : word) {
        if (node->next[c - 'a'] == nullptr) {
            node->next[c - 'a'] = new Trie();
        }
        node = node->next[c - 'a'];
    }
    node->isWord = true;
    node->len = word.size();
    return true;
}

int search(struct Trie *trie, string &word) {
    struct Trie *node = trie;
    for (auto c : word) {
        if (node->next[c - 'a'] == nullptr) {
            return -1;
        }
        node = node->next[c - 'a'];
        if (node->isWord) {
            return node->len;
        }
    }
    return -1;
}


class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        struct Trie *trie = new Trie();
        int maxlen = 0;
        for (auto w : forbidden) {
            insertTrie(trie, w);
            maxlen = max(maxlen, int(w.size()));
        }
        int n = word.size();
        int res = 0;
        for (int l = n - 1, r = n - 1; l >= 0; l--) {
            string curr = word.substr(l, min(r - l + 1, maxlen));
            int len = search(trie, curr);
            if (len < 0) {
                res = max(res, r - l + 1);
            } else {
                r = l + len - 2;
            }
        }
        return res;
    }
};

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

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