LeetCode Weekly Contest 238

前言

参加 Leetcode 竞赛是我在刷题三阶段的方法论中最后一阶段用的性价比非常高的方法，在规定的时间内解决一定量的题目，这和真实的OA (Online Assessment) 或者 Onsite 面试是一样的，可以把它当作一个很好的 Mock 练习机会。

所以每周抽点时间去练习和学习新的题目对于个人的编程能力与问题解决能力都有很大的帮助，当你有碰到做不出的题目的时候，你能知道自己的弱项在哪里，然后可以根据这进行加强和练习，比赛是一面给自己的镜子。

那么从这周开始，争取每周末都会给出大家本周比赛的一些讲解和点评，但因为比赛结束时已经是美东晚上 12 点，所以文章只能等到第二天早上再写，而且排版等细节可能不会那么完美，希望大家多多担待，重点是文章内容。

今天这篇文章是对 LeetCode 第238场周赛的简单讲解和评论，包括对Leetcode 周赛 238的每一题的题解，代码，难度分析，题目类型，以及一些个人对这题的看法等，希望对大家有所帮助。

💡注意 ： 题解并不一定都是最优解（代码以pass 了 LeetCode 的 Oline Judge 为准），文章初衷是给大家提供一定的想法和问题的解决方案，也欢迎大家在评论区与我交流。

1837. Sum of Digits in Base K
      
1838. Frequency of the Most Frequent Element
      
1839. Longest Substring Of All Vowels in Order
      
1840. Maximum Building Height
      

本场比赛还是有一点难度的。全AC 的不到400人。

1837. 一道简单的暴力题，会编程的人基本都要会的入门题目。1838. 这是一道 滑动窗口 题， 但是不太明显，需要经过一定的思考才能发现可以使用滑动窗口。

1839. 一道简单的双指针题目，但需要进行一些简单的 pre-processing。

1840. 不少英雄在此题坠落，这题包含了贪心思想和一定的数学，不太好想。

💡吐槽 ： LeetCode 都快2000题了，难度也明显比以前有所提升，希望这些算法系列的文章能帮助到大家

1837 Sum of Digits in Base K

题意：

给你两个数字 n 和 k，n是10进制的数字，问你如果把这数字转成k进制的话，转换后的数字每个数位的和是多少n = 34, k = 6, 这里把 34 转换成6进制的话是 54（6），他每个数位的和一共是9注：因为这里k<=10 的关系，不用担心会有字母出现。（10进制以上需要用到字母）

思路：

1. 可以简单的进行暴力，Java 的 library 提供base 相互转换的方法，我们可以直接转换然后把转换后的每个数位加起来即可。对于每一个digit，也可以直接的把数字转成String 来快速求。
   
2. 当然，在面试中如果不能使用 library 那我们就要手写转换的方法了，求每一个数位也可以直接 %10 就行，这里我就图方便了嘻嘻。
   

💡代码：

classSolution {

 publicintsumBase(intn, intk) {

   Strings=convert(n+"", 10, k);

   returnget(s);

 }

 publicStringconvert(Stringstr, intfromBase, inttoBase) {//用库直接转换

   returnInteger.toString(Integer.parseInt(str, fromBase), toBase);

 }

 publicintget(Strings) {//求和

   intsum=0;

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

     sum+=s.charAt(i) -'0';

   }

   returnsum;

 }

}

空间复杂度和时间复杂度：

• 时间复杂度：max(O(log n),O(length(n)))
  
• 空间复杂度：O(length(n)) (为了方便把数字换成String 了)
  

1838 Frequency of the Most Frequent Element

题意：

给你一个数组和一个数字k，你可以对每一个数进行增加的操作，但增加的总值不能超过k，问最多能使多少个数字一样nums = [1,2,4], k = 5 这里如果把1增加3，2增加2的话会使得最终的数组成为 [4,4,4],最多能使三个数字一样

###

思路：

1. 我们可以知道最终最多的那个数字肯定是在数组里面的
   
2. 那我们先对数组排序一下，假设我们最终最多的那个数字是 A[i]，那么我们只可以把比它小的数字变成A[i]，因为我们只可以进行增加操作但不能进行减少操作
   
3. 我们这里保持一个滑动窗口，我们会把滑动窗口里面的所有数字变成A[i]
   
4. 如果我们把滑动窗口的数都变成A[i]，我们需要多少操作呢？我们需要 A[i] * sizeOf(Window) - Sum(Window) 的操作
   
