686. Repeated String Match

   bool isSubStr(int n, string& A, string& B) {
        if(n*A.size()<B.size()) return false;
        string a = "";
        for(int i=0; i<n; i++) a += A;
        for(int i=0; i<A.size(); i++) {
            int j;
            for(j=0; j<B.size(); j++) {
                if(a[i+j] != B[j]) break;
            }
            if(j==B.size()) return true;
        }
        return false;
    }
    int repeatedStringMatch(string A, string B) {
        if(B.size() == 0) return 1;
        if(A.size() == 0) return -1;
        int na = A.size(), nb = B.size();
        int k = nb/na;
        for(int n=k; n<=k+2; n++) {
            if(isSubStr(n, A, B)) return n;
        }
        return -1;
    }

687. Longest Univalue Path

    int len(TreeNode* node, int pa, int& mx) { // pa is the value of parent node
        if(!node) return 0;
        int l = len(node->left, node->val, mx);
        int r = len(node->right, node->val,mx);
        mx = max(mx, l+r);
        if(node->val == pa) return 1+max(l,r);
        else return 0;
    }
    int longestUnivaluePath(TreeNode* root) {
        if(!root) return 0;
        int mx = 0;
        // root doesn't have parent node, pick any value that is different
        len(root, root->val-1, mx);
        return mx;
    }

526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/

    void count(int N, vector<bool>& fil, int& res) {
        if(N==0) {res++; return;}
       
        for(int i=fil.size()-1; i>=0; i--) {
            if(!fil[i] && (N%(i+1)==0 || (i+1)%N==0)){
                fil[i] = true;
                count(N-1, fil, res);
                fil[i] = false;
            }
        }
    }
    int countArrangement(int N) {
        int res = 0;
        vector<bool> fil(N, false);
        count(N, fil, res);
        return res;
    }

515. Find Largest Value in Each Tree Row

https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
Solution 1. Recursion.
    void levelOrder(TreeNode* node, vector<int>& res, int lev) {
        if(!node) return;
        if(res.size() == lev) res.push_back(node->val);
        else
            res[lev] = res[lev] > node->val ? res[lev] : node->val;
        levelOrder(node->left, res, lev+1);
        levelOrder(node->right, res, lev+1);
    }
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        levelOrder(root, res, 0);
        return res;
    }
Solution 2. 
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        int mx = INT_MIN;
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr) {
                res.push_back(mx);
                mx = INT_MIN;
                if(!q.empty())
                    q.push(nullptr);
            }
            else {
                mx = mx>node->val ? mx : node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return res;
    }

553. Optimal Division

https://leetcode.com/problems/optimal-division/description/
    string optimalDivision(vector<int>& nums) {
        if(nums.size()==0) return "";
        if(nums.size()==1) return to_string(nums[0]);
        string res = to_string(nums[0]);
        if(nums.size()==2) return res+"/"+to_string(nums[1]);
        res += "/(";
        for(int i=1; i<nums.size(); i++) {
            res += to_string(nums[i]) + "/";
        }
        res[res.size()-1] = ')';
        return res;
    }

647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/
Solution 1. Moving the center of the palindrome and count.
    int countSubstrings(string s) {
        int n = s.size();
        int res = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; i-j>=0 && i+j<n; j++) {
                if(s[i-j] == s[i+j]) res++;
                else break;
            }
            for(int j=0; i-j>=0 && i+j+1<n; j++) {
                if(s[i-j] == s[i+j+1]) res++;
                else break;
            }
        }
        return res;
    }
Solution 2. Recursion. Slow because of duplicated comparisons.
    int count(string& s, int n) {
        if(n<2) return n;
        int m = count(s, n-1);
        for(int lo = 0; lo<n; lo++) {
            int i=lo, j = n-1;
            for(; i<=j; i++, j--) {
                if(s[i]!=s[j]) break;
            }
            m += i>j;
        }
        return m;
    }
    int countSubstrings(string s) {
        return count(s, s.size());
    }

540. Single Element in a Sorted Array

https://leetcode.com/problems/single-element-in-a-sorted-array/description/
    int singleNonDuplicate(vector<int>& nums) {
        for(int i=1;i<nums.size();i+=2) {
            if(nums[i] != nums[i-1]) return nums[i-1];
        }
        return nums.back();
    }
or use XOR
    int singleNonDuplicate(vector<int>& nums) {
        int res = 0;
        for(int n : nums) {
            res ^= n;
        }
        return res;
    }

406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/description/
Solution 1. Sort and insert
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> res;
        sort(people.begin(), people.end(),
             [&](pair<int, int> a, pair<int, int> b){
                 if(a.first!=b.first)return a.first>b.first;
                 else return a.second<b.second;
             });
        for(int i=0; i<people.size(); i++) {
            res.insert(res.begin()+people[i].second, people[i]);
        }
        return res;
    }
