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

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

https://www.linkedin.com/in/andy-yongjian-deng-212977200/



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

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


往期链接：

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

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

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

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

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

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

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

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

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

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

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

反转链表  

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]


示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]

区间交际问题  解析

首先，对于两个区间，我们用[a1,a2]和[b1,b2]表示在A和B中的两个区间，那么什么情况下这两个区间没有交集呢：

只有这两种情况，写成代码的条件判断就是这样：



if b2 < a1 or a2 < b1:
    [a1,a2] 和 [b1,b2] 无交集


根据命题的否定，上面逻辑的否命题就是存在交集的条件：

# 不等号取反，or 也要变成 and
if b2 >= a1 and a2 >= b1:
    [a1,a2] 和 [b1,b2] 存在交集

就这四种情况而已。那么接下来思考，这几种情况下，交集是否有什么共同点呢？

交集区间是有规律的，果交集区间是`[c1,c2]`，那么`c1=max(a1,b1)`，`c2=min(a2,b2)`！这一点就是寻找交集的核心，我们把代码更进一步：

while i < len(A) and j < len(B):
    a1, a2 = A[i][0], A[i][1]
    b1, b2 = B[j][0], B[j][1]
    if b2 >= a1 and a2 >= b1:
        res.append([max(a1, b1), min(a2, b2)])
    # ...

最后一步，我们的指针`i`和`j`肯定要前进（递增）的，什么时候应该前进呢？

结合上图示例就很好理解了，是否前进，只取决于`a2`和`b2`的大小关系：

while i < len(A) and j < len(B):
    # ...
    if b2 < a2:
        j += 1
    else:
        i += 1


以此思路写出代码：

1. class Solution {    //经典区间问题
   
2.     public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
   
3.         List<int[]> list = new ArrayList<>();
   
4.         int i = 0, j = 0;   //i指目前在firstList的第几个元素，j指目前在secondList的第几个元素
   
5.         while(i < firstList.length && j < secondList.length){
   
6.             if(firstList[i][0] <= secondList[j][1] && firstList[i][1] >= secondList[j][0]){ //集合间存在交集
   
7.             //将交集存入list
   
8.                 list.add(new int[]{Math.max(firstList[i][0], secondList[j][0]), Math.min(firstList[i][1], secondList[j][1])});
   
9.             }
   
10.             //指针前进
    
11.             if(firstList[i][1] < secondList[j][1]){
    
12.                 i++;
    
13.             }else{
    
14.                 j++;
    
15.             }
    
16.         }
    
17.         return list.toArray(new int[list.size()][2]);
    
18.     }
    
19. }

复制代码

反转链表  解析

算法步骤：
第 1 步：先将待反转的区域反转；
第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

具体思路见代码注释：

1. class Solution {
   
2.     public ListNode reverseBetween(ListNode head, int left, int right) {
   
3.         // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
   
4.         ListNode dummyNode = new ListNode(-1);
   
5.         dummyNode.next = head;
   
6.         // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
   
7.         ListNode pre = dummyNode;
   
8.         for(int i = 1; i < left; i++){
   
9.             pre = pre.next;
   
10.         }
    
11.         //left 节点的前一个节点
    
12.         ListNode listBegin = pre;
    
13.         pre = pre.next;
    
14.         //left节点
    
15.         ListNode subBegin = pre;
    
16. 
    
17.         // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
    
18.         for(int i = left; i < right; i++){
    
19.             pre = pre.next;
    
20.         }
    
21.         //right 节点
    
22.         ListNode subEnd = pre;
    
23.         pre = pre.next;
    
24.         //right 节点后的一个节点
    
25.         ListNode listEnd = pre;
    
26. 
    
27.         // 第 3 步：切断出一个子链表（截取链表）
    
28.         listBegin.next = null;
    
29.         subEnd.next = null;
    
30. 
    
31.         // 第 4 步：反转链表的子区间
    
32.         ListNode subPre = null;
    
33.         ListNode cur = subBegin;
    
34.         while(cur != null){
    
35.             ListNode curNext = cur.next;
    
36.             cur.next = subPre;
    
37.             subPre = cur;
    
38.             cur = curNext;
    
39.         }
    
40.         
    
41.         // 第 5 步：接回到原来的链表中
    
42.         subBegin.next = listEnd;
    
43.         listBegin.next = subEnd;
    
44.         //不能返回head，因为若输入为[3,5] left = 1, right = 2，
    
45.         //head在第一个位置，反转链表后为head在第二个位置，那么返回的结果就是[3]
    
46.         //返回dummyNode.next无论如何都是第一个节点，返回结果是[5,3]
    
47.         return dummyNode.next;  
    
48.     }
    
49. }

复制代码

区间覆盖问题
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：
输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

区间覆盖问题  解析

对于这种区间问题，如果没啥头绪，首先排个序看看，比如我们按照区间的起点进行升序排序：

排序之后，两个相邻区间可能有如下三种相对位置：

按照起点升序排列，起点相同时按照终点降序排列
假设得到如下排序：

对于这三种情况：
对于情况一，找到了覆盖区间，那么让覆盖区间数+1
对于情况二和情况三，如上图，在遍历到线段2时，发现线段1与线段2相交或完全不相交则更新right=2.right，left不变仍等于1.left（left和right指遍历到此轮时的参考线段范围）。left不变是因为往后遍历时后面的线段起始点不可能比left再小了，left此时没有参考价值了，所以不用更新left。
依据几种情况，我们可以写出如下代码：

class Solution {    //区间问题
    public int removeCoveredIntervals(int[][] intervals) {
        // 按照起点升序排列，起点相同时按照终点降序排列
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] == b[0]) return b[1]-a[1];   // 起点相同时按照终点降序排列
            return a[0] - b[0]; // 按照起点升序排列
        });
        // 记录合并区间的起点和终点
        int left = intervals[0][0];
        int right = intervals[0][1];
        int res = 0;
        for(int i = 1; i < intervals.length; i++){
            // 情况一，找到覆盖区间
            if(intervals[i][0] >= left && intervals[i][1] <= right) res++;
            // 情况二，情况三 更新right
            if((right >= intervals[i][0] && right <= intervals[i][1]) || intervals[i][0] >= right) right = intervals[i][1];
        }
        return intervals.length - res;
    }
}

想到了一个先排序再贪心遍历的O(nlogn)算法。

区间交集问题

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。


示例 1：
输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2：
输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]
示例 3：
输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]
示例 4：
输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

区间覆盖那题，被2个区间覆盖的算不算吗?
比如 1-4,2-5,3-6 里      2-5  酸是被覆盖的吗？ 看你的代码，好像是不算的。对吧

qweasdzxc2019 发表于 2021-8-11 02:00
区间覆盖那题，被2个区间覆盖的算不算吗?
比如 1-4,2-5,3-6 里      2-5  酸是被覆盖的吗？ 看你的代码， ...

不算，对于区间a:[a1, a2]被b:[b1，b2]覆盖是指b1>=a1&&b2>=a2