tags: Weekly Contest

Weekly Contest 390

3090. Maximum Length Substring With Two Occurrences (Easy)

限制 :

• 2 <= s.length <= 100
• s consists only of lowercase English letters.

Solution

利用前後夾擊的方式算出最長的序列，有點類似 LCS ，但又不太像。

時間複雜度:

$O(n^2)$

空間複雜度:

$O(n)$

程式碼:

class Solution {
public:
    int max_len_of_string(string str, int begin, int end)
    {
        map<char, int> record;
        for (int i = begin; i <= end; i++)
        {
            auto it = record.find(str[i]);
            if (it == record.end())
            {
                record[str[i]] = 0;
            }
            record.find(str[i])->second++;
            if (record.find(str[i])->second > 2)
            {
                return i;
            }
        }
        return end;
    }
    int maximumLengthSubstring(string s) {
        int max_num = 0;
        for (int i = 0; i < s.size(); i++)
        {
            max_num = max(max_num, max_len_of_string(s, i, s.size()) - i);
        }
        return max_num;
    }
};

3091. Apply Operations to Make Sum of Array Greater Than or Equal to k (Medium)

限制 :

• 1 <= k <= 105

Solution

計算 k 的平方根 sqrt_num。如果 k 是完全平方數，最小操作數為 sqrt_num + sqrt_num - 2。如果 k 接近完全平方數，則為 sqrt_num + sqrt_num - 1。其他情況下，操作數量為 sqrt_num + sqrt_num。

時間複雜度:

$O(1)$

空間複雜度:

$O(1)$

程式碼:

class Solution {
public:
    int minOperations(int k) {
        int sqrt_num = sqrt(k);
        if (sqrt_num * sqrt_num == k)
            return sqrt_num + sqrt_num - 2;
        else if ((sqrt_num + 1) * sqrt_num >= k) {
            return sqrt_num + sqrt_num - 1;
        } else
            return sqrt_num + sqrt_num;
    }
};

3092. Most Frequent IDs(Medium)

限制 :

• 1 <= nums.length == freq.length <= 105
• 1 <= nums[i] <= 105
• -105 <= freq[i] <= 105
• freq[i] != 0
• The input is generated such that the occurrences of an ID will not be negative in any step.

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼:

4(Hard)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼: