290. Word Pattern

https://leetcode.com/problems/word-pattern/description/
Solution 1.0 Read the string one by one and compare. Use stringstream the read. (0 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        string item;
        int i=0, n=pattern.size();
        for(; getline(ss, item, ' ');i++) {
            if(i==n || mp[pattern[i]] != ms[item]) return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;

    }
Solution 1.2 Use istringstream
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        istringstream in(str);
        int i = 0, n = pattern.size();
        for(string item; in>>item;i++) {
            if(i==n || mp[pattern[i]]!=ms[item])
                return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;
    }
Solution 1.1 Convert the string to a vector<string> and compare. (3 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        vector<string> s;
        string item;
        while(getline(ss, item, ' ')) {
            s.push_back(item);
        }
        if(pattern.size() != s.size()) return false;
        for(int i=0; i<s.size();i++) {
            if(!mp.count(pattern[i]) && !ms.count(s[i])) {
                mp[pattern[i]] = i+1;
                ms[s[i]] = i+1;
            }
            if(!mp.count(pattern[i]) || !ms.count(s[i])) return false;
            if(mp[pattern[i]] != ms[s[i]]) return false;
        }
        return true;
    }

111. Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
Recursion, (9 ms)
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        int l = minDepth(root->left);
        int r = minDepth(root->right);
        if(l == 0) return r+1;
        else if(r == 0) return l+1;
        else return min(l,r) + 1;
    }
or, (6 ms)
    void inOrder(TreeNode* node, int d, int& m) {
        if(!node) return;
        if(!node->left && !node->right) {
            m = min(m, d+1);
        }
        inOrder(node->left, d+1, m);
        inOrder(node->right, d+1, m);
    }
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int m = INT_MAX;
        inOrder(root, 0, m);
        return m;
    }

20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

    bool isValid(string s) {
        if(s.size() == 0) return true;
        stack<char> st;
        for(char c : s){
            switch(c) {
                case '{': st.push(c); break;
                case '(': st.push(c); break;
                case '[': st.push(c); break;
                case '}':
                    if(st.empty()||st.top()!='{') return false;
                    else st.pop();
                    break;
                case ')':
                    if(st.empty()||st.top()!='(') return false;
                    else st.pop();
                    break;
                case ']':
                    if(st.empty()||st.top()!='[') return false;
                    else st.pop();
                    break;
            }
        }
        if(st.empty()) return true;
        else return false;
    }

438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size()) return {};
        int np = p.size();
        vector<int> stat('z'+1, 0), res;
        for(int i=0; i<np; i++) {
            stat[s[i]]++;
            stat[p[i]]--;
        }
        stat[s[np-1]]--;
        for(int i=np-1; i<s.size(); i++) {
            stat[s[i]]++;
            int j = 0;
            for(j='a'; j<'z'+1; j++) {
                if(stat[j]!=0) break;
            }
            if(j=='z'+1) res.push_back(i-np+1);
            stat[s[i-np+1]]--;
        }
        return res;
    }

507. Perfect Number

https://leetcode.com/problems/perfect-number/description/

if(num == 1) return false;
        int s = 1, N = sqrt(num);
        for(int i=2; i<=N;i++) {
            if(num%i == 0) s += i + num/i;
        }
        if(s == num) return true;
        return false;
    }

205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/description/
Solution 0. Store the same index for the last appearance of s[i] and t[i] to two arrays. If the indices for s[i] and t[i] are different, they are not isomorphic.
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        int mps[256] = {0}, mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(mps[s[i]] != mpt[t[i]])
                return false;
            mps[s[i]] = i+1;
            mpt[t[i]] = i+1;
        }
        return true;
    }
Solution 1. Use array as map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        //vector<char> mps(256, 0), mpt(256, 0);
        char mps[256] = {0};
        char mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(!mps[s[i]] && !mpt[t[i]]) {
                mps[s[i]] = t[i];
                mpt[t[i]] = s[i];
            }
            else if(mps[s[i]] != t[i] || mpt[t[i]] != s[i])
                return false;
        }
        return true;
    }
Solution 1.1 use map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        unordered_map<char,char> mp, mq;
        for(int i=0; i<s.size(); i++) {
            if(!mp.count(s[i]) && !mq.count(t[i])) {
                mp[s[i]] = t[i];
                mq[t[i]] = s[i];
            }
            else if(mp[s[i]] != t[i] || mq[t[i]] != s[i]) return false;
        }
        return true;
    }

112. Path Sum

https://leetcode.com/problems/path-sum/description/