The sort could be:
auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2) { 

    return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); 

};

sort(people.begin(), people.end(), comp);

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/
Solution 1. swap number i to index i-1
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int i=0;
        while(i<nums.size()) {
            if(nums[i] != nums[nums[i]-1])
                swap(nums[i], nums[nums[i]-1]);
            else i++;
        }
        for(int i=0; i<nums.size(); i++) {
            if(i+1 != nums[i]) res.push_back(nums[i]);
        }
        return res;
    }
Solution 2. Mark by +/-
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i=0; i<nums.size(); i++) {
            nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
            if(nums[abs(nums[i])-1]>0) res.push_back(abs(nums[i]));
        }
        return res;
    }
Solution 3. counting number nums[i] by adding n to index i-1
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i=0; i<n; i++) {
            nums[(nums[i]-1)%n] += n;
        }
        for(int i=0; i<n; i++) {
            if(nums[i]>2*n) res.push_back(i+1);
        }
        return res;
    }

513. Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/description/
Solution 1
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        int res;
        TreeNode* last = nullptr;
        while(q.size()>1) {
            if(last == nullptr) res = q.front()->val;
            last = q.front();
            q.pop();
            if(last == nullptr) {
                q.push(nullptr);
            }
            else {
                if(last->left) q.push(last->left);
                if(last->right) q.push(last->right);
            }
        }
        return res;
    }
Solution 2. Recursion
    void findLeft(TreeNode* node, int& mx, int& maxDep, int dep) {
        if(!node) return;
        if(maxDep < dep) {
            maxDep = dep;
            mx = node->val;
        }
        findLeft(node->left, mx, maxDep, dep+1);
        findLeft(node->right, mx, maxDep, dep+1);
    }
    int findBottomLeftValue(TreeNode* root) {
        int mx = root->val, maxDep = 0;
        findLeft(root, mx, maxDep, 0);
        return mx;
    }

338. Counting Bits

https://leetcode.com/problems/counting-bits/description/
    vector<int> countBits(int num) {
        vector<int> res;
        for(int i=0; i<=num; i++) {
            int n = i;
            int b = 0;
            while(n) {
                b += n&1;
                n >>= 1;
            }
            res.push_back(b);
        }
        return res;
    }

419. Battleships in a Board

https://leetcode.com/problems/battleships-in-a-board/description/
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        for(int i=0; i<board.size(); i++)
            for(int j=0; j<board[0].size(); j++) {
                if(board[i][j] == 'X') {
                    if(i!=0 && j!=0)
                        res += (board[i-1][j] != 'X' && board[i][j-1] != 'X');
                    else if(i==0 && j!=0)
                        res += (board[i][j-1] != 'X');
                    else if(i!=0 && j==0)
                        res += (board[i-1][j] != 'X');
                    else res++;
                }
            }
        return res;
    }

537. Complex Number Multiplication

https://leetcode.com/problems/complex-number-multiplication/description/
Solution 1.stringstream
    string complexNumberMultiply(string a, string b) {
        int ar, ai, br, bi;
        char buff;
        stringstream ssa(a), ssb(b), res;
        ssa >> ar >> buff >> ai >> buff;
        ssb >> br >> buff >> bi >> buff;
        res << ar*br - ai*bi << "+" << ar*bi + br*ai << "i";
        return res.str();
    }
Solution 2. strtok
    string complexNumberMultiply(string a, string b) {
        string ars = strtok((char*)a.c_str(), "+i");
        string ais = strtok(NULL, "+i");
        string brs = strtok((char*)b.c_str(), "+i");
        string bis = strtok(NULL, "+i");
        long ar = stol(ars);
        long ai = stol(ais);
        long br = stol(brs);
        long bi = stol(bis);
        long re = ar*br - ai*bi;
        long im = ar*bi + ai*br;
     
        return to_string(re)+"+"+to_string(im)+"i";
    }

654. Maximum Binary Tree

https://leetcode.com/problems/maximum-binary-tree/description/
Solution 1.
use a vector to keep part of tree nodes in decreasing order.
keep popping the vector until empty or a bigger number.
The bigger number (if exists) is current number's root, and the last popped number (if exist) is current number's right child and it is the parent of the number before last popped. 
push current number into the vector.
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> v;
        for(int n : nums) {
            TreeNode* node = new TreeNode(n);
            while(!v.empty() && v.back()->val<n) {
                node->left = v.back();
                v.pop_back();
            }
            if(!v.empty()) v.back()->right = node;
            v.push_back(node);
        }
        return v.front();
    }
