LeetCode --- 406周赛

题目列表

3216. 交换后字典序最小的字符串

3217. 从链表中移除在数组中存在的节点

3218. 切蛋糕的最小总开销 I

3219. 切蛋糕的最小总开销 II

一、交换后字典序最小的字符串

这题读懂题目要求就行,关键在于字典序的理解,由于只能交换一次,肯定是优先改变靠前的字符顺序,才能让字典序变得最小,代码如下

class Solution {
public:
    string getSmallestString(string s) {
        int n = s.size();
        for(int i = 1; i < n; i++){
            if(s[i]%2 == s[i-1]%2 && s[i] < s[i-1]){
                swap(s[i], s[i-1]);
                return s;
            }
        }
        return s;
    }
};

二、从链表中移除在数组中出现的结点

考察链表的增删查改,基本数据结构,没啥可说的,代码如下

/**
 * 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) {
        ListNode *newhead = nullptr, *tail = nullptr, *cur = head;
        unordered_set<int> st(nums.begin(), nums.end());
        while(cur) {
            if(st.count(cur->val) == 0) {
                if(newhead == nullptr) {
                    newhead = tail = cur;
                } else {
                    tail = tail->next = cur;
                }
            }
            cur = cur->next;
        }
        if(tail) tail->next = nullptr;
        return newhead;
    }
};

三、切蛋糕的最小总开销 I & II

这题其实很适合用分治来写,一块蛋糕切一次,分成两块蛋糕,在分别对这两个蛋糕进行切分,很标准将一个问题划分成两个更小规模的重复子问题,代码如下

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        int a = horizontalCut.size(), b = verticalCut.size();
        int memo[a+1][a+1][b+1][b+1];
        memset(memo,-1,sizeof(memo));
        function<int(int,int,int,int)>dfs=[&](int up,int down,int left,int right)->int{
            if(up == down && left == right) return 0;
            if(memo[up][down][left][right]!=-1) return memo[up][down][left][right];
            int res = INT_MAX;
            for(int i = up; i < down; i++){ // 枚举切割哪一行
                res = min(res, dfs(up,i,left,right) + dfs(i+1,down,left,right) + horizontalCut[i]);
            }
            for(int i = left; i < right; i++){ // 枚举切割哪一列
                res = min(res, dfs(up,down,left,i) + dfs(up,down,i+1,right) + verticalCut[i]);
            }
            return memo[up][down][left][right] = res;
        };
        return dfs(0,a,0,b);
    }
};

但是数据范围增大之后,这样做就会超时,这里我们就需要去考虑贪心了。

如何贪心?我们模拟一下切蛋糕的过程,能得出下面几个结论:

  • 1、无论如何切,切的次数总是相同的,因为每次切都只会增加一个独立的蛋糕,一开始只有一块,分出的块数固定为m*n,故一共要切m*n - 1刀
  • 2、切的顺序不同,总能被化简为,每次切都是将某一行/某一列全部切完才算结束的情况,如下图

  • 3、每次横切一刀之后,下次的竖切次数就会+1,同理每次竖切一刀之后,下次的横切次数就会+1,因为横切之后,原本一块蛋糕就成了两块蛋糕,故竖切一刀也就变成了两刀,竖切同理,如下图

  • 4、由3可知:竖切不会影响竖切,横切也不会影响横切,所以我们只要考虑竖切和横切哪个先就行

代码如下

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        long long ans = 0;
        ranges::sort(horizontalCut);
        ranges::sort(verticalCut);
        int h = 1, v = 1;
        int i = horizontalCut.size()-1, j = verticalCut.size()-1;
        while(i>=0 || j>=0) {
            if(i < 0){
                int y = verticalCut[j];
                ans += 1LL*v*y;
                j--;
            }else if(j < 0){
                int x = horizontalCut[i];
                ans += 1LL*h*x;
                i--;
            }else{
                int x = horizontalCut[i];
                int y = verticalCut[j];
                if(x > y){
                    ans += 1LL*x*h;
                    v++, i--;
                }else{
                    ans += 1LL*v*y;
                    h++, j--;
                }
            }
        }
        return ans;
    }
};

相关推荐

  1. LeetCode406个人题解

    2024-07-20 17:28:06       23 阅读
  2. LeetCode401个人题解

    2024-07-20 17:28:06       32 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 17:28:06       123 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 17:28:06       131 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 17:28:06       109 阅读
  4. Python语言-面向对象

    2024-07-20 17:28:06       117 阅读

热门阅读

  1. 二分 以及例题

    2024-07-20 17:28:06       31 阅读
  2. MySQL——视图

    2024-07-20 17:28:06       27 阅读
  3. Window任务栏应用图片无法加载解决方法

    2024-07-20 17:28:06       31 阅读
  4. linux shell(上)

    2024-07-20 17:28:06       31 阅读
  5. RK3588 编译opencv&opencv_contrib记录

    2024-07-20 17:28:06       35 阅读
  6. 二叉树---路径总和

    2024-07-20 17:28:06       25 阅读
  7. windows 安装 kubectl 并连接到 k8s 集群【图文教程】

    2024-07-20 17:28:06       26 阅读
  8. computeIfAbsent 和 putIfAbsent

    2024-07-20 17:28:06       27 阅读
  9. 微软Edge浏览器全解析教程

    2024-07-20 17:28:06       25 阅读