56. 合并区间

以数组 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 <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List merged = new ArrayList();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  1.       Arrays.sort(intervals, new Comparator<int[]>() {<br />            @Override<br />            public int compare(int[] o1, int[] o2) {<br />                return o1[0] - o2[0];<br />            }<br />        });
  3.     List<int[]> outputs = new ArrayList<>();<br />        for (int i = 0; i < intervals.length; i++) {<br />            int[] currInterval = intervals[i];<br />            // 如果符合下面的一个条件，则直接将当前区间放入结果中<br />            //      1. 当前区间是第一个区间<br />            //      2. 当前区间和结果中最后一个区间没有重叠<br />            if (outputs.isEmpty()<br />                    || outputs.get(outputs.size() - 1)[1] < currInterval[0]) {<br />                outputs.add(currInterval);<br />            } else { // 有重叠，需要合并<br />                int newLastRight =<br />                       Math.max(outputs.get(outputs.size() - 1)[1], currInterval[1]);<br />                outputs.get(outputs.size() - 1)[1] = newLastRight;<br />            }<br />        }
  5.     return outputs.toArray(new int[outputs.size()][]);

作者：tangweiqun
链接：https://leetcode-cn.com/problems/merge-intervals/solution/shi-pin-wen-zi-xiang-xi-jiang-jie-he-bing-qu-jian-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对链表自顶向下归并排序

找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

对两个子链表分别排序。

将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。

JavaC++JavaScriptPython3GolangC
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}

  1. public ListNode sortList(ListNode head, ListNode tail) {<br />        if (head == null) {<br />            return head;<br />        }<br />        if (head.next == tail) {<br />            head.next = null;<br />            return head;<br />        }<br />        ListNode slow = head, fast = head;<br />        while (fast != tail) {<br />            slow = slow.next;<br />            fast = fast.next;<br />            if (fast != tail) {<br />                fast = fast.next;<br />            }<br />        }<br />        ListNode mid = slow;<br />        ListNode list1 = sortList(head, mid);<br />        ListNode list2 = sortList(mid, tail);<br />        ListNode sorted = merge(list1, list2);<br />        return sorted;<br />    }
  3. public ListNode  (ListNode head1, ListNode head2) {<br />        ListNode dummyHead = new ListNode(0);<br />        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;<br />        while (temp1 != null && temp2 != null) {<br />            if (temp1.val <= temp2.val) {<br />                temp.next = temp1;<br />                temp1 = temp1.next;<br />            } else {<br />                temp.next = temp2;<br />                temp2 = temp2.next;<br />            }<br />            temp = temp.next;<br />        }<br />        if (temp1 != null) {<br />            temp.next = temp1;<br />        } else if (temp2 != null) {<br />            temp.next = temp2;<br />        }<br />        return dummyHead.next;<br />    }<br />}<br /> public ListNode sortList(ListNode head) {<br />        if(head == null || head.next == null){<br />            return head;<br />        }<br />        int len = getLength(head);<br />        int[] nums = ListNode2Array(head,len);<br />        Arrays.sort(nums);<br />        ListNode newHead = new ListNode(-1);<br />        ListNode tmp = newHead;<br />        for(int i = 0;i <= len - 1;i++){<br />            newHead.val = nums[i];<br />            if(i < len - 1){<br />                newHead.next = new ListNode(-1);<br />                newHead = newHead.next;<br />            }<br />        }<br />        <br />        return tmp;<br />    }<br />    public int getLength(ListNode head){<br />        int len = 0;<br />        while(head != null){<br />            len++;<br />            head = head.next;<br />        }<br />        return len;<br />    }<br />    public int[] ListNode2Array(ListNode head,int len){<br />        int[] nums = new int[len];<br />        int i = 0;<br />        while(head != null){<br />            nums[i] = head.val;<br />            head = head.next;<br />            i++;<br />        }<br />        return nums;<br />    }<br />public ListNode sortList(ListNode head) {<br />        if (head == null) {<br />            return head;<br />        }<br />        int length = 0;<br />        ListNode node = head;<br />        while (node != null) {<br />            length++;<br />            node = node.next;<br />        }<br />        ListNode dummyHead = new ListNode(0, head);<br />        for (int subLength = 1; subLength < length; subLength <<= 1) {<br />            ListNode prev = dummyHead, curr = dummyHead.next;<br />            while (curr != null) {<br />                ListNode head1 = curr;<br />                for (int i = 1; i < subLength && curr.next != null; i++) {<br />                    curr = curr.next;<br />                }<br />                ListNode head2 = curr.next;<br />                curr.next = null;<br />                curr = head2;<br />                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {<br />                    curr = curr.next;<br />                }<br />                ListNode next = null;<br />                if (curr != null) {<br />                    next = curr.next;<br />                    curr.next = null;<br />                }<br />                ListNode merged = merge(head1, head2);<br />                prev.next = merged;<br />                while (prev.next != null) {<br />                    prev = prev.next;<br />                }<br />                curr = next;<br />            }<br />        }<br />        return dummyHead.next;<br />    }
  5. public ListNode merge(ListNode head1, ListNode head2) {<br />        ListNode dummyHead = new ListNode(0);<br />        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;<br />        while (temp1 != null && temp2 != null) {<br />            if (temp1.val <= temp2.val) {<br />                temp.next = temp1;<br />                temp1 = temp1.next;<br />            } else {<br />                temp.next = temp2;<br />                temp2 = temp2.next;<br />            }<br />            temp = temp.next;<br />        }<br />        if (temp1 != null) {<br />            temp.next = temp1;<br />        } else if (temp2 != null) {<br />            temp.next = temp2;<br />        }<br />        return dummyHead.next;<br />    }<br />

179. 最大数

给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
private class LargerNumberComparator implements Comparator {
@Override
public int compare(String a, String b) {
String order1 = a + b;
String order2 = b + a;
return order2.compareTo(order1);
}
}

  1. public String largestNumber(int[] nums) {<br />        // Get input integers as strings.<br />        String[] asStrs = new String[nums.length];<br />        for (int i = 0; i < nums.length; i++) {<br />            asStrs[i] = String.valueOf(nums[i]);<br />        }
  3.     // Sort strings according to custom comparator.<br />        Arrays.sort(asStrs, new LargerNumberComparator());
  5.     // If, after being sorted, the largest number is `0`, the entire number<br />        // is zero.<br />        if (asStrs[0].equals("0")) {<br />            return "0";<br />        }
  7.     // Build largest number from sorted array.<br />        String largestNumberStr = new String();<br />        for (String numAsStr : asStrs) {<br />            largestNumberStr += numAsStr;<br />        }
  9.     return largestNumberStr;<br />    }

349. 两个数组的交集

  1. public int[] intersection(int[] nums1, int[] nums2) {
  2.         Set<Integer> set1 = new HashSet<>(),set2 = new HashSet<>();
  3.         List<Integer> list = new ArrayList<>();
  4.         for(int i:nums1){
  5.             list.add(i);
  6.         }
  7.         for(int i:nums2){
  8.             set2.add(i);
  9.         }
  10.         list.retainAll(set2);
  11.         set1.addAll(list);
  12.         return set1.stream().mapToInt(i->i).toArray();
  13.     }

作者：LeetCode
链接：https://leetcode-cn.com/problems/largest-number/solution/zui-da-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。