Home Code Leetcode

# 第 390 场周赛

第一题写的匆匆忙，都使用暴力，居然 WA , 单纯就是粗心写快了
第二题也没有分析太多，上来直接给它写了一个 bfs，果不其然，超时了。后来仔细分析了一些，就贪过去了
第三题这种懒更新的手法之前也遇到过，思维算是比较简单（之前遇到过的话）
第四题感觉就是裸的哈希题，就是复制粘贴出现了问题，没有改长度（输入的两个数组分别取长度 n 和 m）

# 每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

示例 1：

输入： s = "bcbbbcba"

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次： "bcbbbcba" 。

示例 2：

输入： s = "aaaa"

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次： "aaaa" 。

提示：

  • 2 <= s.length <= 100
  • s 仅由小写英文字母组成

# 思路一（暴力枚举）

暴力枚举每个子串，统计其中出现的字母出现次数，最后做一次判断，若每个字母出现次数均不大于 2，那么更新答案，取 MAX

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int n = s.size();
        int maxv = 1;
        for(int i = 0; i < n; i ++ ){
            for(int j = i; j < n; j ++ ){
                unordered_map<char, int> mp;
                for(int k = i; k <= j; k ++ )   mp[s[k]] ++ ;
                bool flag = true;
                for(auto &item : mp){
                    if(item.second >= 3)    flag = false;
                }
                if(flag)    maxv = max(maxv, j - i + 1);
            }
        }
        return maxv;
    }
};

复杂度分析

  1. 时间复杂度：O(n2)O(n^2)，其中 n 为 s 的长度
  2. 空间复杂度：O(1)O(1)，每次统计只需要使用 26 空间大小的数组

# 思路二（双指针）

不难看出使用暴力枚举，其中会涉及到一些重复统计的操作：比如当需要统计从 i 开始的字符串，判断长度为 4 和长度为 5 的字符串是否满足条件时，使用暴力的方法会以此重新遍历，而一个更好的方法的在统计长度为 4 的子串的基础之上，得出长度为 5 的子串的字符出现次数.

class Solution {
public:
    int cnt[26];
    int maximumLengthSubstring(string s) {
        int n = s.size();
        memset(cnt, 0, sizeof cnt);
        int maxv = 0;
        for(int i = 0, j = 0; i < n; i ++ ){
            cnt[s[i] - 'a'] ++ ;
            while(cnt[s[i] - 'a'] >= 3) cnt[s[j ++ ] - 'a'] -- ;
            maxv = max(maxv, i - j + 1);
        }
        return maxv;
    }
};

复杂度分析

  1. 时间复杂度：O(n)O(n)，其中 n 为 s 的长度
  2. 空间复杂度：O(1)O(1)，每次统计只需要使用 26 空间大小的数组

# 执行操作使数据元素之和大于等于 K

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下 任意 操作 任意 次数（可能为零）：

  • 选择数组中的任何一个元素，然后将它的值 增加 1 。
  • 复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之 和 大于或等于 k 所需的 最少 操作次数。

示例 1：

输入： k=11

输出： 5

解释：

可以对数组 nums = [1] 执行以下操作：

  • 将元素的值增加 1 三次。结果数组为 nums = [4] 。
  • 复制元素两次。结果数组为 nums = [4,4,4]

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。

示例 2：

输入： k=1

输出： 0

解释：

原始数组的和已经大于等于 1 ，因此不需要执行操作。

提示：

  • 1 <= k <= 100000

# 思路 (贪心)

加一操作都应当在复制操作之前，证明如下.

不防设当前数组最大值为mm，那么存在两种操作：

  • 先复制，再加一，那么元素和增加了m+1m + 1
  • 先加一，再复制，那么元素和增加了m+2m + 2

两种操作使得最终数组的最大值均为 m+1 ，但是第二种操作会使得数组元素和更大.

那么我们可以枚举前面的加一操作的次数add=0,1,2,...,k−1add = 0, 1, 2, ..., k -1 次，设至少还需要进行xx 次复制操作使得数组元素和大于kk，则(add+1)∗(x+1)≥k(add + 1) * (x + 1) \geq k，那么x≥⌈kadd+1⌉−1x \geq \lceil \frac{k}{add+1} \rceil -1，对所以的x+addx + add 去最小值即可

class Solution {
public:
    int minOperations(int k) {
        int minv = 1e9 + 10;
        for(int add = 0; add <= k - 1; add ++ ){
            int v = 1 + add;
            int x = ((k + add) / (add + 1)) - 1;
            minv = min(minv, x + add);
        }
        return minv;
    }
};

复杂度分析

  1. 时间复杂度：O(k)O(k)
  2. 空间复杂度：O(1)O(1)

# 最高频率的 ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ， nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

  • 增加 ID 的数目： 如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
  • 减少 ID 的数目： 如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。

请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，如果在某次操作后集合为空，那么 ans[i] 为 0 。

示例 1：

输入： nums = [2,3,2,1], freq = [3,2,-3,1]

输出： [3,3,2,2]

解释：

第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

示例 2：

** 输入：**nums = [5,5,3], freq = [2,-2,1]

输出：[2,0,1]

解释：

第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。

