215. Kth Largest Element in an Array -M !!!

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

A:

--------用maxHeap  ---------O(n+k*log(k))-----------------

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        // need a min heap, thus the top() is the minimum to remove
        priority_queue<int, vector<int>, greater<int> > q; // default is less, which result into max queue
        for(auto v : nums)
        {
            q.push(v);
            if(q.size()>k)
                q.pop();
        }
        return q.top();
    }
};

QuickSelect
(这道题的关键点在于 当值全部大于（或小于）pivot点的时候的处理方式。--》 因此要把pivot点swap到中间的操作。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // half of the quick sort
        int n = nums.size();
        if(k == 1){
            auto max_iter = max_element(nums.begin(), nums.end());// get max
            return *max_iter;
        }
        int mid = (nums.front() + nums.back()) / 2;// first get mid of first and last
        vector<int> bigger, smaller;
        int midCount = 0;
        for(const auto & val : nums){
            if( val > mid){
                bigger.push_back(val);// move to new and pop it out
            }else if(val == mid){
                midCount++;
            }else{
                smaller.push_back(val);
            }
        }
        if(bigger.size()>=k){
            return findKthLargest(bigger, k);
        }else if(bigger.size() + midCount >= k){
            return mid;
        }else{
            return findKthLargest(smaller, k- bigger.size() - midCount);
        }
    }
};

这个题目，自己第一次做的时候， 没有做把end的值swap到mid位置的操作，因此会出现死循环。

Mistakes:
1:   当k ==1的时候，还是要继续分下去。     而基础条件应该是 start == end
2:

double pivot = (A[start] + A[end])/2;

 这里，当A[start] == 1, A[end]==2的 时候，pivot 的结果是1.   ！！！！！
 因此要除以 2.0


------------------------排序-------  但是对于太大的数组，不适合--------------------

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

213. House Robber II -------------M

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

A:
递归，with memory

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> V(n, vector<int>(n,-1));
        return helper(nums,0,n-1, V);
    }
private:
    int helper(vector<int> & nums, int start, int end, vector<vector<int>> & V){
        if(start>end)
            return 0;
        if(V[start][end]>=0)
            return V[start][end];
        int withStart = nums[start] + helper(nums, start+2, end - (start==0?1:0), V);
        int noStart = helper(nums, start+1, end, V);
        
        int res = max(withStart, noStart);
        V[start][end] = res;
        return res;
    }
};

思路很简单，就是每次不取  头  或者不取尾。

class Solution {
public:
    int rob(vector<int>& nums) {        
        int n = nums.size();
        if(n==1)
            return nums[0];
        // two cases, with, or without first element
        return max(helper(nums,0, n-2), helper(nums, 1, n-1) );
    }
private:
    int helper(vector<int> & nums, int start, int end){
        //DP, each time, we jump or not jump
        int cur = 0, pre = 0; // current maxSum, or preMaxSum
        for(int i =start; i<= end; i++){
            int newMax = max(cur, pre+nums[i]);
            pre = cur;
            cur = newMax;
        }
        return cur;
    }
};

Mistakes:

忘记了当只有一个的情况，要单独列出来

House Robber

Q:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

A:
就是简单的 记录之前的两个位置.  每次加如一个新的值

class Solution {
public:
    int rob(vector<int>& nums) {
        int cur = 0, pre = 0; // max rob after using current value 
        for(int i =0; i<nums.size(); ++i)
        {
            int newCur = max(nums[i]+pre, cur);
            pre = cur;
            cur = newCur;
        }
        return cur;
    }
};

Mistakes:

212. Word Search II ----H ~~~~~~~~

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.

 

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

 

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

A:
就是用Trie了， 自己建Trie要麻烦些罢了。
然后用DFS即可。

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        int m = board.size();
        if(m== 0)
            return res;
        int n = board[0].size();
        Node* root = buildTrie(words);
        unordered_set<string> resSet;// to avoid duplicates
        vector<vector<bool>> visited(m,vector<bool>(n, false));
        for(int i =0;i<m;i++){
            for(int j = 0; j<n;j++){
                dfs(board, i,j,root->kids[board[i][j]], resSet, visited);
            }
        }
        res.assign(resSet.begin(),resSet.end());
        return res;
    }
