LeetCode 第 53 场双周赛(三)

简介: LeetCode 第 53 场双周赛(三)

大家好,这里是一起打 Leetcode 竞赛系列文章的第 5 篇。

本周有周赛和双周赛,本文是对上午的双周赛 Biweekly Contest 53 的简单讲解和评论。以下会包括每一题的简单讲解,代码,难度分析,以及一些个人对这题的看法等,希望大家喜欢!

注意 : 题解并不一定都是最优解(代码以 pass 了 LeetCode 的 Oline Judge 为准),文章初衷是给读者们提供一定的想法和问题的解决方案。

前言 : 参加 Contest 的好处

  1. 每周抽点时间去练习和学习新的题目这对于个人的编程能力与问题解决能力都有很大的帮助。
  2. 在规定的时间内解决一定的题目,这和真实的OA (Online Assessment) 或者 Onsite 面试是一样的,可以把它当作一个很好的 Mock 练习机会。
  3. 当你有碰到做不出的题目的时候,你能知道自己的弱项在哪里,然后可以根据这进行加强和练习,比赛是一面给自己的镜子。

对本场比赛的一些看法

本场比赛难度相对比较正常,都是比较常规的题目,第三题稍微有点难度需要一点思考。

1876. 简单的暴力签到题1877. 一道贪心和双指针题目1878. 一道观察型的题目1879. 使用 bit 进行压缩的DP题目


1878 Get Biggest Three Rhombus Sums in a Grid

题意:

此题强烈建议去看原题,原题里的图给出了很好的解释。

给你一个二维数组,找出所有的四角形和里最大的三个 unique,如果没有三个,则返回全部。什么是四角形?!

0 1 0  1 0 1 0 1 0

0 0 1 0 00 1 0 1 01 0 0 0.10 1 0 1 00 0 1 0 0

为了方便以下的思路解释,我们称以下的斜线分别为左斜线和右斜线0 0 10 1 0  (左斜线)1 0 0

1 0 00 1 0 (右斜线)0 0 1

思路:

  1. 我们首先对每个数字进行长度为 1,2,3 . . . 的左右斜线和进行储存
  2. 我们用 dpicnt 表示以 (i , j)为起点长度为cnt 的左斜线和。dpicnt 表示以 (i , j)为起点长度为cnt 的右斜线和
  3. 如果当前位置是  (i , j),我们想求以 (i , j) 为起点长度为 cnt 的四角形和。sum = dpicnt + dpicnt + dpi+cntcnt + dpi+cntcnt - mati - mati+2*cnt - mati+cnt - mati+cnt。公式看起来有点复杂,代码里的comment图会进行更详细解释。 简单点来说,就是把四角形的四条线加起来
  4. 当然,要注意check 看看是否outbound

代码:

classSolution {

   publicint[] getBiggestThree(int[][] mat) {

       intn=mat.length,m=mat[0].length;

       intdp[][][][]=newint[n][m][Math.max(n,m)+1][2];

       TreeSet<Integer>tree=newTreeSet<>();

       

       for(inti=0;i<n;i++){

           for(intj=0;j<m;j++){

               intr=i,c=j;

               intsum=0;

               intcnt=0;

               while(r<n&&c>=0){

                   sum+=mat[r++][c--];

                   dp[i][j][cnt++][0]=sum;

               }

               

               sum=0;

               r=i;c=j;

               cnt=0;

               while(r<n&&c<m){

                   sum+=mat[r++][c++];

                   dp[i][j][cnt++][1]=sum;

               }

               

           }

       }

       

       

       for(inti=0;i<n;i++){

           for(intj=0;j<m;j++){

               tree.add(mat[i][j]);//单个需要进行特殊处理

               for(intcnt=1;cnt<=n;cnt++){

                   if(i+cnt*2>=n||j-cnt<0||j+cnt>=m){//检查outbound

                       break;

                   }

                   intsum=dp[i][j][cnt][0] +dp[i][j][cnt][1] +dp[i+cnt][j-cnt][cnt][1] +dp[i+cnt][j+cnt][cnt][0] -mat[i][j] -mat[i+2*cnt][j] -mat[i+cnt][j-cnt] -mat[i+cnt][j+cnt];

                   tree.add(sum);

               }

           }

       }

       

         

       //转换回array

       List<Integer>list=newArrayList<>(tree);

       Collections.reverse(list);

       intres[]=newint[Math.min(3,list.size())];

       for(inti=0;i<res.length;i++){

           res[i]=list.get(i);

       }

       returnres;

   }

}