提示：

  • 1 <= nums.length == freq.length <= 100000
  • 1 <= nums[i] <= 100000
  • -105 <= freq[i] <= 100000
  • freq[i] != 0
  • 输入保证任何操作后，集合中的元素出现次数不会为负数

# 思路（哈希表 + 懒删除堆）

  1. 维护一个哈希表，用于统计每个数出现的次数
  2. 维护一个堆，堆中保存一个值和出现次数的 pair ，堆顶元素的出现次数最大.
  3. 每次进行删除或增加操作时，都将最新的 pair 存入到堆中
  4. 对于堆中的元素，可能是失效的，每次取出现频率最大的元素时区哈希表内检查其是否有效，无效就弹出
class Solution {
public:
    typedef long long ll;
    typedef pair<ll, ll> pii;
    struct cmp{
        bool operator()(const pii&a, const pii &b){
            return a.second < b.second;
        }
    };
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        unordered_map<ll, ll> mp;
        int n = nums.size();
        vector<ll> res(n);
        priority_queue<pii, vector<pii>, cmp> qu; 
        for(int i = 0; i < n; i ++ ){
            mp[nums[i]] += freq[i];
            if(mp[nums[i]] != 0)    qu.push({nums[i], mp[nums[i]]});
            while(!qu.empty()){
                auto tp = qu.top();
                if(mp[tp.first] != tp.second){
                    qu.pop();
                    continue;
                }
                break;
            }
            if(qu.empty())  res[i] = 0;
            else    res[i] = qu.top().second;
        }
        return res;
    }
};

复杂度分析

  1. 时间复杂度：O(nlogn)O(nlogn)，其中 n 指数组 nums 的长度
  2. 空间复杂度：O(n)O(n)

# 最长公共后缀查询

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。

请你返回一个整数数组 ans ，其中 ans[i] 是 wordsContainer 中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

** 输入：**wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]

输出：[1,1,1]

解释：

我们分别来看每一个 wordsQuery[i] ：

  • 对于 wordsQuery[0] = "cd" ， wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
  • 对于 wordsQuery[1] = "bcd" ， wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
  • 对于 wordsQuery[2] = "xyz" ， wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

示例 2：

** 输入：**wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]

输出：[2,0,2]

解释：

我们分别来看每一个 wordsQuery[i] ：

  • 对于 wordsQuery[0] = "gh" ， wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
  • 对于 wordsQuery[1] = "acbfgh" ，只有下标为 0 的字符串有最长公共后缀 "fgh" 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
  • 对于 wordsQuery[2] = "acbfegh" ， wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

提示：

  • 1 <= wordsContainer.length, wordsQuery.length <= 10000
  • 1 <= wordsContainer[i].length <= 5 * 1000
  • 1 <= wordsQuery[i].length <= 5 * 1000
  • wordsContainer[i] 只包含小写英文字母。
  • wordsQuery[i] 只包含小写英文字母。
  • wordsContainer[i].length 的和至多为 5 * 100000 。
  • wordsQuery[i].length 的和至多为 5 * 100000 。

# 思路（字符串哈希）

  1. 将 wordsContainer 中的每个元素 wordsContainer[i] 的后缀都通过哈希保存起来，其哈希值作为 哈希map 的 key ，值指定为点字符串的长度和下标 i.
  2. 每次添加操作实现检查当前的哈希值之前是否存在，如若不存在直接添加进哈希表，否则按照题中规则进行更新（保存长度最短，下标最小）
typedef unsigned long long ull;
typedef pair<int, int> pii;
class Solution {
public:
    unordered_map<ull, pii> mp;
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        int n = wordsContainer.size();
        int minLength = 1e9 + 10;
        int minIndex = -1;
        for(int i = 0; i < n; i ++ ){
            int length = wordsContainer[i].size();
            if(length < minLength)   minLength = length, minIndex = i;
            ull hash = 0;
            for(int j = length - 1; j >= 0; j -- ){
                hash = hash * 131 + wordsContainer[i][j];
                if(mp.find(hash) == mp.end())   mp[hash] = {length, i};
                else{
                    auto item = mp[hash];
                    if(item.first > length) mp[hash] = {length, i};
                }
            }
        }
        int m = wordsQuery.size();
        vector<int> res(m);
        for(int i = 0; i < m; i ++ ){
            int length = wordsQuery[i].size();
            ull hash = 0;
            bool flag = false;
            for(int j = length - 1; j >= 0; j -- ){
                hash = hash * 131 + wordsQuery[i][j];
                if(mp.find(hash) == mp.end())   continue;
                res[i] = mp[hash].second;
                flag = true;
            }
            if(!flag)   res[i] = minIndex;
        }
        return res;
    }
};

复杂度分析

  1. 时间复杂度：O(max(n,m))O(max(n, m))，其中 n 指数组 wordsContainer 内所以元素的长度和， m 指数组 wordsQuery 内所以元素的长度和
  2. 空间复杂度：O(max(n,m))O(max(n, m))，其中 n 指数组 wordsContainer 内所以元素的长度和， m 指数组 wordsQuery 内所以元素的长度和
Edited on Views times

Give me a cup of [coffee]~(￣▽￣)~*

Value WeChat Pay

WeChat Pay