Leetcode 双周赛题解 40

ACM算法日常

发布于 2020-12-15 09:49:06

3800

发布于 2020-12-15 09:49:06

文章被收录于专栏：ACM算法日常

leetcode双周赛40

5557. 最大重复子字符串

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 「重复值为 k」。单词 word 的 「最大重复值」 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。

给你一个字符串 sequence 和 word ，请你返回 「最大重复值 k」。

「示例 1：」

输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。

「示例 2：」

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

「提示：」

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence 和 word 都只包含小写英文字母。

「思路」

既然要求word在sequence中连续出现的最大次数，而数据范围小于等于100，那么枚举答案即可，然后用size_t find (const string& str, size_t pos = 0)判断是否包含某个子串。

时间复杂度：

O(n^2)

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        if(sequence.find(word) == string::npos) return 0;
        string ret = word;
        for(int i = 2; ; ++i) {
            ret += word;
            if(sequence.find(ret) == string::npos) return i - 1;
        }
        return 0;
    }
};

5558. 合并两个链表

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。

「示例 1：」

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

「提示：」

3 <= list1.length <= 10000
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10000

「思路」

经典链表基础题，按照题意模拟即可，锻炼对基础数据结构的熟悉程度。应该也是面试经常会考的题目。

时间复杂度：

O(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        int i = 0;
        ListNode* st = list1;
        while(1) {
            if(i == a - 1) {//找到前一段最后一个节点
                ListNode* tmp = list1;
                b = b - a + 2;
                while(b --) list1 = list1->next;//找到第三段起点
                tmp->next = list2;//将第二个字符串接上去
                while(list2->next != nullptr) list2 = list2->next;
                list2->next = list1;//将最后一段接上去
                break;
            }else {
                list1 = list1->next;
                ++ i;
            }
        }
        return st;
    }
};

5560. 设计前中后队列

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：

FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的 「最前面」 。
void pushMiddle(int val) 将 val 添加到队列的 「正中间」 。
void pushBack(int val) 将 val 添加到队里的 「最后面」 。
int popFront() 将 「最前面」 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将 「正中间」 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将 「最后面」 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

请注意当有 「两个」 中间位置的时候，选择靠前面的位置进行操作。比方说：

将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, **6**, 3, 4, 5] 。
从 [1, 2, **3**, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。

「示例 1：」

输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）

「提示：」

1 <= val <= 109
最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。

「思路」

因为调用函数的次数不超过1000次，那么数组长度也不会超过1000，

O(n^2)

模拟这个过程即可。

同样还是锻炼基础数据结构熟悉程度的题目，锻炼码力题。

注意题目给定「中位数的概念」，我选择用vecotr模拟：

pushFront：将数组整体后移一位，然后改变第一位值
pushMiddle：将数组整体后移mid位，然后改变中位数值
pushBack：自带的push_back即可
popFront：数组整体前移一位，然后pop_back
popMiddle ：数组整体前移mid位，然后pop_back
popBack ：自带的pop_back即可

时间复杂度：

O(n^2)

class FrontMiddleBackQueue {
public:
    vector<int> vs;
    int n;
    FrontMiddleBackQueue() {
        vs.clear();
    }
    void pushFront(int val) {
        vs.push_back(val);
        n = vs.size();
        for(int i = n - 1; i >= 1; --i) vs[i] = vs[i - 1];
        vs[0] = val;
    }
    
    void pushMiddle(int val) {
        vs.push_back(val);
        n = vs.size();
        int mid = (n + 1) / 2;
        for(int i = n - 1; i >= mid; --i) vs[i] = vs[i - 1];
        vs[mid - 1] = val;
    }
    
    void pushBack(int val) {
        vs.push_back(val);
    }
    
    int popFront() {
        n = vs.size();
        if(n == 0) return -1;
        int x = vs[0];
        for(int i = 0; i < n - 1; ++i) vs[i] = vs[i + 1];
        vs.pop_back();
        return x;
    }
    
    int popMiddle() {
        n = vs.size();
        if(n == 0) return -1;
        int mid = (n % 2 == 0?(n/2-1):(n/2));
        int x = vs[mid];
        for(int i = mid; i < n - 1; ++i) vs[i] = vs[i + 1];
        vs.pop_back();
        return x;
    }
    
    int popBack() {
        n = vs.size();
        if(n == 0) return -1;
        int x = vs.back();
        vs.pop_back();
        return x;
    }
};

5559. 得到山形数组的最少删除次数

我们定义 arr 是 「山形数组」 当且仅当它满足：

arr.length >= 3
存在某个下标i(从0开始)满足0 < i < arr.length - 1且：
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums ，请你返回将 nums 变成 「山形状数组」 的 「最少」 删除次数，就是最少删除多少个元素。

「示例 1：」

输入：nums = [1,3,1]
输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。

「示例 2：」

输入：nums = [2,1,1,5,6,2,3,1]
输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

「示例 3：」

输入：nums = [4,3,2,1,1,2,3,1]
输出：4

「提示：」

3 <= nums.length <= 1000
1 <= nums[i] <= 109
题目保证 nums 删除一些元素后一定能得到山形数组。

「思路」

顶峰的左边是一段连续的子序列，并且是递增的子序列；顶峰的右边是一段连续的子序列，并且是递减的子序列。

显然最少删除次数，就是让左右的子序列越长越好。

那么我们用最长上升子序列算法

O(n*log(n))

算出以每个元素为右端点的最长上升子序列长度ls[i]，和以每个元素为左端点的最长下降组序列长度rs[i]，答案就是最小的n - 1 - ls[i] - rs[i]。

时间复杂度：

O(n*log(n))

class Solution {
public:
    int minimumMountainRemovals(vector<int>& ar) {
        int n = ar.size();
        vector<int> ls(n, 0), rs(n, 0), dp(n, 0x3f3f3f3f);
        for(int i = 0; i < n; ++i) {
            int p = lower_bound(dp.begin(), dp.end(), ar[i]) - dp.begin();
            dp[p] = ar[i];
            ls[i] = p;
        }
        fill(dp.begin(), dp.end(), 0x3f3f3f3f);
        for(int i = n - 1; i >= 0; --i) {
            int p = lower_bound(dp.begin(), dp.end(), ar[i]) - dp.begin();
            dp[p] = ar[i];
            rs[i] = p;
        }
        int ans = n;
        for(int i = 1; i < n - 1; ++i) {
            ans = min(ans, n - 1 - ls[i] - rs[i]);
        }
        return ans;
    }
};