//假设以下数组

//0 2 0

//3 0 5     如果我们求长度是1的四角新,这里的例子由 (2 3 4 5)组成,它的和是 14

//0 4 0     dp[0][1][1][0] = 2+3 = 5   dp[0][1][1][1] = 2+5 = 7

//          dp[1][0][1][1] = 3+4 = 7   dp[1][2][1][0] = 5+4 = 9

//          由于四个角被重复计算,我们需要最后把他们减去

//          (2+3) + (3+4) + (2+5) + (5 + 4) - (2 + 3 + 4 + 5) = 28 - 14 = 14

//简单来说,就是把四角形的四条线加起来

空间复杂度和时间复杂度:

  • 时间复杂度:O(nm min(n,m))
  • 空间复杂度:O(nm min(n,m))
目录
相关文章
|
存储 弹性计算 运维
阿里云经济型e系列云服务器测评,专为中小应用打造
2023年9月,阿里云推出了一款全新云服务器实例,经济型e实例,基于“飞天+CIPU”黄金技术架构设计,可轻松满足网站建设、开发测试和小型应用构建等场景需求,使用成本最低可降至每天0.5元,告别复杂的选型和高昂的成本,进一步降低了学生群体、个人开发者和小微企业的上云门槛。
2689 0
阿里云经济型e系列云服务器测评,专为中小应用打造
|
数据安全/隐私保护 索引
基于 SpringBoot+Vue 的网上图书商城管理系统(附源码,教程)下
基于 SpringBoot+Vue 的网上图书商城管理系统(附源码,教程)
|
SQL 运维 关系型数据库
一款 SQL 自动检查神器,再也不用担心 SQL 出错了,自动补全、回滚等功能大全
一款 SQL 自动检查神器,再也不用担心 SQL 出错了,自动补全、回滚等功能大全
319 0
|
NoSQL 测试技术 定位技术
【MongoDB 专栏】MongoDB 的地理空间索引与位置查询
【5月更文挑战第10天】MongoDB 支持地理空间数据处理,提供2dsphere(球面)和2d(平面)索引,适用于地图导航、物流、社交网络等领域。通过创建索引,可加速位置查询,如查询范围、最近邻及地理空间聚合。案例包括地图应用、物流追踪和社交网络。注意数据准确性、索引优化和性能测试,以发挥其在地理空间处理中的潜力。学习此功能,为应用开发解锁更多可能性!
456 2
【MongoDB 专栏】MongoDB 的地理空间索引与位置查询
|
11月前
|
开发工具
java.lang.unsatisfiedlinkerror解决方法
java.lang.unsatisfiedlinkerror解决方法
1163 1
|
9月前
|
安全 网络安全 数据安全/隐私保护
Cisco-网络地址转换动态NAT
Cisco-网络地址转换动态NAT
128 1
|
负载均衡 关系型数据库 数据管理
关系型数据库的横向扩展
【5月更文挑战第2天】关系型数据库的横向扩展
339 6
关系型数据库的横向扩展
|
存储 编译器 Linux
完全理解ARM启动流程:Uboot-Kernel
完全理解ARM启动流程:Uboot-Kernel
1092 0
|
数据可视化 关系型数据库 MySQL
使用IDEA连接Mysql数据库
使用IDEA连接Mysql数据库,提前在可视化工具中建好表
853 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问