LeetCode：第 406 场周赛

总结

彻底失败好吧，后面两个题确实没考虑清楚。这下要掉大分咯😭😭😭

Q1：100352. 交换后字典序最小的字符串

题目传送门：100352. 交换后字典序最小的字符串 - 力扣（LeetCode）

日常签到题

最后实现代码如下：

class Solution {
public:
    string getSmallestString(string s) {
        int n = s.size();
        for(int i=1;i<n;++i){
            int a = s[i-1]-'0', b = s[i]-'0';
            if (a%2==b%2&&b<a) {
                char tmp = s[i];
                s[i] = s[i-1];
                s[i-1] = tmp;
                break;
            }
        }
        return s;
    }
};

Q2：100368. 从链表中移除在数组中存在的节点

题目传送门：100368. 从链表中移除在数组中存在的节点 - 力扣（LeetCode）

链表题，链表好久没写了还卡了一下😭

最后实现代码如下：

/**
 * 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* modifiedList(vector<int>& nums, ListNode* head) {
        vector<bool> vis(100003, false);
        for(auto num : nums) vis[num] = true;
        ListNode *hhead = new ListNode(-1, head);
        ListNode *tmp = head; ListNode *prev = hhead;
        while (tmp!=nullptr) {
            while (tmp!=nullptr&&vis[tmp->val]) tmp = tmp->next;
            prev->next = tmp;
            prev = tmp; 
            if (tmp!=nullptr)tmp = tmp->next;
        }
        return hhead->next;
    }
};

以上为考试时实现的代码，第22行需要注意要判断一下，不然会有nullptr去指下一个的情况。

上面的代码还是太丑了，copy一个标准答案，以后可以这么写逻辑会更清晰一些。

class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        unordered_set<int> st(nums.begin(), nums.end());
        ListNode dummy(0, head);
        ListNode* cur = &dummy;
        while (cur->next) { // 从下一个节点开始看
            if (st.contains(cur->next->val)) {
                cur->next = cur->next->next; // 删除
            } else {
                cur = cur->next; // 向后移动
            }
        }
        return dummy.next;
    }
};

注意：LeetCode中的链表题都是没有哨兵节点的！！！

Q3：100361. 切蛋糕的最小总开销 I

题目传送门：100361. 切蛋糕的最小总开销 I - 力扣（LeetCode）

划分型问题，可以用二维DP思想来做，但是用到第四题会超时。

确实，听完了灵神的解析，此题就是一道贪心，考试的时候大体思路是对的，贪心有一个地方写错了导致此题没有做出来，确实也是考试的时候思考不够细致导致的，这个还需多加练习。

解决这题初步需要想到：

每条边都会被切完
横切的代价是，当前竖块数 * 横切消耗
竖切的代价是，当前横块数 * 竖切消耗

此题会使用交换论证法这种思想，具体证明还是推荐灵神的题解：贪心及其证明：交换论证法（Python/Java/C++/Go）

什么是交换论证法呢？具体而言就是我们将这个大问题先简化为讨论相邻两个决策的性质（讨论交换决策顺序对最终结果造成的影响），对于本题一个操作序列不难想到：

交换相邻两个横切操作，对最终答案不会有影响
同理，交换相邻两个竖切操作，对最终答案也不会造成影响

因此关键需要讨论交换两个不同的操作，我们设这两个操作的代价分别是：竖切 $costV$ 和横切 $costH$ ，在进行这两个操作之前，已经有 $cntH$ 个横块， $cntV$ 个竖块。不难得知先执行横切再执行竖切则所需耗费的代价是：

costH \times cntV + costV \times (cntH+1)

同理，先执行竖切再执行横切所耗费的代价是：

costV\times cntH + costH\times (cntV+1)

如果先执行竖切再执行横切会有更小的代价,不难列出下面的式子：

costV\times cntH + costH\times (cntV+1) < costH \times cntV + costV \times (cntH+1)

化简得：

costH < costV

这意味着，无论水平切割还是垂直切割，优先切开销较大的那条线，并且这个优先顺序与水平和垂直切割的次数（ $cntV$ , $cntH$ ）无关。换句话说，如果按照这个规则进行切割，将开销较大的操作移动到后面，会导致总开销更大。

这下这个问题转变为了一个使用双指针实现的贪心问题。

最后实现代码如下：

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        int cnt_vert = 1,cnt_horz = 1,ans=0;
        priority_queue<int> horiz,verti;
        for(auto cut : horizontalCut) horiz.push(cut);
        for(auto cut : verticalCut) verti.push(cut);
        while (!horiz.empty()&&!verti.empty()) {
            if (horiz.top() < verti.top()) {
                ans += verti.top()*cnt_horz; cnt_vert++;
                verti.pop();
            } else {
                ans += horiz.top()*cnt_vert; cnt_horz++;
                horiz.pop();
            }
        }
        while (!horiz.empty()){
            ans += horiz.top()*cnt_vert; cnt_horz++;
            horiz.pop();
        }
        while (!verti.empty()){
            ans += verti.top()*cnt_horz; cnt_vert++;
            verti.pop();
        }
        return ans;
    }
};

Q4：100367. 切蛋糕的最小总开销 II

题目传送门：100367. 切蛋糕的最小总开销 II - 力扣（LeetCode）

同Q3

最后实现代码如下：

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        int cnt_vert = 1,cnt_horz = 1;
        long long ans=0;
        priority_queue<int> horiz,verti;
        for(auto cut : horizontalCut) horiz.push(cut);
        for(auto cut : verticalCut) verti.push(cut);
        while (!horiz.empty()&&!verti.empty()) {
            if (horiz.top() < verti.top()) {
                ans += verti.top()*cnt_horz; cnt_vert++;
                verti.pop();
            } else {
                ans += horiz.top()*cnt_vert; cnt_horz++;
                horiz.pop();
            }
        }
        while (!horiz.empty()){
            ans += horiz.top()*cnt_vert; cnt_horz++;
            horiz.pop();
        }
        while (!verti.empty()){
            ans += verti.top()*cnt_horz; cnt_vert++;
            verti.pop();
        }
        return ans;
    }
};