Solution 2. Recursion
    TreeNode* construct(vector<int>& nums, int lo, int hi) {
        if(lo>hi) return nullptr;
        int mx = nums[lo], ix = lo;
        for(int i=lo+1; i<=hi;i++) if(nums[i]>mx) {
            mx = nums[i];
            ix = i;
        }
        TreeNode* node = new TreeNode(mx);
        node->left = construct(nums, lo, ix-1);
        node->right = construct(nums, ix+1, hi);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size()-1);
    }

535. Encode and Decode TinyURL

https://leetcode.com/problems/encode-and-decode-tinyurl/description/
class Solution {
    unordered_map<string, string> encodeMap;
    unordered_map<string, string> decodeMap;
    string dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if(encodeMap.count(longUrl)) return encodeMap[longUrl];
        string shortUrl = "http://tinyurl.com/";
        int n = encodeMap.size(), nd = dict.size();
        while(n) {
            shortUrl += dict[n%nd];
            n /= nd;
        }
        encodeMap[longUrl] = shortUrl;
        decodeMap[shortUrl] = longUrl;
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return decodeMap[shortUrl];
    }
};

176. Second Highest Salary

https://leetcode.com/problems/second-highest-salary/description/
select max(Salary) as SecondHighestSalary
from Employee
where Salary < (select max(Salary) from Employee)

select (
  select distinct Salary from Employee order by Salary Desc limit 1 offset 1
) as SecondHighestSalary

665. Non-decreasing Array

https://leetcode.com/problems/non-decreasing-array/description/
    bool checkPossibility(vector<int>& nums) {
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MAX);
        int dec = 0, idx = -1;
        for(int i=1; i<nums.size(); i++) {
            if(nums[i-1]>nums[i]) {
                dec++;
                if(dec == 1) idx = i;
            }
            if(dec>1) return false;
        }
        if(dec == 1)
                return (idx>1 && nums[idx]>=nums[idx-2])
                    || (idx+1<nums.size() && nums[idx+1]>=nums[idx-1]);
        return true;
    }

196. Delete Duplicate Emails

https://leetcode.com/problems/delete-duplicate-emails/description/
delete p1
from Person p1, Person p2
where p1.Email = p2.Email
and p1.Id > p2.Id

Solution 2.
delete from Person where id not in( select t.id from ( select min(id) as id from Person group by email ) t )

479. Largest Palindrome Product

https://leetcode.com/problems/largest-palindrome-product/description/
    long getCandidate(int n) {
        string s = to_string(n);
        reverse(s.begin(), s.end());
        return stol(to_string(n) + s);
    }
    int largestPalindrome(int n) {
        if(n==1) return 9;
        int mx = pow(10,n) - 1;
        int mi = pow(10,n-1);
        for(int i=mx; i>=mi; i--) {
            long c = getCandidate(i);
            for(long j=mx; j*j>=c; j--) {
                if(c%j == 0 && c/j >= mi) {
                    return c%1337;
                }
            }
        }
        return -1;
    }

682. Baseball Game

      int calPoints(vector<string>& ops) {
        int res = 0;
        stack<int> pts;
        for(int i=0; i<ops.size(); i++) { // initialize i = 0
            if(ops[i] == "C") {
                        int s = pts.top();
                        res -= s;
                        pts.pop();
            }
            else if(ops[i] == "D") {
                        int s = 2 * pts.top();
                        res += s;
                        pts.push(s);
            }
            else if(ops[i] == "+") {
                        int s1 = pts.top();
                        pts.pop();
                        int s2 = pts.top() + s1;
                        res += s2;
                        pts.push(s1);
                        pts.push(s2);
            }
            else {
                    int s = atoi(ops[i].c_str());
                    res += s;
                    pts.push(s);
            }   
        }
        return res;
    }

681. Next Closest Time

bool isValid(string time) {
    if(stoi(time.substr(0,2))>23) return false;
    if(stoi(time.substr(3,2))>59) return false;
    return true;
}
string nextClosestTime(string time) {
    string t = time;
    string s = {t[0], t[1], t[3], t[4]};
    vector<string> v;
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            for(int k=0; k<4; k++)
                for(int l=0; l<4; l++) {
                    t[0] = s[i], t[1] = s[j], t[3] = s[k], t[4] = s[l];
                    if(isValid(t)) v.push_back(t);
                }
    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());
    auto it = find(v.begin(), v.end(), time);
    if(it+1 == v.end()) return *v.begin();
    else return *(it+1);
}

7. Reverse Integer

https://leetcode.com/problems/reverse-integer/description/
    int reverse(int x) {
        if(x == INT_MIN) return 0;
        if(x < 0) return -reverse(-x);
        int res = 0;
        while(x) {
            int r = x%10;
            if(res > INT_MAX/10) return 0;
            res = res * 10 + r;
            x /= 10;
        }
        return res;
    }