5. 如果需要的操作大于 k 的时候，那我们这个窗口肯定是不能变成更大的数字的啦（因为我们的数组是排序好的，我们一个个去试的时候是从小到大），这时候我们就可以把Window的最小的数字给移除掉，因为越小的数字需要越多的操作去变成 A[i]
   

💡代码：

classSolution {

 publicintmaxFrequency(int[] A, intk) {

   Arrays.sort(A);

   intres=0;

   longsum=0;

   for (inti=0, j=0; i<A.length; i++) {

     sum+=A[i];

     

     //如果不能把滑动窗口里所有的数变成 A[i]，我们就移除最小的数字并且update 滑动窗口的sum

     while (sum+k< (A[i] +0l) * (i-j+1)) {

       sum-=A[j++];

     }

     

     //滑动窗口的size : j - i + 1

     //出了while loop 后滑动窗口是好的，可以把里面所有的元素变成A[i]

     

     res=Math.max(res, i-j+1);

   }

   returnres;

 }

}

空间复杂度和时间复杂度：

• 时间复杂度：O(nlogn)，排序
  
• 空间复杂度：O(1)
  

1839 Longest Substring Of All Vowels in Order

题意：

给你一个字串符s，要你找出其最长的漂亮的子字串符(subString)。什么是漂亮的字串符？这个字串符只能有 a e i o u，并且缺一不可，每个的数量不限。并且，a的位置在e之前，e在i之前，i在o之前，o在u之前aaaaaaeiiiioou ： 美，和齐姐一般aaaeeeooo ： 丑aeoiu ： 丑如果给的 s = “aeiaaioaaaaeiiiiouuuooaauuaeiu”， 他的最长美丽子字串符是 aaaaeiiiiouuu， 长度13

思路：

1. 我们可以先把String 改成array 然后再做一点提前处理，我们把 a 改成0，e改成1，i改成2，e改成3 和 u改成5，其他的全用 -1
   
2. 如果我们遇到 0 (也就是a)，我们在0这里开始找一个最长的子数组，这个子数组的condition是相邻的两个数字的差必须大于或等于0并且不能超过1
   
3. 当我们走到这个子数组的终点之后我们还要看看最后的数字是不是4 (u) 。因为其它数字都是-1的关系不会对子数组造成影响
   

💡代码：

classSolution {

   publicintlongestBeautifulSubstring(Strings) {

       Map<Character,Integer>f=newHashMap<>();//用map 储存转换的 pair

       f.put('a',0);

       f.put('e',1);

       f.put('i',2);

       f.put('o',3);

       f.put('u',4);

       

       intA[]=newint[s.length()];

       Arrays.fill(A,-1);

       

       for(inti=0;i<s.length();i++){ //转化成一个数字数组,方便

           if(f.containsKey(s.charAt(i))){

               A[i]=f.get(s.charAt(i));

           }

       }

       

       

       intres=0;

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

           if(A[i]==0){//是a，也就是我们子字符的开始

               intj=i+1;

               while(j<A.length&&A[j]-A[j-1]>=0&&A[j]-A[j-1]<=1){

                   j++;

               }

               

               //如果子字符最后一个是u的话，那整个子字符就是好的，我们update我们的最长结果

               if(A[j-1]==4){

                   res=Math.max(res,j-i);

               }

               i=j-1;

           }

       }

       returnres;

   }

}

空间复杂度和时间复杂度：

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)
  

1840 Maximum Building Height

题意：

此题强烈建议大家去官网看一下原题，官网提供的图片能够更好的诠释题意。

现在有 1 - n 的土地，你要在这这些土地里进行盖楼。每两块土地之间的距离不能大于1。并且还给了以下的条件限定：

1. 位置1里不能盖楼 (高度为0)
   
2. 再给你一个restrictions 数组，restrictions[i] = [id, maxHeighti]， 表示在 id 这块土地你能建立的楼最高只能是maxHeighti
   

问，所有楼中最高的高度是多少?例子：n = 5, restrictions = [[2,1],[4,1]]，以下是一个最优建筑方式：[0,1,2,1,2]，其所有建筑的最高是2 n = 6, restrictions = [] 以下是一个最优建筑方式：[0,1,2,3,4,5] 其所有建筑的最高是5

思路：