Recursion
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && sum==root->val) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
or,
    bool preOrder(TreeNode* node, int sum, int s) {
        s += node->val;
        if(!node->left && !node->right && s==sum) return true;
        return (node->left? preOrder(node->left, sum, s):false) ||
        (node->right? preOrder(node->right, sum, s):false);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        return preOrder(root, sum, 0);
    }
Iteration
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        stack<TreeNode*> st;
        stack<int> sm;
        st.push(root);
        sm.push(0);
        TreeNode* node;
        int sn = 0;
        while(!st.empty()) {
            node = st.top();
            st.pop();
            sn = sm.top() + node->val;
            sm.pop();
            if(!node->left && !node->right && sn==sum) return true;
            if(node->right) {st.push(node->right); sm.push(sn);}
            if(node->left) {st.push(node->left); sm.push(sn);}
        }
        return false;
    }

181. Employees Earning More Than Their Managers

https://leetcode.com/problems/employees-earning-more-than-their-managers/description/
select E.Name as Employee
from Employee as E, Employee as M
where E.ManagerId = M.Id and E.Salary > M.Salary;

38. Count and Say

https://leetcode.com/problems/count-and-say/description/
Solution 1. (0 ms)
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res.push_back('0' + cnt);
                res.push_back(s[i-1]);
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res.push_back('0' + cnt);
        res.push_back(s.back());
        return res;
    }
Solution 1.1  (3 ms)
res += to_string(cnt) + s[i-1]; is slower than res.push_back('0' + cnt); res.push_back(s[i-1]);
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res += to_string(cnt) + s[i-1];
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res += to_string(cnt) + s.back();
        return res;
    }

1. Two Sum

https://leetcode.com/problems/two-sum/description/
Solution 1. Sort the index according to its value using lambda expression and search. (6 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> idx(nums.size(),0);
        for(int i=0; i<idx.size(); i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int i, int j){return nums[i]<nums[j];});
        for(int i=0, j=idx.size()-1; i<j;) {
            int x = nums[idx[i]]+nums[idx[j]];
            if(x == target) return {idx[i], idx[j]};
            else if(x>target) j--;
            else i++;
        }
        return {};

    }
Solution 2. Use a map: target - nums[i] -> i. (12 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.size()<2) return {};
        unordered_map<int,int> mp;
        mp[target-nums[0]] = 0;
        for(int i=1; i<nums.size(); i++){
            if(mp.count(nums[i])) return {mp[nums[i]], i};
            else mp[target-nums[i]] = i;
        }
        return {};
    }

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/
Solution , fast and slow runner
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }

9. Palindrome Number

https://leetcode.com/problems/palindrome-number/description/
Solution 1. Only compare half digits (fastest). Corner cases are (x!=0 && x%10 == 0).
    bool isPalindrome(int x) {
        if(x<0 || (x!=0 && x%10==0)) return false;
        int y = 0;
        while(x>y) {
            y = y*10 + (x%10);
            x /= 10;
        }
        return x == y || (x == y/10);
    }
Solution 1.1 Reverse whole number
    bool isPalindrome(int x) {
        if(x<0) return false;
        int a = x;
        int y = 0;
        while(a) {
            y = y*10 + (a%10);
            a /= 10;
        }
        return x == y;
    }
Solution 2. Covert to string and compare it to its reverse.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        string t = s;
        reverse(begin(t),end(t));
        return s == t;
    }
Solution 2.1 Two pointers for string.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        for(int i=0, j=s.size()-1;i<j; i++,j--){
            if(s[i] != s[j]) return false;
        }
        return true;
    }

26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
Solution 1.  Loop through the array, when see a none duplicated number, copy it to location s and s++.
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2) return nums.size();
        int s=1;
        for(int i=1; i<nums.size(); i++) {
            if(nums[i] != nums[i-1]) {
                nums[s] = nums[i];
                s++;
            }
        }
        nums.erase(nums.begin()+s, nums.end());
        return s;
    }
Solution 2. Remove when see duplicates. (slow)
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2) return nums.size();
        for(vector<int>::iterator it = nums.begin()+1; it<nums.end();) {
            if(*it == *(it-1)) nums.erase(it);
            else it++;
        }
        return nums.size();
    }

LeetCode Notes

Avoiding overflow
  mid = (high - low)/2 + low; instead of mid = (high + low)/2;
Remove duplicates from array, example
        int s=1;
        for(int i=1; i<nums.size(); i++) {
            if(nums[i] != nums[i-1]) {
                nums[s] = nums[i];
                s++;
            }
        }
Fast and slow runner
  141. Linked List Cycle
Counting duplicates
  38. Count and Say      26. Remove Duplicates from Sorted Array