193. Valid Phone Numbers

https://leetcode.com/problems/valid-phone-numbers/description/
^   start with
$   end with

basic regex
(   {   |    are regular characters matching ( { |
\(  \{  \| ...  are special operations
grep '^\([0-9]\{3\}-\|([0-9]\{3\}) \)[0-9]\{3\}-[0-9]\{4\}$' file.txt

extended regex
(   {   |    are special operations
\(  \{  \| ...  are escape characters matching ( { |
grep -E '^([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}$' file.txt

189. Rotate Array

https://leetcode.com/problems/rotate-array/description/
Solution 1. O(1) space, 3 reversions
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        if(N ==0 || k%N ==0) return;
        k = k%N;
        reverse(begin(nums), begin(nums)+N-k);
        reverse(begin(nums)+N-k, end(nums));
        reverse(begin(nums), end(nums));
    }
Solution 2. O(1) space, keep rotating one by one until total number of rotating = nums.size()
    void rotate1(vector<int>& nums, int k) {
        int N = nums.size();
        if(N ==0 || k%N ==0) return;
        k = k%N;
        int cnt = 0, iStart = 0, iCurrt = 0, numRot = nums[0], tmp;
        while(cnt<N) {
            do{
                iCurrt = (iCurrt + k)%N;
                tmp = nums[iCurrt];
                nums[iCurrt] = numRot;
                numRot = tmp;
                cnt++;
            }while(iStart != iCurrt);
           
            iStart++;
            iCurrt = iStart;
            numRot = nums[iCurrt];
        }

    }
Solution 3.
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        k = k%N;
        if(k == 0) return;
        vector<int> nk(k);
        for(int i=0; i<k; i++) nk[i] = nums[N-k+i];
     
        for(int i=N-k-1; i>=0; i--) {
            nums[i+k] = nums[i];
        }

        for(int i=0; i<k; i++) nums[i] = nk[i];
    }

596. Classes More Than 5 Students

https://leetcode.com/problems/classes-more-than-5-students/description/
select class
from courses
group by class
having count(distinct student) > 4

278. First Bad Version

https://leetcode.com/problems/first-bad-version/description/
    int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while(lo<hi){
            int mid = lo +(hi - lo)/2;
            if(isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

168. Excel Sheet Column Title

https://leetcode.com/problems/excel-sheet-column-title/description/

    string convertToTitle(int n) {
        string s = "";
        while(n) {
            n--;
            s = char('A' + n%26) + s;
            n /= 26;
        }
        return s;
    }

125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/
    bool isPalindrome(string s) {
        if(s.size()<2) return true;
        for(int i=0, j=s.size()-1; i<j;) {
            char a = tolower(s[i]);
            char b = tolower(s[j]);
            if(!(a>='a'&&a<='z') && !(a>='0'&&a<='9')) { i++; continue;}
            if(!(b>='a'&&b<='z') && !(b>='0'&&b<='9')) { j--; continue;}
            if(a!=b) return false;
            i++;
            j--;
        }
        return true;
    }

204. Count Primes

https://leetcode.com/problems/count-primes/description/
Solution 1. Use Sieve of Eratosthenes (13 ms)
    int countPrimes(int n) {
        if(n<=2) return 0;
        bool s[n] = {false}; // faster than vector<bool> s(n,false);
        int np = 1;
        for(int i=3; i<n; i+=2) {
            if(!s[i]) {
                np++;
                if(i>n/i) continue;
                for(int j=i*i, step=i<<1; j<n; j+=step) {
                    //set step = 2*i to ignore even numbers
                    s[j] = true;
                }
            }
        }
        return np;
    }

414. Third Maximum Number

https://leetcode.com/problems/third-maximum-number/description/
Solution 1. Use a set
    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for(int n:nums){
            if(top3.size()<3 || n> *top3.begin())
                top3.insert(n);
            if(top3.size()>3) top3.erase(top3.begin());
        }
        return (top3.size() == 3) ? *top3.begin() : *top3.rbegin();
    }
Solution 2. Use pointers
    int thirdMax(vector<int>& nums) {
        int *p1 = &nums[0], *p2 = nullptr, *p3 = nullptr;
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] > *p1) {
                p3 = p2;
                p2 = p1;
                p1 = &nums[i];
            }
            else if(nums[i] == *p1) continue;
            else if(!p2) p2 = &nums[i];
            else if(nums[i] < *p1 && nums[i] > *p2) {
                p3 = p2;
                p2 = &nums[i];
            }
            else if(nums[i] == *p2) continue;
            else if(!p3) p3 = &nums[i];
            else if(nums[i] < *p2 && nums[i] > *p3 ) {
                p3 = &nums[i];
            }
        }
        if(p3) return *p3;
        else return *p1;
    }
Solution 3
    int thirdMax(vector<int>& nums) {
        int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN, i = 0;
        for(int n : nums) {
            if(n > m1) {
                m3 = m2;
                m2 = m1;
                m1 = n;
                i++;
            }
            else if(n < m1 && n > m2) {
                m3 = m2;
                m2 = n;
                i++;
            }
            else if(n < m2 && n > m3 ) {
                m3 = n;
                i++;
            }
            else if(n == INT_MIN) i++;
        }
        if(m1>m2 && m2>m3 && i>=3) return m3;
        else return m1;
    }

69. Sqrt(x)

https://leetcode.com/problems/sqrtx/description/
Solution 1.
    int mySqrt(int x) {
        if(x == 0) return 0;
        int n = 0;
        for(int m = 1<<30; m!=0; m>>=1){
            int r = n|m;
            while(r>x/r) {
                m >>= 1;
                r = n|m;
            }
            n |= m;
        }
        return n;
    }
Solution 2
    int mySqrt(int x) {
        if(x == 0) return 0;
        double y = log10(x)/2.;
        return (int) pow(10.,y);
    }

532. K-diff Pairs in an Array

https://leetcode.com/problems/k-diff-pairs-in-an-array/description/
    int findPairs(vector<int>& nums, int k) {
        if(k<0) return 0;
        unordered_map<int,int> mp;
        int res = 0;
        for(auto n: nums) mp[n]++;
        if(k==0) {
            for(auto &x : mp) {
                res += (x.second>1);
            }
            return res;
        }
        for(auto &x : mp) {
            if(mp.count(x.first+k)) res++;
        }
        return res;
    }

677. Map Sum Pairs

https://leetcode.com/problems/map-sum-pairs/description/

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

class MapSum {
    unordered_map<string,int> mp;
public:
    /** Initialize your data structure here. */
    MapSum() {
    }
    void insert(string key, int val) {
        mp[key] = val;
    }
    int sum(string prefix) {
        int s = 0;
        for(auto & x: mp) {
            if(x.first.size()>=prefix.size()) {
                int i;
                for(i=0; i<prefix.size(); i++) {
                    if(x.first[i]!=prefix[i]) break;
                }
                if(i==prefix.size()) s += x.second;
            }
        }
        return s;
    }
};

680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/description/
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
    bool valid(string& s, int i, int j, int del) {
        if(del == 2) return false;
        if(i>=j) return true;
        if(s[i]!=s[j])
            return valid(s, i+1, j, del+1) || valid(s, i, j-1, del+1);
        else return valid(s, i+1, j-1, del);
    }
    bool validPalindrome(string s) {
        return valid(s, 0, s.size()-1, 0);
    }

679. 24 Game

https://leetcode.com/problems/24-game/description/
You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.
Solution 1: Recursion.
    vector<double> products(vector<int>& n, int L, int R) {
        if(L == R) return {(double)n[L]};
        vector<double> res;
        for(int i=L; i<R; i++) {
            vector<double> resl = products(n, L, i);
            vector<double> resr = products(n, i+1, R);
            for(auto l: resl) {
                for(auto r: resr) {
                    res.push_back(l+r);
                    res.push_back(l-r);
                    res.push_back(l*r);
                    if(abs(r)>1e-8)
                        res.push_back(l/r);
                }
            }
        }
        return res;
    }
    bool judgePoint24(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        do {
            vector<double> res = products(nums, 0, nums.size()-1);
            for(auto f: res) {
                if(abs(f-24.0)<1e-6) return true;
            }
        } while(next_permutation(nums.begin(), nums.end()));
        return false;

    }

678. Valid Parenthesis String

Solution 1. Use stacks. Storing the index of each char.
    bool checkValidString(string s) {
        stack<int> st;
        stack<int> blk;
        for(int i=0; i<s.size(); i++) {
            char c = s[i];
            if(c == '(') st.push(i);
            else if(c == '*') blk.push(i);
            else {
                if(st.empty() && blk.empty()) return false;
                if(!st.empty()) st.pop();
                else blk.pop();
            }
        }
        if(st.size()>blk.size()) return false;
        while(!st.empty() && !blk.empty()) {
            if(blk.top()<st.top()) return false;
            st.pop();
            blk.pop();
        }
        return st.empty();
    }
Solution 2. Counting the remaining '(' at each step.
    bool check(string& s, int i=0, int cnt=0) {
        if(cnt < 0) return false;
        if(i==s.size()) return cnt == 0;
        if(s[i] == '(') return check(s, i+1, cnt+1);
        else if(s[i] == ')') return check(s, i+1, cnt-1);
        else return check(s, i+1, cnt)
            || check(s, i+1, cnt+1)
            || check(s, i+1, cnt-1);
    }
    bool checkValidString(string s) {
        return check(s);
    }

28. Implement strStr()

https://leetcode.com/problems/implement-strstr/description/
Solution. KMP search.
    vector<int> calcLPS(const string& pat) {
        vector<int> lps(pat.size(), 0);
        int len = 0;
        lps[0] = 0;
        int i = 1;
        while(i<pat.size()) {
            if(pat[len] == pat[i]) {
                len++;
                lps[i++] = len;
            }
            else {
                if(len != 0)
                    len = lps[len-1];
                else
                    lps[i++] = 0;
            }
        }
        return lps;
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        if(haystack.size() < needle.size()) return -1;
        vector<int> lps = calcLPS(needle);
        int i = 0;
        int j = 0;
        while(i<haystack.size()) {
            if(haystack[i] == needle[j]) {
                i++;
                j++;
            }
            if(j == needle.size()) return i-j;
            else if(i<haystack.size() && haystack[i] != needle[j]) {
                if(j != 0) j = lps[j-1];
                else i++;
            }
        }
        return -1;
    }

197. Rising Temperature

https://leetcode.com/problems/rising-temperature/description/
select w1.Id
from Weather as w1, Weather as w2
where TO_DAYS(w1.DATE) = TO_DAYS(w2.DATE) + 1
and W1.Temperature > W2.Temperature;
or,
select w1.Id
from Weather as w1, Weather as w2
where DATEDIFF(w1.DATE,w2.DATE) = 1
and W1.Temperature > W2.Temperature;

155. Min Stack

https://leetcode.com/problems/min-stack/description/
Solution 1. One stack
class MinStack {
    stack<int> dst;
    int mi = INT_MAX;
public:
    /** initialize your data structure here. */
    MinStack() {
     
    }
    void push(int x) {
        if(x <= mi) {
            dst.push(mi);
            mi = x;
        }
        dst.push(x);
    }
    void pop() {
        if(dst.top() == mi) {
            dst.pop();
            mi = dst.top();
        }
        dst.pop();
    }
 
    int top() {
        return dst.top();
    }
 
    int getMin() {
        return mi;
    }
};
or, push the min every time pushing a new element.
class MinStack {
    stack<int> dst;
    int mi = INT_MAX;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        dst.push(mi);
        if(x <= mi) mi = x;
        dst.push(x);
    }
    void pop() {
        dst.pop();
        mi = dst.top();
        dst.pop();
    }
    int top() {
        return dst.top();
    }
    int getMin() {
        return mi;
    }
Solution 2. Two stacks.
class MinStack {
    stack<int> dst;
    stack<int> mst;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        int mi;
        if(dst.empty()) mi = x;
        else mi = min(mst.top(), x);
        mst.push(mi);
        dst.push(x);
    }
    void pop() {
        dst.pop();
        mst.pop();
    }
    int top() {
        return dst.top();
    }
    int getMin() {
        return mst.top();
    }
};

581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
    int findUnsortedSubarray(vector<int>& nums) {
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MAX);
        int l = 0, h = nums.size() - 1;
        for(int i=1; i<nums.size()-1; i++ ) {
            if(nums[i]<nums[l]) {
                while(nums[i]<nums[l]) l--;
            }
            else if(l == i-1) l++;
        }
        for(int i=nums.size()-2; i>=0; i-- ) {
            if(nums[i]>nums[h]) {
                while(nums[i]>nums[h]) h++;
            }
            else if(h == i+1) h--;
        }
        return max(h-l-1, 0);
    }

190. Reverse Bits

https://leetcode.com/problems/reverse-bits/description/
    uint32_t reverseBits(uint32_t n) {
        int res = 0, f = 1;
        for(int i=0; i<32; i++, n >>= 1) {
            res <<= 1;
            res |= (n & 1);
        }
        return res;
    }

475. Heaters

https://leetcode.com/problems/heaters/description/
int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int maxRg = 0, j = 0;
        for(int i=0; i<houses.size(); i++) {
            int h, minh = abs(heaters[j] - houses[i]);
            while(j+1<heaters.size()) {
                h = abs(heaters[j+1] - houses[i]);
                if(h<=minh) {
                    minh = min(minh, h);
                    j++;
                }
                else {
                    break;
                }
            }
            maxRg = max(maxRg, minh);
        }
        return maxRg;
    }

303. Range Sum Query - Immutable

https://leetcode.com/problems/range-sum-query-immutable/description/
Solution 1. Because:
You may assume that the array does not change.
There are many calls to sumRange function.
It is better to calculate sum when initialize the object.
class NumArray {
    vector<int> sm;
public:
    NumArray(vector<int> nums) {
        sm.resize(nums.size()+1, 0);
        for(int i=0; i<nums.size(); i++)
            sm[i+1] = sm[i] + nums[i];
    }
 
    int sumRange(int i, int j) {
        return sm[j+1] - sm[i];
    }
};
Solution 2. do not calculate sum at initialization. Much slower.
class NumArray {
    vector<int> n;
public:
    NumArray(vector<int> nums) {
        n = nums;
    }
 
    int sumRange(int i, int j) {
        int s = 0;
        for(int k=i; k<=j; k++)
            s += n[k];
        return s;
    }

};

605. Can Place Flowers

https://leetcode.com/problems/can-place-flowers/description/
Solution 1. add 0 to both side for convenience.
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(n == 0) return true;
        if(flowerbed.size() == 0) return false;
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        for(int i=1; i<flowerbed.size()-1; i++) {
            if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0) {
                i++;
                n--;
            }
        }
        return n<=0;
    }
Solution 2.
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(n == 0) return true;
        if(flowerbed.size() == 0) return false;
        int z = flowerbed[0] ? 0 : 2, res = 0; // a 0 at beginning counted as 2
        for(int i=1; i<flowerbed.size(); i++) {
            if(flowerbed[i] == 1 && flowerbed[i-1] == 0) {
                res += (z-1)/2;
                z = 0;
                if(res>=n) return true;
            }
            else if(flowerbed[i] == 0 && flowerbed[i-1] == 1) {
                z = 1;
            }
            else if(flowerbed[i] == 0) z++;
            else continue;
        }
        res += z/2;
        if(res>=n) return true;
        return false;
    }

400. Nth Digit

https://leetcode.com/problems/nth-digit/description/
    int findNthDigit(int n) {
        vector<int> sd(9,0);
        int d;
        for(d=1; d<9; d++) {
            // d is the length (digits of a single number) of a number
            // sd is the total digits for length from 1 to d
            sd[d] = d*pow(10, d) - (pow(10,d)-1)/9;
            if(sd[d]>=n) break;
        }
        // the length of number prior to the current length
        int d1 = d-1;
        // total digits for length d is n - total digits for length from 1 to d-1
        n -= sd[d1];
        // the number is i-th of numbers with length d
        int i = (n-1)/d;
        // the first number of length d is
        int a = pow(10, d1);
        // what is the number
        a += i;
        // the digit is the i-th digit of the number a
        i = n - i*d;
        // return the digit
        return (a/(int)(pow(10,d-i))) % 10;
    }

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/
Solution 1. 
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* p = headA, *q = headB;
        while(p != q) {
            p = p? p->next : headB;
            q = q? q->next : headA;
        }
        return p;

    }
Solution 2. Counting the length of the lists.
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* p, *q;
        int na = 0, nb = 0, nd = 0;
        p = headA;
        while(p) {
            na++;
            p = p->next;
        }
        p = headB;
        while(p) {
            nb++;
            p = p->next;
        }
        if(na>nb) {
            p = headA;
            q = headB;
        }
        else {
            p = headB;
            q = headA;
        }
        nd = abs(na - nb);
        while(nd>0) {
            p = p->next;
            nd--;
        }
        while(p != q) {
            p = p->next;
            q = q->next;
        }
        return p;
    }

