微软近期高频面试题分享 + 分析（十）

最近来巨硬面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：
https://www.linkedin.com/in/andy-yongjian-deng-212977200/


注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。


往期链接：

微软近期高频面试题分享 + 分析（一）

微软近期高频面试题分享 + 分析（二）

微软近期高频面试题分享 + 分析（三）

微软近期高频面试题分享 + 分析（四）

微软近期高频面试题分享 + 分析（五）

微软近期高频面试题分享 + 分析（六）

微软近期高频面试题分享 + 分析（七）

微软近期高频面试题分享 + 分析（八）

微软近期高频面试题分享 + 分析（九）

fengmiaojing9 发表于 2021-7-16 11:23
这么好的帖子不加米怎么行啊？？？
打扰LZ了，问一下你这边的高频题也适用于DS吗？谢谢！！

适用，不同岗位出题差别不大

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

1. 
   
2. 示例 1：
   
3. 
   
4. 输入：nums = [2,3,1,1,4]
   
5. 输出：true
   
6. 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
   
7. 
   
8. 示例 2：
   
9. 
   
10. 输入：nums = [3,2,1,0,4]
    
11. 输出：false
    
12. 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
    

复制代码

柱状图中最大的矩形解题思路

1、一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形还不能确定，我们需要继续向右遍历，如下图。

2、然后看到到高度为 1 的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的。但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小 ，因为这个 1 卡在了这里 2 不能再向右边扩展了，如下图。

3、我们计算一下以 2 为高度的最大矩形的面积是 2。其实这个时候，求解这个问题的思路其实已经慢慢打开了。如果已经确定了一个柱形的高度，我们可以无视它，将它以虚框表示，如下图。

3、遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；

4、接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；

5、再接下来，遍历到高度为 2 的柱形。

发现了一件很神奇的事情，高度为 6 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。

将可以确定的柱形设置为虚线。

接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离；

确定好以后，我们将它标成虚线。

我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。
这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。
这个时候，还需要考虑的一个细节是，在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。
那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，我们其实都不能确定。
因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候 中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。
说到这里，其实我们的思路已经慢慢清晰了。
我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。
这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。
我们在缓存数据的时候，是从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完成以后我们就不再需要了，符合后进先出的特点。因此，我们需要的这个作为缓存的数据结构就是栈。
当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。

6、最后遍历到最后一个柱形，即高度为 3 的柱形。

（一次遍历完成以后。接下来考虑栈里的元素全部出栈。）
接下来我们就要依次考虑还在栈里的柱形的高度。和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为 len （这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。

7、下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。

8、下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。

9、最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。

到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

这么好的帖子不加米怎么行啊？？？
打扰LZ了，问一下你这边的高频题也适用于DS吗？谢谢！！

YankeeDoodle 发表于 2021-07-16 00:50:43
适用，不同岗位出题差别不大

哇，谢谢LZ！！！！！

mark。      

跳跃游戏  解析

典型的贪心算法
不用管怎么跳的
实时维护最远可以到达的位置
只要最远可以到达的位置大于或等于最后一个下标的位置，就说明能到达最后一个下标

1. class Solution {
   
2.     public boolean canJump(int[] nums) {
   
3.         int canGet = 0;
   
4.         for(int i = 0; i<nums.length; i++){
   
5.             if(i <= canGet){
   
6.                 canGet = Math.max(canGet, i+nums[i]);
   
7.             }else{
   
8.                 return false;
   
9.             }
   
10.             if(canGet >= nums.length-1){
    
11.                 return true;
    
12.             }
    
13.         }
    
14.         return false;
    
15.     }
    
16. }

复制代码

复杂度分析

• 时间复杂度：O(n)O(n)，其中 nn 为数组的大小。只需要访问 nums 数组一遍，共 nn 个位置。
• 空间复杂度：O(1)O(1)，不需要额外的空间开销。
  

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

1. 示例 1:
   
2. 
   
3. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
   
4. 输出: 6
   
5. 解释: 节点 2 和节点 8 的最近公共祖先是 6。
   
6. 示例 2:
   
7. 
   
8. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
   
9. 输出: 2
   
10. 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

复制代码

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。