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].
思路: 先sort排序,再merge。 Merge的过程就是找当前interval的start如果小于或者等于之前interval的end,那么之前的interval就可以extend当前interval,preInterval.end=curInterval.end; 否则的话,就不能merge;为了进行遍历,我们用两个变量preStart,preEnd来保存之前的interval的信息,遍历的时候我们用cur.start跟preEnd进行比较 1) cur.start>=preEnd, merge,然后更新preStart,preEnd 2)preEnd取Max(cur.end, preEnd).
复杂度: time O(nlogn), space O(n)

/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) return res;
        if (intervals.size() == 1) return intervals;

        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                if (i1.start == i2.start) {
                    return i2.end - i1.end;
                } 
                return i1.start - i2.start;
            }
        });

        int preStart = intervals.get(0).start;
        int preEnd = intervals.get(0).end;

        for(int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start > preEnd) {
                res.add(new Interval(preStart, preEnd));
                preStart = cur.start;
                preEnd = cur.end;
            } else {
                preEnd = Math.max(preEnd, cur.end);
            }
        }
        res.add(new Interval(preStart, preEnd));
        return res;
    }
}
Advertisements

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return [“eat”,”oath”].

思路: 如果用BFS来做的话,

复杂度: time 是MN26^L, space: 26^L, 用Trie来做, 先建立Trie树,把words添加到trie中,然后用BFS 去遍历board,找满足的点。 找的时候需要剪枝。

public class Solution {
    public int[] xDir = new int[]{-1, 0, 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};
    public class TrieNode {
        HashMap&lt;Character, TrieNode&gt; children;
        boolean hasWord;
        public TrieNode() {
            this.children = new HashMap&lt;Character, TrieNode&gt;();
            this.hasWord = false;
        }
    }

    public class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String word) {
            if (word == null || word.length() == 0) return;
            TrieNode current = root;
            for (int i = 0; i &lt; word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    current.children.put(c, new TrieNode());
                }
                current = current.children.get(c);
            }
            current.hasWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) return false;
            TrieNode current = root;
            for (int i = 0; i &lt; word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    return false;
                }
                current = current.children.get(c);
            }
            return current.hasWord;
        }
    }


    public List&lt;String&gt; findWords(char[][] board, String[] words) {
        List&lt;String&gt; res = new ArrayList&lt;&gt;();
        if (board == null || board.length == 0 || board[0] == null || 
            board[0].length == 0 || words.length == 0 || words == null)
            return res;
        // build Trie tree
        Trie trie = new Trie();
        for (String word: words) {
            trie.insert(word);
        }
        StringBuilder sb = new StringBuilder();
        // search words in board
        for (int i = 0; i &lt; board.length; i++) {
            for (int j = 0; j &lt; board[0].length; j++) {
                search(board, trie.root, i, j, res, sb);
            }
        }  
        return res;
    }

    public void search(char[][] board, TrieNode root, int x, int y, List&lt;String&gt; res, StringBuilder sb) {
        if (!isValid(board, x, y)) return;
        char c = board[x][y];
        TrieNode current = root.children.get(c);
        // check edge case
        if (c == '#' || current == null) return;
        sb.append(c);
        if (root.hasWord) { // check has a word
            res.add(sb.toString());
            root.hasWord = false;
        }

        board[x][y] = '#'; // pruning
        for (int k = 0; k &lt; 4; k++) { // explore 4 directions
            int newX = x + xDir[k];
            int newY = y + yDir[k];
            search(board, current, newX, newY, res, sb);
        }
        sb.setLength(sb.length() - 1);
        board[x][y] = c;
    } 

    public boolean isValid(char[][] board, int x, int y) {
        if (x &lt; 0 || x &gt;= board.length || y &lt; 0 || y&gt;= board[0].length) return false;
        return true;
    }
}

380/381. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
思路: 设计个数据结构,用hashmap+List来做。
insert: hashmap中存(val, idx), idx为在List中的元素的下标位置。
remove: 删除的时候要求是O(1);把元素val与List中最后一个元素兑换,然后删除最后一个元素。
1. 从hashmap中拿到元素val在List中的下标 2.拿到List中最后一个元素的值last 3. List中把val下标位置的元素更新为last元素的值,map中加入(last, idx)。 4.最后List中移除最后一个元素,map中remove掉val的key。

public class RandomizedSet {
    List<Integer> list;
    HashMap<Integer, Integer> map;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        if (index != list.size() - 1) {
            int last = list.get(list.size() - 1);
            list.set(index, last);
            map.put(last, index);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

Follow up: 允许duplicates的存在。

public class RandomizedCollection {
    List<Integer> list;
    HashMap<Integer, Set<Integer>> map;
    Random rand = new Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();

    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            Set<Integer> set = map.get(val); // get existing set
            list.add(val); // add to list
            set.add(list.size() - 1); // add idx to set
            map.put(val, set);
            return false;
        } 
        list.add(val);
        int idx = list.size() - 1;
        map.put(val, new HashSet<Integer>(Arrays.asList(idx)));
        return true;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        Set<Integer> set = map.get(val);
        int toRemovePos = set.iterator().next(); // the idx of to remove element 
        set.remove(toRemovePos);
        if (toRemovePos < list.size() - 1) { // list have more than 1 elements
            int last = list.get(list.size() - 1); // get the last element
            list.set(toRemovePos, last); // set the last element at toRemovePos position
            map.get(last).remove(list.size() - 1); // remove the last element from map
            map.get(last).add(toRemovePos); 
        }
        list.remove(list.size() - 1);
        if (map.get(val).isEmpty()) { // check set is empty
            map.remove(val);
        }

        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

思路: 题目不让修改array,禁止排序。 要求O(1)的额外空间,那么也就不能用hashmap来记录元素。给定的数组长度为1+n, 而每个数字的范围又是1-n之间,由于给定数组的特殊性。 我们可以想到用用linkedlist 找环的起始位置来解这道题目。

  1. 快慢指针找环:
public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length &lt; 2) return 0;
        int fast = nums[nums[0]];
        int slow = nums[0];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
  1. 二分法

295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

思路: 寻找datastream或者array中的中位数, 可以用两个heap来实现,一个max heap,一个min heap。 每次加一个数先放到max heap,然后把max heap中poll一个数出来放到min heap。 同时要检查下max heap中的元素比min heap中要多;取中位数的时候,如果两个heap的size相同,则各poll一个元素出来算平均,否则max heap中poll出的就是median.
复杂度. addNum: O(logN), space: O(n), findMedian: O(1)

public class MedianFinder {
    PriorityQueue<Integer> higherPQ;
    PriorityQueue<Integer> lowerPQ;