14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/description/
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0 || strs[0].size() == 0) return "";
        for(int j=0; j<strs[0].size(); j++) {
            for(int i=1; i<strs.size(); i++) {
                if(j>=strs[i].size() || strs[0][j] != strs[i][j]) {
                    return strs[0].substr(0,j);
                }
            }
        }
        return strs[0];
    }

58. Length of Last Word

https://leetcode.com/problems/length-of-last-word/description/
    int lengthOfLastWord(string s) {
        if(s.size() == 0) return 0;
        int i = s.size()-1;
        while(i>=0 && s[i] == ' ') i--;
        if(i == -1) return 0;
        int j;
        for(j=i; j>=0; j--) {
            if(s[j] == ' ') break;
        }
        return  i-j;
    }

633. Sum of Square Numbers

https://leetcode.com/problems/sum-of-square-numbers/description/
    bool judgeSquareSum(int c) {
        int a = sqrt((double) c / 2.0);
        int b = a;
        int c2 = sqrt(c);
        while(a>=0 && b<=c2) {
            int s = a*a + b*b;
            if(s<c) b++;
            else if(s>c) a--;
            else return true;
        }
        return false;
    }

88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/description/
Merge from high index.
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(nums2.size() == 0) return;
        for(int i=m-1, j=n-1, k=m+n-1; k>=0; k--) {
            if(i<0) {
                nums1[k] = nums2[j--];
                continue;
            }
            if(j<0) return;
            if(nums1[i]<=nums2[j]) nums1[k] = nums2[j--];

            else nums1[k] = nums1[i--];
        }    
    }

