LeetCode 226场周赛题解

Stella981
• 阅读 679

【GiantPandaCV导语】这是LeetCode第226场周赛题解,本周考察的知识点有枚举,贪心,前缀和,Manacher回文算法,动态规划,图论等。

比赛链接

题目一:盒子中小球的最大数量

LeetCode 226场周赛题解

题面

  • 解题思路:按照题意模拟一下即可。

  • 时间复杂度:

  • 空间复杂度:

  • 解题代码如下:

class Solution { public:     int a[100];     int f(int x){         int ans=0;         while(x){             ans+=x%10;             x/=10;         }         return ans;     }     int countBalls(int lowLimit, int highLimit) {         int ans=0;         for(int i=lowLimit; i<=highLimit; i++){             a[f(i)]++;         }         for(int i=1; i<100; i++){             if(a[i]>ans){                 ans=a[i];             }         }         return ans;     } };

题目二:从相邻元素对还原数组

LeetCode 226场周赛题解

题面

  • 解题思路:看了一分钟似乎没有思路?然后再想想我们会发现如果把这个相邻关系看成一个无向图的边这个图会是什么样子?其实这个图会退化成一条链,我们只需要找到这个链的头部或者尾部节点就可以一下把这个链拎起来,然后我们就获得了答案了。头部节点或者尾部节点怎么找?直接找入度或者出度为0的点就可以了。另外注意一下,图中节点可能是负数,所以需要加一个offset(我直接取了100000)来方便处理。

  • 时间复杂度:

  • 空间复杂度:

  • 解题代码如下:

class Solution { public:     int cnt[200010];     vector <int> G[200010];     vector <int> ans;     void dfs(int root, int fa){         ans.push_back(root-100000);         for(int i=0; i<G[root].size(); i++){             int v = G[root][i];             if(v == fa) continue;             dfs(v, root);         }     }     vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {         int n = adjacentPairs.size();         for(int i=0; i<n; i++){             int u = adjacentPairs[i][0];             int v = adjacentPairs[i][1];             u += 100000;             v += 100000;             G[u].push_back(v);             G[v].push_back(u);             cnt[v]++;             cnt[u]++;         }         int id = 0;         for(int i=0; i<200010; i++){             if(cnt[i]==1){                 id = i;                 break;             }         }         ans.clear();         dfs(id, -1);         return ans;     } };

题目三:你能在你最喜欢的那天吃到你最喜欢的糖果吗?

LeetCode 226场周赛题解

题面

  • 解题思路:其实是一个非常简单的题目,只要推一下第一组样例应该就差不多了。对于每一个查询,我们可以O(1)判断是否可以在第 favoriteDayi天吃到 favoriteTypei类糖果。具体怎么判断呢?我们可以看到由于第二个条件的限制,在吃第 类糖果的时候,那么 类一定被吃掉了,那么我们可以i对所有的糖果维护一个前缀和。然后我们反向思考什么情况下这个人在第 天是吃不到 favoriteTypei类苹果的:

  • 一种情况就是这个人每天都吃了 dailyCapi(上限)这么多个苹果,但是还是不够数,也就是说 favoriteTypei类之前的苹果还有剩余。

  • 另外一种情况就是这个人每天只吃一个苹果,但是到 favoriteDayi天吃的苹果数量(也就是天数)都已经超过了 favoriteTypei前所有的苹果数量,这样也是不行的。

  • 时间复杂度:

  • 空间复杂度:

  • 解题代码如下:

class Solution { public:     int n;     long long sum[100010];     bool check(long long type, long long day, long long cap){         if(sum[type-1]>=(long long)(cap*day)) return false;         if(day>sum[type]) return false;         return true;     }     vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {         n = candiesCount.size();         for(int i=1; i<=n; i++){             sum[i]=sum[i-1]+candiesCount[i-1];         }         vector<bool>ans;         for(int i=0; i<queries.size(); i++){             long long type = queries[i][0];             long long day = queries[i][1];             long long cap = queries[i][2];             type++;             day++;             if(check(type, day, cap)){                 ans.push_back(true);             }             else{                 ans.push_back(false);             }         }         return ans;     } };

题目四:回文串分割 IV

LeetCode 226场周赛题解

题面

  • 解题思路:这道题其实有两种解法,一种是适合本地2e3的数据范围,一种是适合2e4的数据范围,接下来我就讲一下这两种做法。

解题方法一:O(n^2) DP

  • 解题思路:这是针对本题的数据范围的一种解法,我们设 dp[i][j]表示字符串中的 这一段字串是否是回文串,我们可以从后往前枚举字串的起点进行DP方程状态的更新。维护完这个数组之后我们就可以枚举第一个子段的终点和第二个子段的起点来判断获得最终答案了。

  • 时间复杂度:

  • 空间复杂度:

  • 解题代码:

class Solution { public:  bool checkPartitioning(string s) {   int n = s.length();   vector<vector<bool>> p(n, vector<bool>(n));   for (int i = n - 1; i >= 0; --i) {    p[i][i] = true;    for (int j = i + 1; j < n; ++j) {     if (s[i] == s[j]) {      p[i][j] = (i + 1 == j || p[i + 1][j - 1]);     }    }   }   for (int i = 0; i < n; ++i) {    if (p[0][i]) {     for (int j = i + 1; j < n - 1; ++j) {      if (p[i + 1][j] && p[j + 1][n - 1]) {       return true;      }     }    }   }   return false;  } };

解题方法二:枚举+Manacher

  • 解题思路:先用Manacher算法得到以每个点为中心的最大回文串的左右边界 le[i]ri[i]。并且当 le[i]==1(即该回文串向左可以到达字符串的边界)时,记录下来, le1[ri[i]]=1,表示存在一个回文串左边界为1,右边界为 ri[i]。同理,当 ri[i]==n-1(字符串右边界)时, ri1[le[i]]=1。然后遍历中间的回文串的回文中心,令 t1=p[i]-1(回文串长度), t2=le[i](回文串左边界), t3=ri[i](回文串右边界),当 le1[t2]==1&& ri1[t3]==1时即找到了方案。如果不满足, t1-=2,t2+=2,t3-=2,继续判断,直到 t1<=0。要注意的是当 t2==1或者 t3==n-1时该回文串不能作为中间回文串。关于Manacher算法不了解的读者请看: https://oi-wiki.org/string/manacher/

  • 时间复杂度:

  • 空间复杂度:

  • 解题代码:

`const int maxn=2e3+5;
int T,n,ans,p[maxn<<1],le[maxn<<1],ri[maxn<<1];
int le1[maxn<<1],ri1[maxn<<1];
char s[maxn<<1],ss[maxn];

void manacher(){
    int mid=0,r=0;
    for(int i=1;i<n;++i){
        if(r>=i) p[i]=min(p[(mid<<1)-i],r-i+1);
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>r) r=i+p[i]-1,mid=i;
        int tmp=p[i]-1;
        le[i]=i-tmp,ri[i]=i+tmp;
        if(le[i]==1) le1[ri[i]]=1;
        if(ri[i]==n-1) ri1[le[i]]=1;
    }
}

class Solution {
public:
    bool checkPartitioning(string s2) {
        ans = 0;
        n = s2.size();
        for(int i=0; i<n; i++) ss[i]=s2[i];
        
        s[0]='~',s[1]='|';
        for(int i=0;i<n;++i)
            s[2*i+2]=ss[i],s[2*i+3]='|';
        n=2*n+2;
        for(int i=0;i<n;++i)
            p[i]=0,le1[i]=0,ri1[i]=0;
        manacher();
        for(int i=1;i<n;++i){
            int t1=p[i]-1,t2=le[i],t3=ri[i];
            if(t2==1||t3==n-1){
                t1-=2;
                t2+=2;
                t3-=2;
            }
            while(t1>0){
                if(le1[t2]&&ri1[t3]){
                    ans=1;
                    break;
                }
                t1-=2;
                t2+=2;
                t3-=2;
            }
            if(ans) break;
        }
        if(ans) return true;
        else return false;
    }
};
`

来看一下两种解法在评测机上的耗时情况:

LeetCode 226场周赛题解

Manacher算法明显优于O(n^2)动态规划


欢迎关注GiantPandaCV, 在这里你将看到独家的深度学习分享,坚持原创,每天分享我们学习到的新鲜知识。( • ̀ω•́ )✧

有对文章相关的问题,或者想要加入交流群,欢迎添加BBuf微信:

LeetCode 226场周赛题解

二维码

为了方便读者获取资料以及我们公众号的作者发布一些Github工程的更新,我们成立了一个QQ群,二维码如下,感兴趣可以加入。

LeetCode 226场周赛题解

公众号QQ交流群

本文分享自微信公众号 - GiantPandaCV(BBuf233)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
LeetCode 第225场周赛题解
【GiantPandaCV导语】这是LeetCode的第225场周赛的题解,本期考察的知识点有暴力,前缀和,推导等等。比赛链接https://leetcodecn.com/contest/weeklycontest225/题目一:替换隐藏数字得到的最晚时间!(h
Stella981 Stella981
3年前
JS 苹果手机日期显示NaN问题
问题描述newDate("2019122910:30:00")在IOS下显示为NaN原因分析带的日期IOS下存在兼容问题解决方法字符串替换letdateStr"2019122910:30:00";datedateStr.repl
Stella981 Stella981
3年前
LeetCode 227场周赛题解
【GiantPandaCV导语】这是LeetCode的第227场周赛的题解,本期考察的知识点有「暴力,字符串,二进制枚举」等等。比赛链接https://leetcodecn.com/contest/weeklycontest227/题目一:检查数组是否经排序和轮转得到
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这