    public MedianFinder() {
        higherPQ = new PriorityQueue<Integer>();
        lowerPQ = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
    }

    // Adds a number into the data structure.
    public void addNum(int num) {
        higherPQ.add(num);
        lowerPQ.add(higherPQ.poll());

        if (higherPQ.size() < lowerPQ.size()) {
            higherPQ.add(lowerPQ.poll());
        }

    }

    // Returns the median of current data stream
    public double findMedian() {
        if (higherPQ.size() == lowerPQ.size()) {
            return ((double)higherPQ.peek() + lowerPQ.peek()) / 2.0;
        } else {
            return higherPQ.peek();
        }

    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?
思考: 用maxHeap来做,每个window内都用maxheap来取得最大值。
复杂度: Time(nlogk) Space: O(k)

public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        int res[] = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            // 窗口最左边数从pq中取出
            if (i >= k) pq.remove(nums[i - k]);
            // 把新加的数放到pq
            pq.offer(nums[i]);
            // 放到结果array
            if (i + 1 >= k) res[i - k + 1] = pq.peek();

        }
        return res;
    }

复杂度:Time O(n),
思考: 不会做,参考的几个blog解答。 发现有几个总结不错的解法,受益良多。
大致上这个题目是给定一个数组num跟长度为k的window, 求window从左往右滑动过程中,在滑动窗口所见的范围k内,出现的最大值的集合。
结果集合总共有nums.length – k + 1个元素, 所以我们的数组下标对应的也就是i-k+1;
我们用一个双向队列queue在O(n)时间内解决这个问题,保持窗口内的最大值在窗口边界(队列头),实现这个方法就是不停的删除掉窗口中比新进来元素小的元素。 数组中存的是元素的坐标,而不是每个元素对应的值, 每当有新的元素进入window时候,从队队尾开始,删掉比新元素小的元素,然后将新加进来的元素放到队列末尾。这样就保证了队首元素始终是窗口(队列)最大元素.

我们对这个数组进行遍历大概有以下几个步骤:
1. 对于新加进来的元素i,我们要判断是否k-i的值等于queue中的头部的坐标, 如果等于则需要将queue中头部元素扔掉。
2. 如果queue中队尾元素对应的值小于新加的元素i对应的值,那么持续扔掉队尾元素,保证queue中元素对应的值是降序的。
3. 把i加入queue中。
4. 判断如果i+i >=k,表示至少比较了k次,则需要记录一次最大值放到最终结果里面,我们直接取queue中头部元素对应的值。

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k || k <= 0 || nums == null) return nums;
        Deque<Integer> queue = ArrayDeque<Integer>();
        int[] res = nums.length - k + 1;
        for (int i = 0; i < nums.length; i++) {
            // window 是往右滑动的,每当往右滑动一个数,最左边的数要拿出来,我们要检查queue中的头部的下标是否等于i-k. 
            if (!queue.isEmpty() && queue.peek() == i - k) queue.poll();
            // queue中队尾所有比新数小的都扔掉,保证queue中是降序的
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) queue.pollLast();
            queue.offer(i);
            // 检查如果是比较了至少k次,那就把i-l+1这个点的坐标对应结果放到最终结果里面。
            if (i + 1 >= k) res[i-k+1] = queue.peek();
        }
        return res;
    }
}

Reference: [Leetcode] Sliding Window Maximum 滑动窗口最大值
239. Sliding Window Maximum
https://segmentfault.com/a/1190000003834593

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1

/ \
2 3
/ \
4 5
as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

思路: in-order traversal 来做,先定义好null node为”#”跟delimiter为”,”. serialize过程就是in-order 遍历然后转换成String。 deserialize过程也是对转换的string先按照delimiter进行tokenize一下,把拿到的数组放到Queue里面,然后in-order进行建树,每次从queue里面poll拿到一个节点,查看是否是null node,如果是就返回null,否则就当做根节点,然后依次建该根节点的左子树跟右子树,最后返回的节点就是root.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private final String emptyNode = &amp;quot;#&amp;quot;;
    private final String delimiter = &amp;quot;,&amp;quot;;


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(emptyNode).append(delimiter);
        } else {
            sb.append(root.val).append(delimiter);
            serialize(root.left, sb);
            serialize(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque&amp;lt;String&amp;gt; queue = new ArrayDeque&amp;lt;String&amp;gt;();
        Collections.addAll(queue, data.split(delimiter)); 
        TreeNode root = buildTree(queue);
        return root;
    }

    public TreeNode buildTree(Deque&amp;lt;String&amp;gt; nodes) {
        if (nodes.isEmpty()) 
            return null;
        String node = nodes.poll();
        if (node.equals(emptyNode)) 
            return null;
        TreeNode root = new TreeNode(Integer.valueOf(node));
        root.left = buildTree(nodes);
        root.right = buildTree(nodes);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));