private:
    struct Node{
        unordered_map<char,Node*> kids; // cannot declare here. (26,nullptr);
        bool isLeaf;
        char cur;
        string curWord;
        Node(char ch):cur(ch),isLeaf(false),curWord(""){}
    };
    Node* buildTrie(vector<string> &words){
        Node* root = new Node(' ');
        for(auto word: words){
            auto pre = root; // auto & pre = root is WRONG. DO NOT reference a pointer
            for(auto ch : word){
                if(not pre->kids[ch]){
                    pre->kids[ch] = new Node(ch);
                }
                pre = pre->kids[ch];
            }
            pre->isLeaf = true;
            pre->curWord = word;
        }
        return root;
    }
    void dfs(vector<vector<char>>& board, int i, int j, const Node* root, unordered_set<string>& resSet, vector<vector<bool>>& visited){
        int m = board.size();
        int n = board[0].size();
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || not root){
            return;
        }
        if(root->cur == board[i][j]){
            visited[i][j] = true;
            if(root->isLeaf){
                resSet.insert(root->curWord);
            }
            vector<vector<int>> Diff{ {-1,0},{1,0},{0,-1},{0,1}};
            for(auto& d : Diff){
                for(auto kid : root->kids){
                    dfs(board, i+d[0], j + d[1], kid.second, resSet,visited);
                }
            }
            visited[i][j] = false;
        }
    }
};

Mistakes:
1:  even isLeaf==true, 也需要继续找下去。  例如 words = {"the", "they" "their"}

2: 没有处理一个word被多次找到的情况。i.e.   word节点可能被多次找到，

例如输入是    {{'a'}} , {"a"}的时候。
   这样，我们就需要 每次见dfs下一层， 进去之后再检查 flag  matrix是否  valid
 但是，这样又会出现 一个位置 多次计算的问题。
 因此还是要  每次进入之前检测。
其实还是对自己的这个Trie的定义的理解问题。  代码里，我们是先到一个TrieNode之后，再检测该位置是否match，然后再试探着dfs

3： 
这个题目的关键点（for me）  就是 考虑到root的定义， 我们初始dfs的 时候，就要进入root的下一个TrieNode.

dfs(board, i,j,root->kids[board[i][j]], resSet, visited);

Contains Duplicate III ！！！！！！！！

Q:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
A:
就是对一个 k+1的窗口  保持一个排序。同时用 最大最小 来检测。

TreeSet：  是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int c = nums[i];
            if ((set.floor(c) != null && c <= set.floor(c) + t)
            || (set.ceiling(c) != null && c >= set.ceiling(c) -t))
                return true;
     
            set.add(c);
            if (i >= k)
                set.remove(nums[i - k]);
        }
        return false;
    }
}

Mistakes:

219. Contains Duplicate II

Q:
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
A:
就是简单的，在  k+1的长度中查询 duplicate

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet();
        for(int i =0;i< nums.length;i++){
            if(i - k - 1 >=0)   // delete first
                set.remove( nums[i-k-1]);
            
            if(set.contains(nums[i]))
                return true;
            set.add(nums[i]);
        }
        return false;
    }
}
 

Contains Duplicate

Q:
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
A:
--------Sol : 用Set    ,  use O(n) extra space   O(n) time---------

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i :nums){
            if(set.contains(i))
                return true;
            set.add(i);
        }
        return false;
    }
}

-------Sol 2:   manipulate nums, ,  use O(1) space, and O(n) time ----------------
每次按照某一位的 bit分开nums[],  然后再继续分，直到最后32bit还一样，就true,否则false

223. Rectangle Area -------------M ~~~~

Q:
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

