在职刷题打卡

4/19
1. Continuous Subarray Sum;
2. Subarray Sum Equals K
3. Expression Add Operators
4. Remove Invalid Parentheses
5. Add Binary

4/20
Add and Search Word - Data structure design

就刷了一题

Add and Search Word - Data structure design。 这个trie的解法竟然只比5%的submissions快，难道可以再优化时间吗？

struct Node{
    bool isWord;
    unordered_map<char, Node*> children;
    Node(){
        isWord = false;
    }
};
class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Node();
    }
   
    /** Adds a word into the data structure. */
    void addWord(string word) {
        Node* dummy = root;
        for(char c: word){
            if(!dummy->children[c])
                dummy->children[c] = new Node();
            dummy = dummy->children[c];
        }
        dummy->isWord = 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) {
        Node* dummy = root;
        return help(word, 0, dummy);
    }
   
    bool help(string &word, int id, Node* root){
        if(!root)
            return false;
        if(id == word.size())
            return root->isWord;
        unordered_map<char, Node*> cur_children = root->children;
        char c = word[id];
        if(c != '.')
            return help(word, id + 1, cur_children[c]);
        for(auto it = cur_children.begin(); it != cur_children.end(); it++){
            if(help(word, id + 1, it->second))
                return true;
        }
        return false;
    }
private:
    Node* root;
};

4/21

• Search in Rotated Sorted Array:  compare A[mid] vs target; then A[mid] vs A[left]
• Valid Parentheses
  

Read N Characters Given Read4 II - Call multiple times

还没弄懂题目。。。

4/22

• Read N Characters Given Read4 II - Call multiple times
• Remove duplicates from array
  

4/23
1. number of digit ones  
2. 3sum (no sort)
3. Max Consecutive Ones III
4. Minimum Area Rectangle
5. Design Circular Queue
6. Search a 2D Matrix II
7. Range Sum Query 2D - Immutable
8. Subarray Sum Equals K
9. Random Pick with Weight

need to review soon:
Search a 2D Matrix II
Design Circular Queue
Random Pick with Weight

4/24

• Custom Sort String
• Word Pattern
• Word Pattern II
• Walls and Gates