Showing posts with label Pocket Gems. Show all posts
Showing posts with label Pocket Gems. Show all posts

Sunday, May 28, 2017

269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Given the following words in dictionary,
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".
Example 2:
Given the following words in dictionary,
[
  "z",
  "x"
]
The correct order is: "zx".
Example 3:
Given the following words in dictionary,
[
  "z",
  "x",
  "z"
]
The order is invalid, so return "".
Note:
  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.



Solution:

The idea is to use topological sort to get the order of characters.

To build the graph, we compare every two adjacent words.

If we found the character in the same index different, we know the order of these two characters, and thus add an edge and update the indegree.

After building the graph, we simply apply topological sort.



Code:


public class Solution {
    public String alienOrder(String[] words) {
        ArrayList<Character>[] adj = new ArrayList[26];
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<Character>();
        }
        
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (indegree[c - 'a'] < 0) {
                    indegree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 == c2) {
                    if (j == w2.length() - 1 && w1.length() > w2.length()) {
                        return "";
                    }
                    continue;
                }
                if (!adj[c1 - 'a'].contains(c2)) {
                    adj[c1 - 'a'].add(c2);
                    indegree[c2 - 'a']++;
                }
                break;
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0) {
                queue.offer((char)('a' + i));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char nei : adj[c - 'a']) {
                indegree[nei - 'a']--;
                if (indegree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int d : indegree) {
            if (d > 0) {
                return "";
            }
        }
        return sb.toString();
    }
}



Use HashMap


public class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        StringBuilder order = new StringBuilder();
        HashMap<Character, HashSet<Character>> adj = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            adj.put(c, new HashSet<Character>());
        }
        int[] degree = new int[26];
        Arrays.fill(degree, -1);
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (degree[c - 'a'] == -1) {
                    degree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2 - 'a']++;  
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) {
                    return "";
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (degree[i] == 0) {
                queue.offer((char)(i + 'a'));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : adj.get(c)) {
                if (--degree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (degree[i] > 0) {
                return "";
            }
        }
        return order.toString();
    }
}

Saturday, May 27, 2017

380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.
  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();



Solution:

Use a HashMap and an ArrayList.

ArrayList is to store the elements and the HashMap is to mapping the position of the element.

To insert an element, simply check if its already in the map. If not, we append it to the ArrayList and update the HashMap.

To remove an element, we use HashMap to find its location, swap with the end of the ArrayList, and remove it. Don't forget to update the mapping of the end element which swapped location.



Code:


public class RandomizedSet {

