211. Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true

思路:用Trie来实现, Search的时候关键在于’.’的处理, 这里可以递归实现. 递归的时候每次都取第一个字符来c判断:
1.c为’.’: 需要递归搜索当前TrieNode的children是否包含word的下一个字符。
2.c不为’.’:
1,如果当前trieNode的children里不存在c,返回false.
2, 如果当前trieNode里存在c, 则trieNode更新下,word取下一个字符,然后递归

public class WordDictionary {
    public class TrieNode {
        HashMap<Character, TrieNode> children;
        boolean hasWord;
        public TrieNode() {
            children = new HashMap<>();
            hasWord = true;
        }
    }

    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        TrieNode current = root;
        for (int i = 0; i < 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;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return search(word, root);
    }

    public boolean search(String word, TrieNode current) {
        if (current == null || word.length() == 0 || word == null) return true;
        char c = word.charAt(0);
        if (c != '.') {
            if (!current.children.containsKey(c)) {
                return false;
            } else {
                current = current.children.get(c);
                return search(word.substring(1), current);
            }

        } else { // '.' search all children for 
            for(TrieNode child: current.children.values()) {
                if (search(word.substring(1), child)) {
                    return true;
                }
            }
        }
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

思路:Trie的实现,这里用HashMap来实现。

class TrieNode {
    // Initialize your data structure here.
    HashMap&lt;Character, TrieNode&gt; children;
    boolean hasWord;
    public TrieNode() {
        children = new HashMap&lt;Character, TrieNode&gt;();
        hasWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        if (word.length() == 0 || word == null) 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;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word.length() == 0 || word == null) 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;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix.length() == 0 || prefix == null) return true;
        TrieNode current = root;
        for (int i = 0; i &lt; prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (!current.children.containsKey(c)) {
                return false;
            }
            current = current.children.get(c);
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert(&quot;somestring&quot;);
// trie.search(&quot;key&quot;);

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. 二分法

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.

思路:我们用两个指针,一个指向头,一个指向尾。 大概思路就是把0元素放到left左边,2放到right右边。用一个pointer指针从左往右开始遍历,当遇到0时,0与left位置上的元素交换, 当遇到2的时候,与right进行交换,注意:right位置的元素可能为0,right把0元素交换到前面的时候,需要下次再判断一次,看是否需要跟left交换。
复杂度: time O(n), space: O(1)

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int left = 0;
        int right = nums.length - 1;
        int i = 0;
        while(i &lt;= right) {
            if (nums[i] == 0) {
                swap(nums, i, left);
                i++;
                left++;
            } else if (nums[i] == 2){
                swap(nums, i, right);
                right--;
            } else {
                i++;
            }

        }

    }

    public void swap(int[] nums, int n1, int n2) {
        int tmp = nums[n1];
        nums[n1] = nums[n2];
        nums[n2] = tmp;
    }
}

Graph, BFS, DFS的总结

HackerRank中对Graph的BFS跟DFS讲的不错,再次做个简短总结.
如下图所示
DFS: Go Deep. recursive的过程,需要flag,用来避免陷入infinite loop.
BFS: Go BOARD. iterative的过程, 需要用queue,来记录nextToVisit的点.
bfs-dfs
代码部分:

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=zaBhtODEL0w
 */
public class Graph {
    private HashMap&lt;Integer, Node&gt; nodeLookup = new HashMap&lt;Integer, Node&gt;();


    public Node getNode(int id) {
        if (!nodeLookup.containsKey(id)) return null;
        return nodeLookup.get(id);
    }

    private void addEdge(int source, int destination) {

    }

    public boolean hasPathDFS(int source, int destination) {
        Node s = getNode(source);
        Node d = getNode(destination);
        HashSet&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();
        return hasPathDFS(s, d, visited);
    }

    private boolean hasPathDFS(Node source, Node destination, HashSet visited) {
        if (visited.contains(source.id)) return false;
        visited.add(source.id);
        if (source == destination) {
            return true;
        }

        for (Node child: source.adjacent) {
            if (hasPathDFS(child, destination, visited)){
                return true;
            }
        }
        return false;
    }

    public boolean hashPathBFS(int source, int destination) {
        return hasPathBFS(this.getNode(source), this.getNode(destination));
    }

    private boolean hasPathBFS(Node source, Node destination) {
        LinkedList&lt;Node&gt; nextToVisit = new LinkedList&lt;Node&gt;();
        HashSet&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();
        nextToVisit.add(source);
        while(!nextToVisit.isEmpty()) {
            Node node = nextToVisit.remove();
            if (node == destination) {
                return true;
            }

            if (visited.contains(node.id)) {
                continue;
            }
            visited.add(node.id);

            for (Node child: node.adjacent) {
                nextToVisit.add(child);
            }
        }
        return false;

    }


