LeetCode(58) -- 15, 23,

P15. 3Sum (Medium)

一个数组中，找出三个数的和为0的所有triplets

我的思路

暂时没什么思路，用暴力求解，结果超时了。

我的代码

public class M_15_3Sum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        HashSet<Triple> triples = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[k] < 0) {
                        continue;
                    }
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        Triple triple = new Triple(nums[i], nums[j], nums[k]);
                        if (triples.contains(triple)) {
                            continue;
                        }
                        triples.add(triple);

                        List<Integer> triplet = new ArrayList<>();
                        triplet.add(nums[i]);
                        triplet.add(nums[j]);
                        triplet.add(nums[k]);
                        list.add(triplet);
                    }
                }
            }
        }
        return list;
    }

    class Triple  {
        private final int x, y, z;
        private final int[] sorted;

        public Triple(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.sorted = new int[] {x, y, z};
            Arrays.sort(sorted);
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof Triple
                    && Arrays.equals(((Triple)obj).sorted, this.sorted);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(sorted);
        }
    }
}

讨论区

public class M_15_3Sum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int low = i + 1, high = nums.length - 1, sum = -nums[i];
            while (low < high) {
                if (nums[low] + nums[high] == sum) {
                    list.add(Arrays.asList(nums[i], nums[low], nums[high]));
                    while (low < high && nums[low] == nums[low + 1]) low++;
                    while (low < high && nums[high] == nums[high - 1]) high--;
                    low++;
                    high--;
                } else if (nums[low] + nums[high] < sum) {
                    low++;
                } else {
                    high--;
                }
            }
        }
        return list;
    }
}

88% 学习这个。

最优解

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> threeSums = new ArrayList<>();

        for(int i=0; i<nums.length; i++){
            for(int j=1; j<nums.length; j++){
                for(int k=2; k<nums.length-2; k++){
                    if(nums[i]+nums[j]+nums[k] == 0){
                        ArrayList<Integer> lst = new ArrayList<Integer>();
                        lst.add(nums[i]);
                        lst.add(nums[j]);
                        lst.add(nums[k]);
                        threeSums.add(new ArrayList<Integer>(lst));
                        System.exit(0);
                    }
                }
            }
        }

        return threeSums;
    }

    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        if( n < 3) return result;

        Arrays.sort(nums);
        for ( int i = 0; i < n-2; i++){
            if( i > 0 && nums[i] == nums[i-1]) continue;
            if( nums[i] + nums[n-2] + nums[n-1] < 0) continue;
            if( nums[i] + nums[i+1] + nums[i+2] > 0) break;
            int j = i + 1, k = n -1;
            while( j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if( sum == 0){
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++; k--;
                    while( j < k && nums[j] == nums[j-1]) j++;
                    while( j < k && nums[k] == nums[k+1]) k--;
                } else if ( sum < 0 ){
                    j++;
                } else {
                    k--;
                }
            }
        }
        return result;
    }
}

第一个函数好像是错误的，第二个跟讨论区的差不多。

P23. Merge k Sorted Lists (Medium)

有k个排列好的list，把他们合并到一起，形成一个新的list

我的思路

每次都从所有的头节点中，找出最小值，然后把这个list移动到下一个节点。

我的代码

public class H_23_MergekSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        for (ListNode node : lists) {
            if (node != null) {
                pq.add(node);
            }
        }
        while (pq.size() != 0) {
            ListNode node = pq.poll();
            curr.next = new ListNode(node.val);
            curr = curr.next;
            node = node.next;
            if (node != null) {
                pq.add(node);
            }
        }
        return dummyHead.next;
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

76%

最优解

class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
      	return partition(lists, 0, lists.length-1);
    }

    private ListNode partition(ListNode[] lists, int s, int e){
        if(s > e) return null;
        if(s == e) return lists[e];
        int mid = (s+e)/2;
        ListNode left = partition(lists, s, mid);
        ListNode right = partition(lists, mid+1, e);
        ListNode result = new ListNode(0);
        ListNode current = result;
        while(left != null && right != null){
            if(left.val  < right.val){
                current.next = left;
                left = left.next;
            }else{
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }

        if(left != null)
            current.next = left;
        else
            current.next = right;
        return result.next;
    }
}

分治，把所有list先分成两组，再分四组，再分八组。。。最后是所有list两两合并，并最终合并成一个最大的list.

P42. Trapping Rain Water (Hard)

一个数组表示海拔高度的地图。如果下雨的话，能存多少水

我的思路

存水肯定是从中间的最高山峰向两侧递减。所以我先找最中间的最高点，然后向两侧扩散，向两边分别找出最高点，再向两边分别找出最高点。。。

我的代码

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 2) return 0;
        int count = 0;
        int highest = findHighest(height, 0, height.length - 1);
        int left = highest, right = highest;
        int leftBound = 0, rightBound = height.length - 1;
        while (height[leftBound] == 0) leftBound++;
        while (height[rightBound] == 0) rightBound--;
        while (left > leftBound) {
            int tempLeft = findHighest(height, leftBound, left - 1);
            for (int i = tempLeft; i < left; i++) {
                if (height[i] < height[tempLeft]) {
                    count += height[tempLeft] - height[i];
                }
            }
            left = tempLeft;
        }
        while (right < rightBound) {
            int tempRight = findHighest(height, right + 1, rightBound);
            for (int i = right + 1; i <= tempRight; i++) {
                if (height[i] < height[tempRight]) {
                    count += height[tempRight] - height[i];
                }
            }
            right = tempRight;
        }
        return count;
    }

    private int findHighest(int[] height, int start, int end) {
        int highest = 0, highestIndex = start;
        for (int i = start; i <= end; i++) {
            if (height[i] > highest) {
                highest = height[i];
                highestIndex = i;
            }
        }
        return highestIndex;
    }
}

98%

最优解

public class P42_TrappingRainWater {
    public int trap(int[] height) {
        int i = 0, j = height.length - 1, ans = 0, bound = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                if (height[i] > bound) {
                    bound = height[i++];
                } else {
                    ans += bound -  height[i++];
                }
            } else {
                if (height[j] > bound) {
                    bound = height[j--];
                } else {
                    ans += bound - height[j--];
                }
            }
        }
        return ans;
    }
}