A:
就是简单的找到相交的面积，再减去即可。

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long maxLeftX = max(A,E);
        long minRightX = min(C,G);
        long width = (minRightX - maxLeftX > 0)? (minRightX -maxLeftX):0;
        long maxBottomY = max(B, F);
        long minUpY = min(D, H);
        long height = (minUpY - maxBottomY >0)? (minUpY - maxBottomY) : 0;
        return int( long(C-A)*(D-B) + long(G-E)*(H-F) - width * height);
    }
};

Mistakes:
1：  虽然结果上说， 最终面积并没有超出。但是不表示中间计算过程的结果不超出int的范围。 因此还是需要 在计算过程中 用long  类型表示。 ( 亦即 计算 length 和 height的时候，可能会溢出 )
   因此所有的中间计算结果都要用long类型

225. Implement Stack using Queues -E

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

A:

就是简单的，每次都pop()出来，再放到最后去了

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        dq.push_back(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        deque<int> dq2;
        while(dq.size()>1)
        {
            int v = dq.front();
            dq.pop_front();
            dq2.push_back(v);
        }
        int res = dq.front();
        dq = dq2;
        return res;
    }
    
    /** Get the top element. */
    int top() {
        deque<int> dq2;
        int res;
        while(dq.size()>0)
        {
            res = dq.front();
            dq.pop_front();
            dq2.push_back(res);
        }
        dq = dq2;
        return res;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return dq.empty();
    }
    deque<int> dq;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Mistakes:

1: 第一遍的时候，理解成是用2个Stack来表示Queue了    太TMD搞笑（Diu Ren)了

226. Invert Binary Tree (easy)

Q:
Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

A:
递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return root;
        auto l = root->left;
        auto r = root->right;
        invertTree(l);
        invertTree(r);
        root->left = r;
        root->right = l;
        return root;
    }
};

211. Add and Search Word - Data structure design ----M

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.

Example:

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

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

A:
思路很直接，就是 用 Trie 解决。  (这里，仍然需要自己定义TrieNode)

*********** Solution 1： Trie *******************

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode('2',true);
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        auto runner = root;
        for(int i =0;i<word.length();i++){
            char ch = word[i];
            if(runner->map.find(ch) == runner->map.end()){
                TrieNode * tmp = new TrieNode(ch, i == word.length()-1);
                runner->map[ch] = tmp;
            }
            runner = runner->map[ch];
        }
        runner->isEnd = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return searchHelper(word, root);
    }
private:
    struct TrieNode{
        char ch;
        bool isEnd;
        unordered_map<char, TrieNode*> map;
        TrieNode(char curChar, bool end){
            ch = curChar;
            isEnd = end;
        }
    };
    bool searchHelper(string word, const TrieNode* node){        
        if(word.length() ==0)
            return node->isEnd;
        auto runner = root;
        char ch = word[0];
        if(ch == '.'){
            auto iter = node->map.begin();
            while(iter != node->map.end()){
                int subResult = searchHelper(word.substr(1), iter->second );
                if(subResult)
                    return true;
                iter++;
            }
        }
        if(node->map.find(ch) == node->map.end()){
            return false;
        }else{
            return searchHelper(word.substr(1), node->map.find(ch)->second);
        }
    }

    TrieNode *root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Mistakes:


第二次  Trie Node 用的array，而非HashMap

public class WordDictionary {
    TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        aHelper(word,root);
    }
    private void aHelper(String word, TrieNode root){
        if(word.length()==0){
            root.isLeaf = true;
            return;
        }
        char ch = word.charAt(0);
        if(root.child[ch-'a'] ==null)
            root.child[ch-'a'] = new TrieNode();
        aHelper(word.substring(1),root.child[ch-'a']);
    }
    // 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 sHelper(root,word);
    }
    private boolean sHelper(TrieNode root, String word){
        if(root == null)
            return false;
        if(word.length()==0)
            return root.isLeaf;
        char ch = word.charAt(0);
        word = word.substring(1);
        if(ch != '.'){
            return sHelper(root.child[ch-'a'], word);
        }else{
            for(int i =0;i< 26;i++){
                if( sHelper(root.child[i], word))
                    return true;
            }
            return false;
        }
    }
}
class TrieNode{
    public boolean isLeaf;
    TrieNode child[] ;
    public TrieNode(){
        child = new TrieNode[26];
        isLeaf = false;
    }
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Course Schedule II

Q:
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.


A:
仍然用了BSF

---------------初始解法-----------把constrain放到List中，以便删除---------

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int n = prerequisites.length;
        int result[] = new int[numCourses];
        int lastIndex = 0;
        List<int[]> list = new LinkedList();
        for(int i =0;i<n;i++)
            list.add(new int[]{prerequisites[i][0],prerequisites[i][1]});
        Set<Integer> findSet = new HashSet();