    ArrayList<Integer> list;
    HashMap<Integer, Integer> map;
    java.util.Random rand = new java.util.Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }
    
    /** 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 key = list.get(list.size() - 1);
        int index = map.get(val);
        Collections.swap(list, index, list.size() - 1);
        map.put(key, index);
        map.remove(list.get(list.size() - 1));
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size())); 
    }
}

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

Friday, May 26, 2017

133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/



Solution:

Method 1: BFS

We use BFS to traverse the graph.

When we meet a node, we make a copy of it and store it into the HashMap.

We also check all its neighbors.

If any of its neighbor is not in the HashMap, we make a copy of it and store in the HashMap.

One more step: add this neighbor to the neighbor list of the current node we check.

The time complexity is O(n) and space complexity is also O(n).



Code:


/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode nei : curr.neighbors) {
                if (!map.containsKey(nei)) {
                    map.put(nei, new UndirectedGraphNode(nei.label));
                    queue.add(nei);
                }
                map.get(curr).neighbors.add(map.get(nei));
            }
        }
        return map.get(node);
    }
}

Monday, May 8, 2017

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note: 
  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.



Solution:

The idea is to count the frequency of each number. Then we use a bucket array and put all the numbers that appear x times to index x.

Hence, we add the most frequent number to the result until reach k elements.

Both time complexity and space complexity are O(n).



Code:


public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            }
            else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(key);
        }
        
        for (int i = bucket.length - 1; i >= 0 && k > 0; i--) {
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    result.add(num);
                    k--;
                    if (k == 0) {
                        break;
                    }
                }
            }
        }
        return result;
    }
}

Sunday, May 7, 2017

28. Implement strStr()

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.



Solution:

Method 1: Brute Force

An optimized brute force implementation.

The time complexity is O(n2).



Code:


public class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            int j = 0;
            for (; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == needle.length()) {
                return i;
            }
        }
        return -1;
    }
}



Method 2 : Booye-Moore

The idea is to pre-process a table that when we do the compare of two strings, we know how many steps to skip and continue comparing.

The best time complexity is O(m / n) and worst cast time complexity is O(mn).

The space complexity is O(1).



Code:


public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        int[] right = new int[256];
        Arrays.fill(right, -1);
        for (int j = 0; j < n; j++) {
            right[needle.charAt(j)] = j;
        }
        int skip = 0;
        for (int i = 0; i < m - n + 1; i++) {
            skip = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    skip = Math.max(1, right[haystack.charAt(i + j)]);
                    break;
                }
            }
            if (skip == 0) {
                return i;
            }
        }
        return -1;
    }
}

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.



Solution:

Method 1: DP

We want to know whether s0,i can be break, where i = s.length() - 1.

For any given i, if we find a j that s0,j can be break, and sj,i is in the dictionary. We know s0,i can be break.

The time complexity is O(n3) and the space complexity is O(n).



Code:


public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        // canbreak[i]: first i characters can be break
        boolean[] canbreak = new boolean[s.length() + 1];
        canbreak[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (canbreak[j] && wordDict.contains(s.substring(j, i))) {
                    canbreak[i] = true;
                    break;
                }
            }
        }
        return canbreak[s.length()];
    }
}



Method 2: BFS

We use BFS to search a valid cut.

If we can cut at index i, we offer it into the queue.

Each time we poll an index from the queue and try from this index.

If we find we reach the end of the string, we know there is a valid cut.



Code:


public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        boolean[] visited = new boolean[s.length()];
        while (!queue.isEmpty()) {
            int start = queue.poll();
            if (!visited[start]) {
                for (int i = start + 1; i <= s.length(); i++) {
                    if (wordDict.contains(s.substring(start, i))) {
                        if (i == s.length()) {
                            return true;
                        }
                        queue.offer(i);
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
}

Friday, May 5, 2017

285. Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.



Solution:

Since the tree is BST, we know any node smaller than root is in its left subtree and any node larger than root is in its right subtree.

Therefore, if we find p.val < root.val, we know if we want to find p we should go left. So we set root to be the candidate of its successor and go left.

If p.val > root.val, since we're doing a in-order traversal, we do not need to update the successor.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return root;
        }
        
        TreeNode succ = null;
        while (root != null) {
            if (root.val > p.val) {
                succ = root;
                root = root.left;
            }
            else {
                root = root.right;
            }
        }
        return succ;
    }
}

Wednesday, May 3, 2017

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?



Solution:

This is a classic 3-way-partition quick-select problem.

The original code only needs subtle change to accommodate only three numbers: 0, 1, and 2.



Code:


public class Solution {
    public void sortColors(int[] nums) {
        int lt = 0;
        int gt = nums.length - 1;
        int i = 0;
        
        while (i <= gt) {
            if (nums[i] == 0) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] == 2) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.



Solution:

Method 1: find kth smallest

kth largest number in array nums, is the (nums.length - k + 1)th smallest umber in the array.

And its absolute position in an sorted order is nums.length - k.

Therefore, we recursively call 3-way partition until nums[nums.length - k] is finalized.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        k = nums.length - k;
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k);
        
        return nums[k];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int lt = lo;
        int gt = hi;
        int i = lo;
        
        while (i <= gt) {
            if (nums[i] < v) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > v) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        
        if (lt < pos) {
            partition(nums, lt + 1, hi, pos);
        }
        if (lt > pos) {
            partition(nums, lo, lt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}



Method 2: find kth largest

Modify the 3-way partition to put larger number before pivot and smaller number after pivot.

The kth largest number is nums[k - 1] after partition.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k - 1);
        
        return nums[k - 1];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int gt = lo;
        int lt = hi;
        int i = lo;
        
        while (i <= lt) {
            if (nums[i] > v) {
                exch(nums, gt++, i++);
            }
            else if (nums[i] < v) {
                exch(nums, lt--, i);
            }
            else {
                i++;
            }
        }
        
        if (gt < pos) {
            partition(nums, gt + 1, hi, pos);
        }
        if (gt > pos) {
            partition(nums, lo, gt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}