219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/description/
Solution 1. Use map to store the index for each distinct number.
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size()<2) return false;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++) {
            if(mp.count(nums[i]))
                if(i - mp[nums[i]]<=k) return true;
            mp[nums[i]] = i;
        }
        return false;
    }
Solution 2. Use unordered_set to maintain a set containing nums[i-k,...,i-1].
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size()<2 || k<=0) return false;
        unordered_set<int> st;
        for(int i=0; i<nums.size(); i++) {
            if(st.count(nums[i]))
                return true;
            else {
                if(i-k>=0) st.erase(nums[i-k]);
                st.insert(nums[i]);
            }
        }
        return false;
    }

203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/description/
Solution 0. Iteration 1. use pointer to a pointer.
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        ListNode** pn = &head;
        while(*pn) {
            if((*pn)->val == val) {
                *pn = (*pn)->next;
            }
            else {
                pn = &(*pn)->next;
            }
        }
        return head;
    }
Solution 1. Recursion 0
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        head->next = removeElements(head->next, val);
        ListNode* node = head;
        if(head->val == val) {
            head = head->next;
        }
        return head;
    }
Solution 1.1 Recursion 1
    void remove(ListNode*& node, int val) {
        if(!node) return;
        if(node->val == val) {
            node = node->next;
            remove(node, val);
        }
        else remove(node->next, val);
    }
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        remove(head, val);
        return head;
    }