        boolean isFoundOne = true;
        while(isFoundOne && lastIndex < numCourses){
            isFoundOne = false;
            for(int i = 0;i<numCourses;i++){
                if(findSet.contains(i))
                    continue;
                boolean hasConstrain = false;
                for(int j = 0;j<list.size();j++){
                    int[] tmp = list.get(j);
                    if(findSet.contains(tmp[1])){
                        list.remove(j);
                        j--;
                        continue;
                    }else if(tmp[0] == i){
                        hasConstrain = true;
                        break;
                    }
                }
                if( ! hasConstrain){
                    findSet.add(i);
                    result[lastIndex++] = i;
                    isFoundOne = true;
                    break;
                }
            }
        }
        if( lastIndex == numCourses)
            return result;
        else
            return new int[]{};
    }
}

上面的解法超时。原因是不需要每次遍历所有的constrain，而只需要查看相应 class i 的constrain即可。

*************下面 是雷同于 I 的解法*************

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int result[] = new int[numCourses];
        int lastIndex = 0;
        Map<Integer, List<Integer>> map = new HashMap();
        for(int i = 0;i<numCourses;i++)
            map.put(i, new LinkedList<Integer>());

        for(int i =0;i<prerequisites.length;i++)
            map.get(prerequisites[i][0]).add(prerequisites[i][1]);

        Set<Integer> findSet = new HashSet();
    
        boolean isFoundOne = true;
        while(isFoundOne && lastIndex < numCourses){
            isFoundOne = false;
            for(Integer i : map.keySet()){
                List<Integer> constrainList = map.get(i);
                for(int j = 0;j< constrainList.size();j++){
                    if(findSet.contains(constrainList.get(j))){
                        constrainList.remove(j);
                        j--;
                    }else
                        break;
                }
                if( constrainList.isEmpty() ){
                    findSet.add(i);
                    map.remove(i);
                    result[lastIndex++] = i;
                    isFoundOne = true;
                    break;
                }
            }
        }
        return lastIndex == numCourses? result: new int[]{};
    }
}

Mistakes:
1： 上面的第二个解法中，忘记   map.remove(i)了。

Minimum Size Subarray Sum

Q:
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

A:
two pointer

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length==0)
            return 0;
        int p1 =0,p2= -1; // both are inclusive
        int minLen = Integer.MAX_VALUE;
        long sum = 0;
        while(p2<nums.length){
            if(sum < s){
                p2++;
                if(p2<nums.length)
                    sum += nums[p2];
            }else{
                minLen = Math.min(minLen, p2-p1+1);
                sum -= nums[p1++]; // do not need to check if p1<=p2, coz they s is positive
            }
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }
}

Mistakes:
 这道题的2大错误在于。
1： 刚开始用了 以前的双层循环的解法。  虽然复杂的没有变，但是写起来复杂了。 不好
2： 核心错误：  一开始p2没有确定是inclusive的，因此，开始没有设p2= -1;



***********第二遍*********

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE, pre = -1, sum = 0;
        for(int i =0;i<nums.length;i++){
            sum+= nums[i];
            if(sum<s)
                continue;
            while( sum-nums[pre+1] >= s){
                pre++;
                sum -= nums[pre];
            }
            res = Math.min(i-pre,res);
            sum = sum - nums[++pre];
        }
        return res == Integer.MAX_VALUE? 0 : res;
    }
}
 

