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))