leetcode 352 & leetcode 239 & leetcode 295 & leetcode 53 & leetcode 209

lc352 Data Stream as Disjoint Intervals

可以用treemap解

key保存interval的start，value保存interval的end。分别找出当前val的lowerKey（treemap中>val的最小key值，没有就返回null）和higherKey(<val的最大key没有就返回null) 有以下几种情况： 1）当前插入的key与前后两个interval重叠合并三者，将前一个的interval.end改成后一个的end，并且将后一个从treemap中删除 2）当前插入的key与前面的interval重叠合并，前一个interval的end改成Math.max(end, val) 注意这里的判断条件不能写成 treemap.(treemap.lowerKey(val)) == val – 1; 而是应该写成>=，前者会出现异常，举例来说[4, 9] 现在val=7，按前者的判断条件，可能就直接放到case4里了，变成[4, 9]和[7, 7]共存 3）当前插入的key与后面的interval重叠 put(val, 后一个的end) remove(后一个的key) 4）当前插入的key不和任何已存在interval重叠，直接插入，按题意value设为key值

class SummaryRanges {

    TreeMap<Integer, Integer> tree;

    /** Initialize your data structure here. */

    public SummaryRanges() {

        tree = new TreeMap<>();

    }

    public void addNum(int val) {

        if(tree.containsKey(val))

            return;

        Integer l = tree.lowerKey(val);

        Integer h = tree.higherKey(val);

        Integer lv = l == null ? null : tree.get(l);

        Integer hv = h == null ? null : tree.get(h);

        if(l != null && h != null && lv == val - 1 && h == val + 1){

            //lv = hv;

            tree.put(l, hv);

            tree.remove(h);

        }else if(l != null && lv >= val - 1){

            //lv = val;

            tree.put(l, Math.max(lv, val));

        }else if(h != null && h == val + 1){

            tree.put(val, hv);

            tree.remove(h);

        }else{

            tree.putIfAbsent(val, val);

        }

    }

    public int[][] getIntervals() {

        Iterator it = tree.keySet().iterator();

        int i = 0;

        int[][] res = new int[tree.size()][2];

        while(it.hasNext()){

            Integer key = (Integer)it.next();

            res[i][0] = key;

            res[i][1] = tree.get(key);

            i++;

        }

        return res;

    }

    /*public int[][] getIntervals() {

        return tree.entrySet()

                .stream()

                .map(e -> new int[]{e.getKey(), e.getValue()})

                .toArray(int[][]::new);

    }*/

}

/**

 * Your SummaryRanges object will be instantiated and called as such:

 * SummaryRanges obj = new SummaryRanges();

 * obj.addNum(val);

 * int[][] param_2 = obj.getIntervals();

 */

239 Sliding Window Maximum

1）双向队列，时间复杂度o(n)

　　a）维护一个最大长为k（可能实际长度小于k，见b）的双向队列，保证当前队列有序，头元素为最大，这样每次只需要取dq.peek()即可。怎么保证队列有序其头元素最大呢？每次i迭代后，把队列中没有用的元素剔除。就是把<nums[i]的元素全部剔除，然后把nums[i]的索引i放入队列。怎么剔除？这里就用到了双向队列，从队尾开始删pollLast() 注意，队列中存放的是index而非值本身，目的是为了下一步b中确定队头元素的位置是否还在window内

　　b）保证队头的元素都来自i-k+1~i，因为这是一个sliding window。 if(dp.peek() < i-k+1) dp.poll() //直接删除队首元素

 class Solution {

     public int[] maxSlidingWindow(int[] nums, int k) {

         if(nums == null ||nums.length == 0)

             return nums;

         int len = nums.length;

         int size = len - k + 1;

         int[] res = new int[size];

         Deque<Integer> dq = new ArrayDeque<>();

         for(int i=0, j=0; i<len; i++){

             while(!dq.isEmpty() && dq.peek() < i - k + 1)

                 dq.poll();

             while(!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])

                 dq.pollLast();

             dq.offer(i);

             if(i >= k-1)

                 res[j++] = nums[dq.peek()];

         }

         return res;

     }

 }

2）最大堆，时间复杂度o(nlogk)

维护一个大小为k的最大堆，可以把priorityqueue翻转一下即可 PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()) 每次i迭代，去掉nums[i-k]，插入nums[i]，然后取堆root元素即可。

295 Find Median from Data Stream

用一个最大堆和一个最小堆，最大堆里放历史数据流中前k小的数，最小堆中放剩下的数，数据流总size为偶数，则两个堆大小相等，若为奇数，则最大堆比最小堆多一个数。这样我们median要么是最大堆root值，要么是两个堆root的平均值。

 class MedianFinder {

         PriorityQueue<Integer> min = new PriorityQueue<>();

         PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

     /** initialize your data structure here. */

     public MedianFinder() {

     }

     public void addNum(int num) {

         max.offer(num);

         min.offer(max.poll());

         if(max.size() < min.size())

             max.offer(min.poll());

     }

     public double findMedian() {

         if(max.size() == min.size())

             //return (max.poll() + min.poll()) / 2;

             //poll() will remove the first element of priorityqueue, but peek() will just retrieve the value and will not remove the element

             return (max.peek() +min.peek()) / 2.0;

         else

             return max.peek();

     }

 }

 /**

  * Your MedianFinder object will be instantiated and called as such:

  * MedianFinder obj = new MedianFinder();

  * obj.addNum(num);

  * double param_2 = obj.findMedian();

  */

53 Maximum Subarray

用dp解

dp[i]定义为包含当前i的最大子序列

递归式：dp[i] = max(dp[i-1], dp[i-1] + nums[i]);

注意还要用一个max变量保存dp[i]中（i=0~n-1）最大的那个dp[i]

返回值为max

 class Solution {

     public int maxSubArray(int[] nums) {

         if(nums == null ||nums.length == 0)

             return 0;

         int len = nums.length;

         int[] dp = new int[len];

         dp[0] = nums[0];

         int max = dp[0];

         for(int i=1; i<len; i++){

             dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

             max = Math.max(max, dp[i]);

         }

         //max = Math.max(max, dp[0]);

         return max;

     }

 }

209 Minimum Size Subarray Sum

双指针，

一个指针用来求和，即j-i的所有元素只和，sum += nums[i++]

一个指针用来减去0-j的元素, sum -= nums[j++] 每当j~i之和>=s，记录j~i的长度，用一个min记录所有ij组合的长度最小值,r然后减去当前j所指元素，j++，直到j~i之和<s

 class Solution {

     public int minSubArrayLen(int s, int[] nums) {

         if(nums == null || nums.length == 0)

             return 0;

         int i=0, j=0, min = Integer.MAX_VALUE;

         int sum = 0;

         while(i < nums.length){

             sum += nums[i++];

             while(sum >= s){

                 min = Math.min(min, i-j);

                 sum -= nums[j++];

             }

         }

         return min == Integer.MAX_VALUE ? 0 : min;

     }

 }

巴特西

leetcode 352 & leetcode 239 & leetcode 295 & leetcode 53 & leetcode 209

最新文章

热门文章