Greatest common divisor
int gcd(int x, int y){return y ? gcd(y, x%y) : x;}
Sum of all possible combinations
$$\sum_{k=0}^{n} C_n^k$$

374. Guess Number Higher or Lower

https://leetcode.com/problems/guess-number-higher-or-lower/description/
Solution 1. Recursion.
    int guessing(int lo, int hi) {
        int mi = (hi - lo)/2 + lo;
        int c = guess(mi);
        if(c==0) return mi;
        else if(c==1) return guessing(mi+1, hi);
        else return guessing(lo, mi-1);
    }
    int guessNumber(int n) {
        return guessing(1, n);
    }
Solution 2. Iteration.
    int guessNumber(int n) {
        int mi, re, hi = n, lo = 1;
        while(true) {
            mi = (hi - lo)/2 + lo;
            re = guess(mi);
            if(re == 0) return mi;
            else if(re == 1) lo = mi + 1;
            else hi = mi - 1;
        }
    }

172. Factorial Trailing Zeroes

https://leetcode.com/problems/factorial-trailing-zeroes/description/
Solution. The number of trailing 0 of n! equals the total number of factor 5 in 1, 2, ... , n. 
Each step, n/5 is the number of integers that have at least one factor of 5 in 1,2,...,n.
    int trailingZeroes(int n) {
        if(n == 0) return 0;
        int nz = 0;
        while(n) {
            nz += n/5;
            n /= 5;
        }
        return nz;
    }

441. Arranging Coins

https://leetcode.com/problems/arranging-coins/description/
Solution 1. Subtract the s-th row from n each time.
    int arrangeCoins(int n) {
        int s = 0;
        while(n>s) {
            s++;
            n -= s;
        }
        return s;
    }
Solution 2. A full staircase with s rows and n coins has s(s+1) = 2*n.
Thus s = (-1 + sqrt(1+8*n)) / 2 = (-0.25 + sqrt(2*n + 0.25).
    int arrangeCoins(int n) {
        return floor(-0.5+sqrt((double)2*n+0.25));
    }

434. Number of Segments in a String

https://leetcode.com/problems/number-of-segments-in-a-string/description/
    int countSegments(string s) {
        int cnt = 0;
        char pre = ' ';
        for(char c: s) {
            if(c != ' ' && pre == ' ') {
                cnt++;
                pre = c;
            }
            if(c == ' ')
                pre = ' ';
        }
        return cnt;
    }

232. Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/description/
Solution 1. Use 1 stack.  Recursively push x to the bottom of the stack.
    stack<int> st;
public:
    /** Initialize your data structure here. */
    MyQueue() {
     
    }
    /** Push element x to the back of queue. */
    void push(int x) {
        if(st.empty()) {
            st.push(x);
            return;
        }
        int y = st.top();
        st.pop();
        push(x);
        st.push(y);
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x = st.top();
        st.pop();
        return x;
    }
    /** Get the front element. */
    int peek() {
        return st.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return st.empty();
    }

};
Solution 2. Use 2 stacks for input and output, respectively. move from input to output stack only when output stack is empty.
class MyQueue {
    stack<int> sti;
    stack<int> sto;
public:
    /** Initialize your data structure here. */
    MyQueue() {
     
    }
    /** Push element x to the back of queue. */
    void push(int x) {
        sti.push(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        peek();
        int x = sto.top();
        sto.pop();
        return x;
    }
    /** Get the front element. */
    int peek() {
        if(sto.empty()) {
            while(!sti.empty()) {
                sto.push(sti.top());
                sti.pop();
            }
        }
        return sto.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return sti.empty() && sto.empty();
    }
};

119. Pascal's Triangle II

https://leetcode.com/problems/pascals-triangle-ii/description/
Solution 1. Iteration
rowIndex        row
i = 0           1 0 0 0 0
i = 1           1 1 0 0 0
i = 2           1 2 1 0 0
i = 3           1 3 3 1 0
i represents the ith row of the pascals triangle
j is the index on ith row, index loops from high to low
    vector<int> getRow(int rowIndex) {
        vector<int> r(rowIndex+1, 0);
        r[0] = 1;
        for(int i=1; i<rowIndex+1; i++) {
            for(int j=i; j>=1; j--)
                r[j] += r[j-1];
        }
        return r;

    }
Solution 2. recursion
    vector<int> getRow(int rowIndex) {
        if(rowIndex == 0) return {1};
        vector<int> r = getRow(rowIndex - 1);
        r.push_back(1);
        for(int i=1, n, m=r[0]; i<r.size()-1; i++) {
            n = r[i];
            r[i] = m + r[i];
            m = n;
        }
        return r;
    }