LeetCode 통합 문제 요약

문제 풀이는 필기시험에서 자주 합병 문제에 부딪히는 것을 포함한다. LeetCode에서 흔히 볼 수 있는 합병 문제의 코드를 다음과 같이 요약한다. 수조 합병, 체인표 합병, 구간 합병, 정렬, 귀속 등 자주 사용하는 조작을 포함한다.
 

1. 그룹 통합에 관하여: (LeetCode 88:merge-sorted-array)

       Given two sorted integer arrays A and B, merge B into A as one sorted array.
       Note:            You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A  and B are m and n respectively.
제목: 두 개의 정렬된 정수 그룹 A와 B를 주고 B를 하나의 정렬된 그룹으로 합친다.

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int index = m+n-1;
        int i = m-1;
        int j = n-1;
        while(index>=0 && j>=0 && i>=0){
            if(A[i]<=B[j])
                A[index--]=B[j--];
            else
                A[index--]=A[i--];
        }
        if(i<0){
           while(j>=0)
                A[index--]=B[j--];
       }
        if(j<0){
            while(i>=0)
               A[index--]=A[i--];
       }
    }
}

 

2. 두 개의 질서정연한 체인 테이블의 통합: (LeetCode 21:merge-two-sorted-lists)

       Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
검지offer의 원제이기도 하며, 귀속으로 처리한다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1 ==null && l2 == null)
             return null;
         if(l1==null)
             return l2;
         if(l2 == null)
             return l1;
         if(l1.val

 

3. 여러 개의 질서정연한 체인 테이블을 합친다: (LeetCode 23:merge-k-sorted-lists)

     Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
여러 개의 질서정연한 체인표는 한 번에 합병할 수 있고 상술한 두 개의 질서정연한 체인표의 합병을 호출할 수 있다.두 개의 정렬 체인 테이블의 통합을 바탕으로 매 라운드의 복잡도 o(n), n은 총 노드 개수, T(n)= 2T(n/2)+o(n), 교체 횟수는 k이기 때문에 복잡도는 o(n*k)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
        ListNode node = new ListNode(1);
        if(lists.size()<1)
            return null;
        node = lists.get(0);
        if(lists.size()==1)
            return node;
        for(int i =1;i

병합 방법을 사용하여 두 개를 합칠 수도 있다.

// o(nlogn)
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
       if(lists==null||lists.size()==0){
           return null;
       }
       return mergeKList(lists,0,lists.size()-1);
    }
    public ListNode mergeKList(ArrayList lists,int lo,int hi){
        if (hi<=lo) return lists.get(lo);
        int mid=lo+(hi-lo)/2;
        ListNode left = mergeKList(lists,lo,mid);
        ListNode right = mergeKList(lists,mid+1,hi);
        return merge(left,right);
    }
    public ListNode merge(ListNode left,ListNode right){
        ListNode h = new ListNode(-1);
        ListNode tmp=h;
        while(left!=null&&right!=null){
            if(left.val

 

4. 구간 통합: (LeetCode 56:merge-intervals)

      Given a collection of intervals, merge all overlapping intervals.
      For example,   Given[1,3],[2,6],[8,10],[15,18],      return[1,6],[8,10],[15,18].
구간 시작 값에 따라 오름차순 정렬을 한 다음list 집합에 첫 번째 구간을 추가하고 후속 구간 값을 순서대로 비교합니다. 범위에 없으면 추가되고, 일부분을 포함하면 업데이트합니다.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList merge(ArrayList intervals) {
        ArrayList list = new  ArrayList();
        if(intervals.size()<1)
            return list;
        Collections.sort(intervals,new Comparator(){
            public int compare(Interval o1,Interval o2){
                return o1.start-o2.start;
            }
        });
        list.add(intervals.get(0));
        for(int i =1;i=intervals.get(i).start 
                 && list.get(list.size()-1).end<=intervals.get(i).end){
                list.get(list.size()-1).end = intervals.get(i).end;
            }else if(list.get(list.size()-1).end>=intervals.get(i).start 
                  && list.get(list.size()-1).end>=intervals.get(i).end){
                continue;
            }else{
                list.add(intervals.get(i));
            }
        }
        return list;
    }
}

 

5. 구간 삽입 후 병합(LeetCode: insert-interval)

      Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).  You may assume that the intervals were initially sorted according to their start times.
Example 1:         Given intervals[1,3],[6,9], insert and merge[2,5]in as[1,5],[6,9].         Given[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge[4,9]in as[1,2],[3,10],[12,16].This is because the new interval[4,9]overlaps with[3,5],[6,7],[8,10].
삽입을 하면서 업데이트를 합니다. 삽입 조건이 충족되지 않으면 기존 구간을 결과에 추가하고, 기존 구간과 중첩된 경우 삽입 구간을 합쳐서 다음 삽입을 합니다. 삽입 구간의 end 값이 구간의 시작 값보다 작을 때까지 비교를 끝내고, 마지막으로 기존 집합의 값을 결과에 삽입하여 결과를 되돌려줍니다.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

import java.util.*;
public class Solution {
    public ArrayList insert
                    (ArrayList intervals, Interval newInterval) {
        ArrayList result = new ArrayList();
        if(intervals.size()==0){
            result.add(newInterval);
            return result;
        }
        boolean flag = false;
        int i =0;
        for(;i newInterval.end){
                break;
            }else{
                newInterval.start = 
                        Math.min(intervals.get(i).start,newInterval.start);
                newInterval.end = 
                        Math.max(intervals.get(i).end,newInterval.end);
            }
        }
        result.add(newInterval);
        for(;i