极客时间算法训练营 Week03

class Solution {
    public ListNode mergeKLists(ListNode[] lists){        if(lists.length == 0)            return null;        if(lists.length == 1)            return lists[0];        if(lists.length == 2){           return mergeTwoLists(lists[0],lists[1]);        }
        int mid = lists.length/2;        ListNode[] l1 = new ListNode[mid];        for(int i = 0; i < mid; i++){            l1[i] = lists[i];        }
        ListNode[] l2 = new ListNode[lists.length-mid];        for(int i = mid,j = 0; i < lists.length; i++, j++){            l2[j] = lists[i];        }
        return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
    }      private ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) return l2;        if (l2 == null) return l1;
        ListNode head = null;        if (l1.val <= l2.val){            head = l1;            head.next = mergeTwoLists(l1.next, l2);        } else {            head = l2;            head.next = mergeTwoLists(l1, l2.next);        }        return head;    }}

class Solution {    private List<List<Integer>> res = new ArrayList<>();    private Set<String> set = new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {        // 回溯        backtrack(nums, new ArrayList<>());        return res;    }
    private void backtrack(int[] nums, List<Integer> idxList) {        // 如果所有元素都排列过        if (idxList.size() == nums.length) {            List<Integer> list = new ArrayList<>();            // 通过索引list，构建元素list            for (int index : idxList) list.add(nums[index]);                if (!set.contains(list.toString())) {                    set.add(list.toString());                    res.add(list);                }            return;        }        for (int i = 0; i < nums.length; i++) {            // 如果nums[i]已经排序过，则跳过            if (idxList.contains(i)) continue;            idxList.add(i);            backtrack(nums, idxList);            idxList.remove(idxList.size() - 1);        }    }}