前言
本文属于特定的六道题目题解和调试代码。
1 ✔ [72]编辑距离 Hard 2023-03-07 115
2 ✔ [232]用栈实现队列 Easy 2023-02-23 115
3 ✔ [704]二分查找 Easy 2023-02-06 115
4 ✔ [4]寻找两个正序数组的中位数 Hard 2023-03-04 114
5 ✔ [199]二叉树的右视图 Medium 2022-11-30 111
6 ✔ [56]合并区间 Medium 2023-02-03 107
正所谓磨刀不误砍柴功。下面我做这几篇文档对于涉及的题型或者数据结构的分析都很有帮助，贴出来仅供参考。
如何调试递归程序，有何技巧？
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
1 ✔ [72]编辑距离 Hard 2023-03-07 115
//给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
//
// 你可以对一个单词进行如下三种操作：
//
//
// 插入一个字符
// 删除一个字符
// 替换一个字符
//
//
//
//
// 示例 1：
//
//
//输入：word1 = "horse", word2 = "ros"
//输出：3
//解释：
//horse -> rorse (将 'h' 替换为 'r')
//rorse -> rose (删除 'r')
//rose -> ros (删除 'e')
//
//
// 示例 2：
//
//
//输入：word1 = "intention", word2 = "execution"
//输出：5
//解释：
//intention -> inention (删除 't')
//inention -> enention (将 'i' 替换为 'e')
//enention -> exention (将 'n' 替换为 'x')
//exention -> exection (将 'n' 替换为 'c')
//exection -> execution (插入 'u')
//
//
//
//
// 提示：
//
//
// 0 <= word1.length, word2.length <= 500
// word1 和 word2 由小写英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 2855 👎 0
本题leetcode热评：如果不是真的不会,谁会愿意当傻逼呢
困难点，无论word1和word2长度如何，每个位子都有可能增删改，到底应该先增还是先改还是先删呢？递归改如何写？
困惑点解答：
其实对word1的增和对word2的删是同一个效果，反过来也一样。
对于word1的改和对于word2的改也是等效的。
所以可以的操作变成了：
对word1 增
对word2 增
对word1 改
三种操作， 到这里对操作的可能性减少了。
先改还是先删（或者增）呢？
其实对于正确的结果，先改还是先增效果都是一样的。
到这里，再分析我们的动态规划套路：
分析原问题=》找出子问题=>找出子问题和原问题的关系=》解决子问题=》解决原问题。
这里我又发现一个规律，动态规划问题，大部分都可以画x轴y轴解决。xy轴的结果又可以通过二维数组来记录。
我觉得这个也可以加入到解决动态规划问题的思路里。看到动态规划，就想上面两条。
这道题目的子问题就是无限的减少字母的数量，当word1和word2都是零个字母的时候，就需要0次
当word1字符数量为0时，word2字符数量为多少，就需要多少次。
对应了二维数组中的坐标。
则dp[i][j] 的值就等于 在dp[i-1][j] 和dp[i][j-1]和dp[i-1][j-1]中选一个最下的结果+1。
如果这两个坐标对应的字母相等，那么从dp[i-1][j-1]变换过来就不需要添加值了。
如下在dp[i-1][j-1] -1。
自测代码
public class P72_EditDistance{
public static void main(String[] args) {
//测试代码
Solution solution = new P72_EditDistance().new Solution();
System.out.println(solution.minDistance("horse", "ros"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int minDistance(String word1, String word2) {
/*困难点，无论word1和word2长度如何，每个位子都有可能增删改，到底应该先增还是先改还是先删呢？递归改如何写？*/
/*困惑点解答：
其实对word1的增和对word2的删是同一个效果，反过来也一样。
对于word1的改和对于word2的改也是等效的。
所以可以的操作变成了：
对word1 增
对word2 增
对word1 改
* 三种操作， 到这里对操作的可能性减少了。
先改还是先删（或者增）呢？
其实对于正确的结果，先改还是先增效果都是一样的。
到这里，再分析我们的动态规划套路：
分析原问题=》找出子问题=>找出子问题和原问题的关系=》解决子问题=》解决原问题。
这里我又发现一个规律，动态规划问题，大部分都可以画x轴y轴解决。xy轴的结果又可以通过二维数组来记录。
我觉得这个也可以加入到解决动态规划问题的思路里。看到动态规划，就想上面两条。
*
* */
int[][] dp = new int[word1.length()+1][word2.length()+1];
for (int i = 0; i < word1.length()+1; i++) {
for (int j = 0; j < word2.length()+1; j++) {
if (i == 0 ){
dp[i][j] = j;
continue;
}
if (j == 0) {
dp[i][j] = i;
continue;
}
int min = Math.min(dp[i - 1][j], dp[i][j - 1]);
if (word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = Math.min(min,dp[i-1][j-1] -1)+1;
}else {
dp[i][j] = Math.min(min,dp[i-1][j-1] )+1;
}
if (i== word1.length() && j == word2.length()) {
return dp[i][j];
}
}
}
return dp[word1.length()][word2.length()];
}
public int min(String word1,int left,String word2,int right){
/*怎么判断最优路径*/
char[] charsWord1 = word1.toCharArray();
char[] charsWord2 = word2.toCharArray();
int lenWord1 = word1.length();
int lenWord2 = word2.length();
if (word1.equals(word2)) {
return 0;
}
if (left > right) {
}
char temp = charsWord1[left];
charsWord1[left] = charsWord2[right];
min(word1,left+1,word2,right+1);
charsWord1[left] = temp;
return 0;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int minDistance(String word1, String word2) {
/*困难点，无论word1和word2长度如何，每个位子都有可能增删改，到底应该先增还是先改还是先删呢？递归改如何写？*/
/*困惑点解答：
其实对word1的增和对word2的删是同一个效果，反过来也一样。
对于word1的改和对于word2的改也是等效的。
所以可以的操作变成了：
对word1 增
对word2 增
对word1 改
* 三种操作， 到这里对操作的可能性减少了。
先改还是先删（或者增）呢？
其实对于正确的结果，先改还是先增效果都是一样的。
到这里，再分析我们的动态规划套路：
分析原问题=》找出子问题=>找出子问题和原问题的关系=》解决子问题=》解决原问题。
这里我又发现一个规律，动态规划问题，大部分都可以画x轴y轴解决。xy轴的结果又可以通过二维数组来记录。
我觉得这个也可以加入到解决动态规划问题的思路里。看到动态规划，就想上面两条。
*
* */
int[][] dp = new int[word1.length()+1][word2.length()+1];
for (int i = 0; i < word1.length()+1; i++) {
for (int j = 0; j < word2.length()+1; j++) {
if (i == 0 ){
dp[i][j] = j;
continue;
}
if (j == 0) {
dp[i][j] = i;
continue;
}
int min = Math.min(dp[i - 1][j], dp[i][j - 1]);
if (word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = Math.min(min,dp[i-1][j-1] -1)+1;
}else {
dp[i][j] = Math.min(min,dp[i-1][j-1] )+1;
}
if (i== word1.length() && j == word2.length()) {
return dp[i][j];
}
}
}
return dp[word1.length()][word2.length()];
}
public int min(String word1,int left,String word2,int right){
/*怎么判断最优路径*/
char[] charsWord1 = word1.toCharArray();
char[] charsWord2 = word2.toCharArray();
int lenWord1 = word1.length();
int lenWord2 = word2.length();
if (word1.equals(word2)) {
return 0;
}
if (left > right) {
}
char temp = charsWord1[left];
charsWord1[left] = charsWord2[right];
min(word1,left+1,word2,right+1);
charsWord1[left] = temp;
return 0;
}
}
2 ✔ [232]用栈实现队列 Easy 2023-02-23 115
//请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//
// 实现 MyQueue 类：
//
//
// void push(int x) 将元素 x 推到队列的末尾
// int pop() 从队列的开头移除并返回元素
// int peek() 返回队列开头的元素
// boolean empty() 如果队列为空，返回 true ；否则，返回 false
//
//
// 说明：
//
//
// 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法
//的。
// 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
//
//
//
//
// 示例 1：
//
//
//输入：
//["MyQueue", "push", "push", "peek", "pop", "empty"]
//[[], [1], [2], [], [], []]
//输出：
//[null, null, null, 1, 1, false]
//
//解释：
//MyQueue myQueue = new MyQueue();
//myQueue.push(1); // queue is: [1]
//myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
//myQueue.peek(); // return 1
//myQueue.pop(); // return 1, queue is [2]
//myQueue.empty(); // return false
//
//
//
//
//
//
//
// 提示：
//
//
// 1 <= x <= 9
// 最多调用 100 次 push、pop、peek 和 empty
// 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
//
//
//
//
// 进阶：
//
//
// 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
//
//
// Related Topics 栈 设计 队列 👍 865 👎 0
细心
做这道题目的时候发现自己确实很容易漏掉一些可能，不够严谨，比如在pop方法中
if (!stackResver.empty()) {
top = stackResver.peek();
}
导致有些用例没有通过，只考虑了不为空时，将top赋值，那为空的时候呢？
if (!stackResver.empty()) {
top = stackResver.peek();
}else{
top = null;
}
做题尚且有答案，实际编程中可能就是线上事故了，感觉自己蛮严谨的，还是不够！！
另外发现大部分不细心的点都是出在判断语句上，与大家共勉吧！
仔细再仔细，设计到判断语句，就要谨慎，仔细再仔细
自测代码
public class P232_ImplementQueueUsingStacks{
public static void main(String[] args) {
//测试代码
MyQueue solution = new P232_ImplementQueueUsingStacks().new MyQueue();
solution.push(1);
// solution.push(2);
// System.out.println(solution.peek());
System.out.println(solution.pop());
solution.push(2);
System.out.println(solution.peek());
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class MyQueue {
Stack<Integer> stack;
Stack<Integer> stackResver;
Integer top = null;
public MyQueue() {
stack = new Stack<Integer>();
stackResver = new Stack<Integer>();
}
public void push(int x) {
stack.push(x);
if (top == null) {
top = x;
}
}
public int pop() {
while (!stack.empty()) {
stackResver.push(stack.pop());
}
int res = stackResver.pop();
if (!stackResver.empty()) {
top = stackResver.peek();
}else{
top = null;
}
while (!stackResver.empty()) {
stack.push(stackResver.pop());
}
return res;
}
public int peek() {
return top;
}
public boolean empty() {
return stack.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class MyQueue {
Stack<Integer> stack;
Stack<Integer> stackResver;
Integer top = null;
public MyQueue() {
stack = new Stack<Integer>();
stackResver = new Stack<Integer>();
}
public void push(int x) {
stack.push(x);
if (top == null) {
top = x;
}
}
public int pop() {
while (!stack.empty()) {
stackResver.push(stack.pop());
}
int res = stackResver.pop();
if (!stackResver.empty()) {
top = stackResver.peek();
}else{
top = null;
}
while (!stackResver.empty()) {
stack.push(stackResver.pop());
}
return res;
}
public int peek() {
return top;
}
public boolean empty() {
return stack.empty();
}
}
3 ✔ [704]二分查找 Easy 2023-02-06 115
//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否
//则返回 -1。
//
// 示例 1:
//
// 输入: nums = [-1,0,3,5,9,12], target = 9
//输出: 4
//解释: 9 出现在 nums 中并且下标为 4
//
//
// 示例 2:
//
// 输入: nums = [-1,0,3,5,9,12], target = 2
//输出: -1
//解释: 2 不存在 nums 中因此返回 -1
//
//
//
//
// 提示：
//
//
// 你可以假设 nums 中的所有元素是不重复的。
// n 将在 [1, 10000]之间。
// nums 的每个元素都将在 [-9999, 9999]之间。
//
//
// Related Topics 数组 二分查找 👍 1236 👎 0
自测代码
public class P704_BinarySearch{
public static void main(String[] args) {
//测试代码
Solution solution = new P704_BinarySearch().new Solution();
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int search(int[] nums, int target) {
int res = -1;
int l = 0 ;
int r = nums.length-1;
while (l <= r) {
int temp = (r+l)/2;
if (nums[temp] == target){
return temp;
}
if (nums[temp] > target){
r = temp-1;
continue;
}
if (nums[temp] < target){
l = temp+1;
continue;
}
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int search(int[] nums, int target) {
int res = -1;
int l = 0 ;
int r = nums.length-1;
while (l <= r) {
int temp = (r+l)/2;
if (nums[temp] == target){
return temp;
}
if (nums[temp] > target){
r = temp-1;
continue;
}
if (nums[temp] < target){
l = temp+1;
continue;
}
}
return res;
}
}
4 ✔ [4]寻找两个正序数组的中位数 Hard 2023-03-04 114
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
// 算法的时间复杂度应该为 O(log (m+n)) 。
//
//
//
// 示例 1：
//
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
//
//
//
//
// 提示：
//
//
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -10⁶ <= nums1[i], nums2[i] <= 10⁶
//
//
// Related Topics 数组 二分查找 分治 👍 6382 👎 0
不考虑时间复杂度 O(log (m+n)) ，很容易想到一个方法：
两个通过总长度找到中位数，然后两个指针分别从两个数组从左往右对比小的加1，就可以找到中位数。
O(log (m+n)) 其实就应该想到用二分法，我想到的是从一个数组A中取中位数，然后判断这个数在另一个数组B中的位置，通过位置偏左还是偏右，再取A中位数后面或者前面的数，但是要控制的变量太多，后来看了答案，感觉如果硬是走下去应该也可以解决。
答案思路是，假如中位数是k，那么可以一次性去掉k/2个数。为什么不一次性去掉k个数呢，假如两个数组长度相等，那么k就是两个数组的最后一位比较，这时，最后两位的大小无法确定出可以排除那些值，
但是如果去掉k/2个数时，合并之后，前k/2个数一定都是再k的左边，我们只需要比较两个数组k/2的位置数的大小，然后小的那一块，一定不会在k的右边 ，可以放心去掉。去掉之后，中位数也相应的减少。
可以理解为： 整个有序数组被分成了两份，这两份又是有序的，
中位数藏在这两份中间，
因为是中位数，那么中位数 藏的位置
极端情况 要么在两个数组的中间，要么再一个数组的开头或者结尾，如果再一个数组的开头，那么这个数组的1/2一定比另一个的1/2小，就可以排除掉。 如果在开头，另一个数组的二分之一也一定比这个小可以排除。如果在中间那么也一定不在中间值小的那一块，可以排除掉。
自测代码
public class P4_MedianOfTwoSortedArrays {
public static void main(String[] args) {
//测试代码
Solution solution = new P4_MedianOfTwoSortedArrays().new Solution();
solution.findMedianSortedArrays(ArrayUtil.StrToIntArray("[1,2]"),ArrayUtil.StrToIntArray("[3,4]"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
/*秒： 如果是奇数，mid和mid2相等，如果是偶数，mid和mid2正好是中位数*/
int mid = (len1 + len2 +1) / 2;
int mid2 = (len1 + len2 +2) / 2;
int res1 = find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, mid);
int res2 = find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, mid2);
return (res1 + res2) * 0.5 ;
}
public int find(int[] nums1, int left1, int right1, int[] nums2, int left2, int right2, int mid) {
int len1 = right1 - left1 + 1;
int len2 = right2 - left2 + 1;
if (len1 > len2) {
return find(nums2, left2, right2, nums1, left1, right1, mid);
}
if (len1 <= 0) {
return nums2[left2 + mid - 1];
}
if (mid == 1) {
return Math.min(nums1[left1], nums2[left2]);
}
int tmpe = mid / 2 ;
len1 = Math.min(len1, tmpe);
len2 = Math.min(len2, tmpe);
if (nums1[left1 + len1-1] > nums2[left2 + len2-1]) {
return find(nums1, left1, right1, nums2, left2+len2, right2, mid-len2);
} else {
return find(nums1, left1+len1, right1, nums2, left2, right2, mid-len1);
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
/*秒： 如果是奇数，mid和mid2相等，如果是偶数，mid和mid2正好是中位数*/
int mid = (len1 + len2 +1) / 2;
int mid2 = (len1 + len2 +2) / 2;
int res1 = find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, mid);
int res2 = find(nums1, 0, len1 - 1, nums2, 0, len2 - 1, mid2);
return (res1 + res2) * 0.5 ;
}
public int find(int[] nums1, int left1, int right1, int[] nums2, int left2, int right2, int mid) {
int len1 = right1 - left1 + 1;
int len2 = right2 - left2 + 1;
if (len1 > len2) {
return find(nums2, left2, right2, nums1, left1, right1, mid);
}
if (len1 <= 0) {
return nums2[left2 + mid - 1];
}
if (mid == 1) {
return Math.min(nums1[left1], nums2[left2]);
}
int tmpe = mid / 2 ;
len1 = Math.min(len1, tmpe);
len2 = Math.min(len2, tmpe);
if (nums1[left1 + len1-1] > nums2[left2 + len2-1]) {
return find(nums1, left1, right1, nums2, left2+len2, right2, mid-len2);
} else {
return find(nums1, left1+len1, right1, nums2, left2, right2, mid-len1);
}
}
}
5 ✔ [199]二叉树的右视图 Medium 2022-11-30 111
//给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
//
//
//
// 示例 1:
//
//
//
//
//输入: [1,2,3,null,5,null,4]
//输出: [1,3,4]
//
//
// 示例 2:
//
//
//输入: [1,null,3]
//输出: [1,3]
//
//
// 示例 3:
//
//
//输入: []
//输出: []
//
//
//
//
// 提示:
//
//
// 二叉树的节点个数的范围是 [0,100]
//
// -100 <= Node.val <= 100
//
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 830 👎 0
这道题还是蛮好笑。
说一下我的解题思路，因为之前做过二叉树的题，知道每一层再填满的情况下，都是2的n次方-2。
所以我就想把它变成一个数组，然后直接取这些位置的值。
变成数组的话需要层级遍历，另外我也觉得可以将对二叉树的层级遍历放到我对二叉树操作的工具类里。
然后忽然想到前两天刚做了一个二叉树的层序遍历题：leetCode热题10-15 解题代码，思路
这篇文章中的第二题。对！ 没错！ 层序遍历也是一道题。
然后我将这到题打开发现它还将每层分了不同的list里，我还在想需要合并时，忽然想到，干嘛不直接取最后一个值呢？
于是就解决了哈哈。
反过来再一想，算是层序遍历的变种题啦。
自测代码
public class P199_BinaryTreeRightSideView {
public static void main(String[] args) {
//测试代码
Solution solution = new P199_BinaryTreeRightSideView().new Solution();
TreeNode treeNode = new TreeNode("[1,2,3,null,5,null,4,3,null,5,null,4]");
TreeNode.TreeNodeShow(treeNode);
solution.rightSideView(new TreeNode("[1,2,3,null,5,null,4]"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null){
queue.add(root);
}
if (!queue.isEmpty()) {
do {
queue = checkLevel(queue, res);
}while (!queue.isEmpty()) ;
}
List<Integer> data = new ArrayList<>();
for (int i = 0; i < res.size(); i++) {
int i1 = res.get(i).size() - 1;
data.add(res.get(i).get(i1));
}
return data;
}
public Queue<TreeNode> checkLevel(Queue<TreeNode> queue,List<List<Integer>> data){
Queue<TreeNode> res = new ArrayDeque<>();
ArrayList<Integer> integers = new ArrayList<>();
while (!queue.isEmpty() ){
TreeNode poll = queue.poll();
if (poll == null) {
break;
}
int val = poll.val;
integers.add(val);
TreeNode left = poll.left;
if (left != null) {
res.add(left);
}
TreeNode right = poll.right;
if (right != null) {
res.add(right);
}
}
data.add(integers);
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null){
queue.add(root);
}
if (!queue.isEmpty()) {
do {
queue = checkLevel(queue, res);
}while (!queue.isEmpty()) ;
}
List<Integer> data = new ArrayList<>();
for (int i = 0; i < res.size(); i++) {
int i1 = res.get(i).size() - 1;
data.add(res.get(i).get(i1));
}
return data;
}
public Queue<TreeNode> checkLevel(Queue<TreeNode> queue,List<List<Integer>> data){
Queue<TreeNode> res = new ArrayDeque<>();
ArrayList<Integer> integers = new ArrayList<>();
while (!queue.isEmpty() ){
TreeNode poll = queue.poll();
if (poll == null) {
break;
}
int val = poll.val;
integers.add(val);
TreeNode left = poll.left;
if (left != null) {
res.add(left);
}
TreeNode right = poll.right;
if (right != null) {
res.add(right);
}
}
data.add(integers);
return res;
}
}
6 ✔ [56]合并区间 Medium 2023-02-03 107
//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
//回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
//
//
//
// 示例 1：
//
//
//输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出：[[1,6],[8,10],[15,18]]
//解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
//
//
// 示例 2：
//
//
//输入：intervals = [[1,4],[4,5]]
//输出：[[1,5]]
//解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
//
//
//
// 提示：
//
//
// 1 <= intervals.length <= 10⁴
// intervals[i].length == 2
// 0 <= starti <= endi <= 10⁴
//
//
// Related Topics 数组 排序 👍 1844 👎 0
解题时没有想到先排序，导致，对list操作复杂，排序之后可以只操作list最后一个。
另外 排序方法
Array.sort(int[] , new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] -o2[0];
}
自定义二维数组排序。
o1[0]-o2[0] 表示用数组的第一位升序排序，反过来就是降序。
o1[1]-o2[1] 表示用数组的第二位升序排序，反过来就是降序。
自测代码
public class P56_MergeIntervals{
public static void main(String[] args) {
//测试代码
Solution solution = new P56_MergeIntervals().new Solution();
Integer[][] integers = ArrayUtil.StrToIntegerArray("[[2,3],[4,5],[6,7],[8,9],[1,10]]");
int[][] merge = solution.merge(integers);
System.out.println(ArrayUtil.IntToStrArray(merge));
/*困惑点：使用ArrayList来存储每一个值的范围，通过for循环来对比每一个值，对比完成之后，再放回去，
这个时候list已经被改变，继续循环会报ConcurrentModificationException错误.
解答：上面问题困难点在于，需要对list进行增删改查，混在一起就很麻烦，
下面的解题思路，先通过排序，这样只需要对list最后一位进行增和改就可以。
*/
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null) {
return null;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] -o2[0];
}
});
ArrayList<int[]> res = new ArrayList<>();
int len = intervals.length;
for (int i = 0; i < len; i++) {
Integer l = intervals[i][0];
Integer r= intervals[i][1];
if (res.size() == 0 || res.get(res.size() -1 )[1] < l) {
res.add(new int[]{l,r});
}else {
res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1],r);
}
}
return res.toArray(new int[res.size()][]);
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null) {
return null;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] -o2[0];
}
});
ArrayList<int[]> res = new ArrayList<>();
int len = intervals.length;
for (int i = 0; i < len; i++) {
Integer l = intervals[i][0];
Integer r= intervals[i][1];
if (res.size() == 0 || res.get(res.size() -1 )[1] < l) {
res.add(new int[]{l,r});
}else {
res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1],r);
}
}
return res.toArray(new int[res.size()][]);
}
}
发表于 2023-4-4 09:35
