LeetCode56.合并区间、354. 俄罗斯套娃信封问题（合并区间进阶）

╰+攻爆jí腚メ 2021-09-21 06:16 320阅读 0赞

### LeetCode56.合并区间 ###

**【题目】**

给出一个区间的集合，请合并所有重叠的区间。

**【示例】**

输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

**【思考】**

本身思路很简单，但是需要注意区间与区间的各种包含和交叉关系，最明显的一点就是区间不一定是有序的。

所以需要先排序（根据第一个区间的第一个值排序），然后第二个区间的下标0的值小于第二个区间下标1的值的区间进行合并

排序使用sort并自定义排序方式：  
这里使用的是lamda简化自定义排序方式

Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);

假设传来两个值，v1 与 v2，那么他们的先后顺序以 v1\[0\] 比 v2\[0\] 的结果为准，即：若 v1\[0\] < v2\[0\] 则 v1 < v2，若 = 则 =，若 > 则 >

举一反三：

Arrays.sort(intervals, (v1, v2) -> v1[0] == v2[0] ? v2[1] - v1[1] : v1[0] - v2[0]);

表示：传来两个值 v1 与 v2，若 \[0\] 相同，则按 \[1\] 降序；若不同则按 \[0\] 升序。

**【代码】**

package LeetCode;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class LeetCode56 { 
        public int[][] merge(int[][] intervals) { 
            if (intervals==null || intervals.length==0 || intervals[0].length==0)
                return new int[0][0];
    
            if (intervals.length==1) return intervals;
            int m,i,j;
            m = intervals.length;
            Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
            ArrayList<int[]> paths = new ArrayList<>();
    
            i = 0;
            while (i < m) { 
                int[] cur = new int[2];
                cur[0] = intervals[i][0];
                cur[1] = intervals[i][1];
                j=i+1;
                while (j<m && intervals[j][0]<=cur[1] && intervals[j][1]>=cur[0]) { 
                    cur[0] = Math.min(cur[0],intervals[j][0]);
                    cur[1] = Math.max(cur[1],intervals[j][1]);
                    j++;
                }
                paths.add(cur);
                i = j;
            }
    
            int[][] res = new int[paths.size()][2];
            for (i=0; i<paths.size(); i++) { 
                res[i] = paths.get(i);
            }
    
            return res;
        }
    
        public static void main(String[] args) { 
            int[][] a = { { 1,3},{ 2,6},{ 8,10},{ 15,18}};
            int[][] list = new LeetCode56().merge(a);
            System.out.println(list);
            System.out.println();
        }
    }

--------------------

### 354. 俄罗斯套娃信封问题 ###

**【题目】**

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组 “俄罗斯套娃” 信封（即可以把一个信封放到另一个信封里面）。

说明:  
不允许旋转信封。

**【示例】**

输入: envelopes = \[\[5,4\],\[6,4\],\[6,7\],\[2,3\]\]  
输出: 3  
解释: 最多信封的个数为 3, 组合为: \[2,3\] => \[5,4\] => \[6,7\]。

**【思考】**

这道题目其实是**最长递增子序列（Longes Increasing Subsequence，简写为 LIS）的一个变种**，因为很显然，每次合法的嵌套是大的套小的，相当于找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。

但是难点在于，标准的 LIS 算法只能在数组中寻找最长子序列，而我们的信封是由 (w, h) 这样的二维数对形式表示的，如何把 LIS 算法运用过来呢？

这道题的解法是比较巧妙的：先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20200417231438738.png]

所以这道题的关键就变成对这个二维数组排序：

**方式一：使用Arrays.sort函数并重写排序Comparator接口**

Arrays.sort(envelopes, new Comparator<int[]>() 
        { 
            public int compare(int[] a, int[] b) { 
                return a[0] == b[0] ? 
                    b[1] - a[1] : a[0] - b[0];
            }
        });

**方式二：使用lamda语法简化代码：**

// lamda实现自定义比较接口，先以v[0]升序，如果v[0]相同，在于v[1]降序
            Arrays.sort(envelopes,(v1,v2)->
                    v1[0]==v2[0]?v2[1]-v1[1]:v1[0]-v2[0]);

**【代码】**

package LeetCode;
    
    import java.util.Arrays;
    
    public class LeetCode354 { 
        public int maxEnvelopes(int[][] envelopes) { 
            if (envelopes==null || envelopes.length==0 || envelopes[0].length==0)
                return 0;
    
            int m,i,l,j;
            m = envelopes.length;
            // lamda实现自定义比较接口，先以v[0]升序，如果v[0]相同，在于v[1]降序
            Arrays.sort(envelopes,(v1,v2)->
                    v1[0]==v2[0]?v2[1]-v1[1]:v1[0]-v2[0]);
    
            int[] dp = new int[m];
    
            Arrays.fill(dp,1);
    
            for (i=1; i<m; i++) { 
                l = 0;
                for (j=0; j<i; j++) { 
                    if (envelopes[j][1]<envelopes[i][1]
                        && l < dp[j]) { 
                        l = dp[j];
                    }
                }
                dp[i] = l+1;
            }
    
            l = 0;
            for (i=0; i<m; i++) { 
                if (l<dp[i]) l = dp[i];
            }
    
            return l;
        }
    
        public static void main(String[] args) { 
            int[][] a = { { 5,4},{ 6,4},{ 6,7},{ 2,3}};
            System.out.println(new LeetCode354().maxEnvelopes(a));
        }
    
    }

--------------------

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/a358c9c0491c42b5a0eab05e8212d700.png
[20200417231438738.png]: /images/20210920/d1a9307579e744abb20de0930d5d72a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/0d64ae5cfe9b421b95d855a3d588335c.png