1. 首先这题的n特别大，我们不可能把他的所有情况都给模拟出来，但是他给的 restrictions 数组不是特别大，我们可以通过restrictions 去尝试把最优的建筑方案找出来
   
2. 首先我们对restrictions 进行一下对他们id 的排序
   
3. 每一个 restrictions 只能让你建立一个最高是 maxHeight 的房子，但这真的是你能建立的最高高度吗？显然不是，因为每两个房子之间的高度差不能超过1， 每个restriction 实际上还会被前面和后面的房子影响，所以我们要找出真正的最高是多少
   
4. 如果我们知道上一个能达到的最大高度，那么我们可以通过上一个禁止土地能达到的最高高度来求出现在这个禁止土地能达到的最大高度，这里需要左右都进行处理。这一部分直接看代码可能会更加容易懂
   
5. 当我们都计算好真正的每个禁止土地能达到的最高高度后，假设当前这块禁止土地能达到的真正最高高度是h，表示我们可以选从 [0 : h] 里选一个高度，无论选哪个高度，最终都能够建立一个合法组合 （这里读者可以想一下为什么）
   
6. 好，现在假设我们在Ai 这个禁止土地上面，我们可以选 0 - Ai 的任意一个数，无论选哪个，其他土地都有办法跟上！那么我们再假设如果最高的那个房子发生在 Ai-1 和 Ai 之间好了，所以我们最终只需要对每两个禁止土地的pair 找出能建立的最高房子就好了。
   
7. 假设这个点发生在x，他的高度是y，那么他要成立 : x-pre[0]=y-pre[1] , cur[0]-x=y-cur[1] （pre=A[i-1] ，cur=A[i]）
   
8. 式子整理 ： y = cur[0]-pre[0]+cur[1]+pre[1])/2
   
9. 为什么使用这个式子呢？我们这样想，我们想要最大，从pre -> cur 这个过程，我们对于每一块土地肯定是想建立一个更高的房子，直到不能再提升的时候，我们才进行减少。所以每两个禁止土地之间最终会是一个类似 ^ 的形状
   

💡代码：

classSolution {

 publicintmaxBuilding(intn, int[][] A) {

   intres=0;

   List<int[] >list=newArrayList<>();

   list.add(newint[] {1,0});//把第一块土地加进去

   

   for (intp[] : A) {

     list.add(p);

   }

   Collections.sort(list, (a, b) ->{

     returna[0] -b[0];

   });//对禁止的土地进行id 的排序

   //左走，计算每一个禁止土地能达到的最高高度

   for (inti=1; i<list.size(); i++) {

     intcur[] =list.get(i);

     intpre[] =list.get(i-1);

     intdis=cur[0] -pre[0];//两个禁止土地之间的距离

     if (pre[1] >=cur[1]) {

       cur[1] =Math.min(cur[1], pre[1]);

     }

     else {

       cur[1] =Math.min(cur[1], pre[1] +dis);

     }

   }

   

   //右走，计算每一个禁止土地能达到的最高高度

   for (inti=list.size() -2; i>=0; i--) {

     intcur[] =list.get(i);

     intpre[] =list.get(i+1);

     intdis=pre[0] -cur[0];//两个禁止土地之间的距离

     if (pre[1] >=cur[1]) {

       cur[1] =Math.min(cur[1], pre[1]);

     }

     else {

       cur[1] =Math.min(cur[1], pre[1] +dis);

     }

     res=Math.max(res, cur[1]);

   }

   //最后一块土地进行额外计算

   res=Math.max(res, n-list.get(list.size() -1)[0] +list.get(list.size() -1)[1]);

   // y = cur[0]-pre[0]+cur[1]+pre[1])/2

   

   for (inti=1; i<list.size(); i++) {

     intcur[] =list.get(i);

     intpre[] =list.get(i-1);

     res=Math.max(res, (cur[0] -pre[0] +cur[1] +pre[1]) /2);

   }

   returnres;

 }

}

空间复杂度和时间复杂度：

• 时间复杂度：O(nlogn)
  
• 空间复杂度：O(n)
  

碎碎念

以上就是 Leetcode 周赛 238的题解和想法了，下周是双周赛，估计只鹅

工作之后，打比赛是保持自己刷题手感的高效方法，每周只需一个半小时，仿佛调用了全身的能量去解决问题，带着这种状态进入每天的工作中，也会让我们工作更加高效。

如果你喜欢这篇文章，还想看更多关于周赛的文章，记得点赞留言告诉我哦！～