Solution 2. Iteration 2
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        ListNode* node = head, *pre = head;
        while(node) {
            if(node->val == val) {
                if(node == head) {
                    head = head->next;
                    node = head;
                    pre = head;
                }
                else {
                    pre->next = node->next;
                    node = pre->next;
                }
            }
            else {
                pre = node;
                node = node->next;
            }
        }
        return head;
    }

67. Add Binary

https://leetcode.com/problems/add-binary/description/

    string addBinary(string a, string b) {
        if(a.size()<b.size()) return addBinary(b, a);
        int c = 0;
        int j = b.size()-1, i = a.size()-1;
        for(;i>=0 && (c||j>=0); i--,j--,c/=2) {
            c += a[i] - '0' + (j>=0? b[j] - '0':0);
            a[i] = c%2 + '0';
        }
        return (c? "1":"") + a;
    }

183. Customers Who Never Order

https://leetcode.com/problems/customers-who-never-order/description/

select C.Name as Customers
from Customers as C
where C.Id not in (select Orders.CustomerId from Orders);

select C.Name as Customers
from Customers as C
left join Orders on C.Id = Orders.CustomerId
where Orders.CustomerId is null

select C.Name as Customers
from Customers as C

where not exists (select CustomerId from Orders where C.Id = Orders.CustomerId);

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/
Solution 1. Use a recursive call to check the values. The call stack acts as a stack for the node values, which access the node values backwardly. At the same time, use a pointer p to access the node values forwardly. O(n) in space.
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        return check(head, p);
    }
    bool check(ListNode* node, ListNode*& p) {
        if(!node) return true;
        bool isNext = check(node->next,p) && (node->val == p->val);
        p = p->next;
        return isNext;
    }
Solution 2. O(1) space?
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head, * fast = head, *p;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverseList(slow->next);
        slow->next = fast;
        p = head;
        while(fast) {
            if(p->val != fast->val) return false;
            p = p->next;
            fast = fast->next;
        }
        slow->next = reverseList(slow->next);
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* hd = nullptr, * next;
        while(head) {
            next = head->next;
            head->next = hd;
            hd = head;
            head = next;
        }
        return hd;
    }

195. Tenth Line

https://leetcode.com/problems/tenth-line/description/
#
cnt=0
while read line && [ $cnt -le 10 ];
do
  let 'cnt = cnt + 1'
  if [ $cnt -eq 10 ]; then
    echo $line
    exit 0
  fi
done < file.txt

#use AWK
awk '{if(NR==10) print $0}' file.txt
awk 'FNR == 10 {print }'  file.txt
awk 'NR == 10' file.txt

#use sed
sed -n 10p file.txt

#use tail
tail -n+10 file.txt|head -1

225. Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/description/

class MyStack {
    queue<int> q;
public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
        for(int i=0; i<q.size()-1;i++) {
            q.push(q.front());
            q.pop();
        }
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }
    /** Get the top element. */
    int top() {
        return q.front();
    }
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};