LeetCode(82) -- 47, 55, 56

P47. Permutations II (Medium)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Discuss

public class P47_PermutationsII {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>());
        return ans;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> tempList) {
        if (tempList.size() == nums.length) {
            ans.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0  && nums[i - 1] == nums[i] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            tempList.add(nums[i]);
            backtrack(nums, used, tempList);
            used[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }
}

100%

P55. Jump Game (Medium)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

My Solution

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] memo = new boolean[nums.length];
        dfs(nums, memo, 0);
        return memo[nums.length - 1];
    }

    private void dfs(int[] nums, boolean[] memo, int start) {
        memo[start] = true;
        int l = Math.max(0, start - nums[start]);
        int r = Math.min(nums.length - 1, start + nums[start]);
        while (l <= r) {
            if (l != start && !memo[l]) {
                dfs(nums, memo, l);
            }
            l++;
        }
    }
}

13%

The Best Solution

enum Index{
    GOOD,BAD;
}

public class Solution 
{
    
    public boolean canJump(int[] nums) 
    {
        Index[] mem=new Index[nums.length];
        mem[nums.length-1]=Index.GOOD;
        int leftmost=nums.length-1;
        for(int i=nums.length-2;i>=0;i--)
        {
            if(nums[i]+i>=leftmost)
            {
                leftmost=i;
                mem[i]=Index.GOOD;
            }
            else
            {
                mem[i]=Index.BAD;
            }
        }
        return mem[0]==Index.GOOD?true:false;
        
        
    }
}

Solution

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

From right to left, find out “which is the smallest index that can reach the last position?”

P56. Merge Intervals (Medium)

Given a collection of intervals, merge all overlapping intervals.

My Solution

public class P56_MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        Node head = new Node();
        Node curr = head;
        for (int i = 0; i < intervals.length; i++) {
            Node node = new Node();
            node.l = intervals[i][0];
            node.r = intervals[i][1];
            curr.next = node;
            curr = curr.next;
        }
        curr = head.next;
        int count = 1;
        while (curr.next != null) {
            if (curr.r >= curr.next.l) {
                curr.r = Math.max(curr.r, curr.next.r);
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
                count++;
            }
        }
        curr = head.next;
        int[][] ans = new int[count][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i][0] = curr.l;
            ans[i][1] = curr.r;
            curr = curr.next;
        }
        return ans;
    }

    static class Node {
        int l;
        int r;
        Node next;
    }
}

18%

The Best Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) return intervals;
        int size = 0;
        for (int i = 0; i < intervals.length; i++) {
            int[] curr = intervals[i];
            boolean merged = false;
            for (int j = i + 1; j < intervals.length; j++) {
                int[] next = intervals[j];
                if (canMerge(curr, next)) {
                    intervals[j][0] = Math.min(curr[0], next[0]);
                    intervals[j][1] = Math.max(curr[1], next[1]);
                    intervals[i] = null;
                    merged = true;
                    break;
                }
            }
            if (!merged) {
                size += 1;
            }
        }
        int[][] ans = new int[size][2];
        int i = 0;
        for (int j = 0; j < intervals.length; j++) {
            if (intervals[j] != null) 
                ans[i++] = intervals[j];
        }
        return ans;
    }
    
    private boolean canMerge(int[] a, int[] b) {
        int left = Math.max(a[0], b[0]);
        int right = Math.min(a[1], b[1]);
        return left <= right;
    }
}

没仔细研究，有时间再看。

Solution

class Solution {
    private class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval a, Interval b) {
            return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
        }
    }

    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new IntervalComparator());

        LinkedList<Interval> merged = new LinkedList<Interval>();
        for (Interval interval : intervals) {
            // if the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, simply append it.
            if (merged.isEmpty() || merged.getLast().end < interval.start) {
                merged.add(interval);
            }
            // otherwise, there is overlap, so we merge the current and previous
            // intervals.
            else {
                merged.getLast().end = Math.max(merged.getLast().end, interval.end);
            }
        }

        return merged;
    }
}

Interval这个类哪里来的，不明白。答案里没讲清楚。