    public static class Node {
        private int id;
        LinkedList&lt;Node&gt; adjacent = new LinkedList&lt;Node&gt;();
        private Node(int id) {
            this.id = id;
        }
    }

}

 

Heap的实现总结

HankerRank上对Heap的实现讲的很赞,再次贴下代码作为参考, 以min heap的实现为例, 我们用一个数组来放heap中的元素。
Min Heap的root节点总是最小值,所以获得最小值的时间复杂度为O(1),当root poll()出去后,heap中剩下的元素要进行调整,保证heap是min heap的结构,这个过程叫heapifyDown.
Poll(): 拿掉数组的第一个元素,对于第一个元素空出来的位置,先把数组最后一个元素放到 数组开头位置,然后进行heapifyDown进行调整,从root位置开始,比较root位置代表的parent与其左右children的大小,parent总是与children中元素较小的进行交换。 重复这个过程,直到大的元素不再有children。
Peek(): 返回数组的第一个元素的值。
Insert(): 插入一个新的元素,总是放在数组元素的最后一个位置,然后进行heapifyUp,调整heap满足min heap。
heapifyDown: 把最后一个元素放到root的位置,从root位置开始,比较root位置代表的parent与其左右children的大小,parent总是与children中元素较小的进行交换。 重复这个过程,直到大的元素不再有children。
heapifyUp: 数组新增的最后一个元素与其parent进行比较, 如果新增元素的值小于其parent的值,则进行交换,递归此过程。

import java.util.Arrays;

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=t0Cq6tVNRBA
 */
public class MinIntHeap {
    private int capacity = 10;
    private int size = 0;

    int[] items = new int[capacity];

    private int getLeftChildIndex(int parentIndex) {return 2 * parentIndex + 1};
    private int getRightChildIndex(int parentIndex) {return 2 * parentIndex + 2};
    private int getParentIndex(int childIndex) {return (childIndex - 1) / 2;}

    private boolean hasLeftChild(int index) {return getLeftChildIndex(index) < size;}
    private boolean hasRightChild(int index) {return getRightChildIndex(index) < size;}
    private boolean hasParent(int index) {return getParentIndex(index) >= 0; }

    private int leftChild(int index) {return items[getLeftChildIndex(index)];}
    private int rightChild(int index) {return items[getRightChildIndex(index)];}
    private int parent(int index) {return items[getParentIndex(index)];}

    private void swap(int indexOne, int indexTwo) {
        int tmp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = tmp;
    }

    private void ensureExtraCapacity() {
        if (size == capacity) {
            items = Arrays.copyOf(items, capacity * 2);
            capacity *= 2;
        }
    }

    public int peek() {
        if (size == 0) throw new IllegalStateException();
        return items[0];
    }

    public int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = items[0]; // get the first element
        items[0] = items[size - 1]; // move the last element to the first element position
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        ensureExtraCapacity();
        items[size] = item;
        size++;
        heapifyUp();
    }

    public void heapifyUp() {
        int index = size - 1; // start from last element
        while (hasParent(index) && parent(index) > items[index]) {
            swap(getParentIndex(index), index);
            index = getParentIndex(index);
        }
    }

    public void heapifyDown() {
        int index = 0; // start from root
        while(hasLeftChild(index)) {
            int smallerChildINdex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
                smallerChildINdex = getRightChildIndex(index);
            }

            if (items[index] < items[smallerChildINdex]) {
                break;
            } else {
                swap(index, smallerChildINdex);
            }
            index = smallerChildINdex;
        }
    }

}

Trie的实现

参考HankerRank上的Trie的实现。

import java.util.HashMap;

/**
 * Created by dylan on 10/29/16.
 */
public class Trie {
    public static class Node {
        // Solve 'Contacts' using Tries
        private static final int NUM_OF_CHARACTERS = 26;
//        HashMap&lt;Character, Node&gt; children;
//        boolean isCompleteWord;
        Node[] children = new Node[NUM_OF_CHARACTERS];
        int size = 0;


        private static int getCharIndex(char c) {
            return c - 'a';
        }

        private Node getNode(char c) {
            return children[getCharIndex(c)];
        }

        private void setNode(char c, Node node) {
            children[getCharIndex(c)] = node;
        }

        public void add(String s) {
            add(s, 0);
        }

        private void add(String s, int index) {
            size++;
            if (index == s.length()) return;
            char current = s.charAt(index);
            Node child = getNode(current);
            if (child == null) {
                child = new Node();
                setNode(current, child);
            }
            child.add(s, index + 1);
        }

        public int findCount(String s, int index) {
            if (index == s.length()) return size;
            Node child = getNode(s.charAt(index));
            if (child == null) return 0;
            return child.findCount(s, index + 1);
        }

    }




}