208. Implement Trie (Prefix Tree) --M

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

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

A:

不要搞得太复杂，就是每个character一个节点就行了了。（外加HashMap）
（ empty String “”  是所有 字符串的前缀。~~~即使还没有开始存）

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *cur = root;
        for(int i =0;i<word.length();++i)
        {
            char ch = word[i];
            if(cur->chmap.find(ch) == cur->chmap.end())
            {
                Node* tmp = new Node();
                cur->chmap[ch] = tmp;
            }             
            cur = cur->chmap.at(ch);
        }
        cur->isLeaf = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *cur = root;        
        for(int i =0;i<word.length();++i)
        {
            char ch = word[i];
            if(cur->chmap.find(ch)==cur->chmap.end())
            {
                return false;
            }
            cur = cur->chmap.find(ch)->second;
        }
        return cur->isLeaf;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
                Node *cur = root;        
        for(int i =0;i<prefix.length();++i)
        {
            char ch = prefix[i];
            if(cur->chmap.find(ch)==cur->chmap.end())
            {
                return false;
            }
            cur = cur->chmap.find(ch)->second;
        }
        return true;
    }
private:
    struct Node{
        unordered_map<char,Node*> chmap;
        bool isLeaf=false;
    };
    Node * root; // root contains no char to reach it
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Mistakes:
1：  一开始加上了，如果该节点后面没有，就自己保存一个string，搞得太复杂
2： 这道题，最容易错的地方是，search和 startWith中，最后要检查是否是null节点。

Course Schedule

Q:
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
A:
就是top logical sort （CLIS上的经典代码）

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> status(numCourses, 0);// 0 as no-visited, 1 as visiting, 2 visited
        vector<vector<int>> A(numCourses, vector<int>());
        for(auto M : prerequisites)
            A[M[0]].push_back(M[1]);
        for(int i =0;i<numCourses;++i)
            if(status[i]==0 && not dfs(A, status, i))
                return false;        
        return true;
    }
private:
    bool dfs( vector<vector<int>>& A, vector<int>& S, int i)
    {
        S[i]=1;//gray out the color
        for(auto k : A[i])
        {
            if(S[k]==1)
                return false;
            if(S[k]==0 && not dfs(A,S, k))
                return false;                
        }
        S[i]=2; // mark it black
        return true;
    }
};

-------------old---------每次traversal的同时，还可以在限制条件里  删去已经满足的课程 ----------

public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
        Set<Integer> set = new HashSet();
        Map<Integer, List<Integer>>  map = new HashMap();
        for(int i =0; i<numCourses; i++)  // initialize
            map.put(i,new LinkedList<Integer>());

        for(int j =0; j<prerequisites.length;j++)  // build the set
            map.get(prerequisites[j][0]).add(prerequisites[j][1]);

        boolean foundOne = true;
        while( !map.isEmpty() && foundOne){
            foundOne = false;
            for(int key : map.keySet()){
                boolean allTaken = true;
                List constrainList = map.get(key);
                for(int k = 0;k< constrainList.size();k++) // k is the constrain class
                    if( !set.contains(constrainList.get(k))){ // get the pre-requirement for class  key
                        allTaken = false;
                        break;
                    }else{ // this constrain class (k) is already found
                        constrainList.remove(k); // delete this constrains
                        k--;
                    }
                if(allTaken){
                    foundOne = true;
                    set.add(key);
                    map.remove(key);
                    break;
                }
            }
        }
        return map.isEmpty();
    }
}
 

注意，这里，最后一个break没有加的时候，仍然会超时。


Mistakes:
 1：  当 input 为1 [] 的时候， 陷入了死循环。    原因在于忘记找到可以先上的课后，把它放到set里的同时， 还要 map.remove()了

2：   第一遍解法的时候，如果 最后一个break没有加的时候，仍然会超时。   按理说不应该呀？？？