230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
    int kthSmallest(TreeNode* root, int k) {
        int res;
        inOrder(root, k, res);
        return res;
    }
    void inOrder(TreeNode* node, int& k, int& res) {
        if(!node) return;
        if(k>0) inOrder(node->left, k, res);
        k--;
        if(k ==0) { res = node->val; return; }
        if(k>0) inOrder(node->right, k, res);
    }

650. 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/
When n != 0, there the results is the sum of its prime factors.
    int minSteps(int n) {
        if(n == 1) return 0;
        int res = 0;
        vector<int> prime(n+1, 0);
        for(int i=2; i<prime.size(); i++) prime[i] = i;
        for(int i=2; i<prime.size(); i++) {
            int p = prime[i];
            if(p) {
                for(int j=2*p; j<prime.size(); j+=p) prime[j] = 0;
                while(n%p == 0) {
                   res += p;
                    n /= p;
                }
            }
        }
        return res;
    }

392. Is Subsequence

https://leetcode.com/problems/is-subsequence/description/
    bool isSubsequence(string s, string t) {
        if(s.empty()) return true;
        int i=0, j=0;
        while(j < t.size()) {
            if(s[i] == t[j]) {
                i++;
                j++;
            }
            else
                j++;
        }
        return i == s.size();
    }
or
    bool isSubsequence(string s, string t) {
        if(s.empty()) return true;
        int i=0, j=0;
        for(; i<s.size(); i++) {
            while(j < t.size() && s[i] != t[j]) j++;
            if(j==t.size()) return false;
            j++;
        }
        return i == s.size();
    }

423. Reconstruct Original Digits from English

https://leetcode.com/problems/reconstruct-original-digits-from-english/description/
Solution 1. no need to sort. (19 ms)
    string originalDigits(string s) {
        string res;
        vector<string> ns = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        // order to check the numbers
        vector<int> order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        // distinct char of each number
        vector<char> orderc = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> m(256,0);
        vector<string> part(10,"");
        for(char& c: s) m[c]++;
        for(int i=0; i<10; i++) {
            int n = order[i];
            char key = orderc[i];
            int cnt = m[key];  // count to be remove for each char in a word
            for(char& c : ns[n]) m[c] -= cnt;
            part[n] = string(cnt, char('0' + n));

        }
        for(string& p : part) res += p;
        return res;
    }
or,
    string originalDigits(string s) {
        string res;
        vector<string> ns = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        vector<int> order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        vector<char> orderc = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> m(256,0);
        for(char& c: s) m[c]++;
        for(int i=0; i<10; i++) {
            int n = order[i];
            char key = orderc[i];
            while(m[key] > 0) {
                for(char& c : ns[n]) m[c]--;
                res += to_string(n);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

318. Maximum Product of Word Lengths

https://leetcode.com/problems/maximum-product-of-word-lengths/description/
    int maxProduct(vector<string>& words) {
        int N = words.size();
        int res = 0;
        vector<int> w(N, 0);
        for(int i=0; i<N; i++) {
            for(char c : words[i]) w[i] |= 1 << (c - 'a');
            for(int j=0; j<i; j++) {
                if((w[j] & w[i]) == 0) {
                    res = max(res, (int) words[i].size() * (int) words[j].size());
                }
            }
        }
        return res;
    }

241. Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/description/
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        int pos = 0;
        while((pos = input.find_first_of("+-*", pos + 1)) != string::npos) {
            vector<int> res1 = diffWaysToCompute(input.substr(0, pos));
            vector<int> res2 = diffWaysToCompute(input.substr(pos + 1));
            for(int& a : res1)
                for(int& b : res2)
                    switch(input[pos]) {
                        case '+': res.push_back(a + b);
                            break;
                        case '-': res.push_back(a - b);
                            break;
                        default: res.push_back(a * b);
                            break;
                    }
        }
        if(res.size() == 0) res.push_back(stoi(input));
        return res;
    }

lower_bound and upper_bound

https://stackoverflow.com/questions/12158948/lower-bound-upper-bound

Lower bound: first element that is greater-or-equal.
Upper bound: first element that is strictly greater.

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

719. Find K-th Smallest Pair Distance

    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.back() - nums.front(), mid;
        while(lo<hi) {
            mid = (lo + hi)/2;
            // count number of distances that is <= mid;
            int cnt = countDist(nums, mid);
            if(cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    int countDist(vector<int>& n, int dist) {
        int i = 0, j = 0, cnt = 0;
        for(; i < n.size(); i++) {
            while(j<n.size() && n[j] - n[i] <= dist) j++;
            cnt += j - i -1;
        }
        return cnt;
    }

718. Maximum Length of Repeated Subarray

   int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty() || B.empty()) return 0;
        int NA = A.size(), NB = B.size();
        int res = 0;
        vector<int> dp(NB,0);
        for(int j=0; j<NB; j++) {
            if(A[0] == B[j]) {
                res = 1;
                dp[j] = 1;
            }
        }
        vector<int> dp1 = dp;
        for(int i=1; i<NA; i++) {
            for(int j=0; j<NB; j++) {
                if(A[i] == B[j]) {
                    if(j == 0) {
                        dp[j] = 1;
                    }
                    else {
                        dp[j] =  dp1[j-1]+1;
                        res = max(dp[j], res);
                    }
                }
                else dp[j] = 0;
            }
            dp1 = dp;
        }
        return res;
    }

443. String Compression

int compress(vector<char>& chars) {
        if(chars.size() == 0) return 0;
        chars.push_back(1);
        char c_prev = 1;
        int cnt = 0, k = 0;
        for(int j=0; j<chars.size(); j++) {
            if(chars[j] == c_prev) cnt++;
            else {
                if(cnt != 0) {
                    chars[k++] = c_prev;
                    if(cnt != 1) {
                        string s = to_string(cnt);
                        for(char cs: s) {
                            chars[k++] = cs;
                        }
                    }
                }
                c_prev = chars[j];
                cnt = 1;
            }
        }
        chars.pop_back();
        return k;
    }

717. 1-bit and 2-bit Characters

    bool isOneBitCharacter(vector<int>& bits) {
        if(bits.back() == 1) return false;
        if(bits.size() == 1) return true;
        for(int i=0; i<bits.size();) {
            if(bits[i] == 1) i += 2;
            else i++;
            if(i == bits.size()-1) return true;
        }
        return false;
    }

46. Permutations

https://leetcode.com/problems/permutations/description/
Solution 1. 
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        perm(nums, 0, res);
        return res;
    }
    void perm(vector<int>& nums, int idx, vector<vector<int>>& res) {
        if(idx == nums.size()) {
            res.push_back(nums);
            return;
        }
        for(int i=idx; i<nums.size(); i++) {
            // 0 ~ idx-1 are fixed, swap nums[idx] with nums[idx ~ nums.size()-1]
            swap(nums[idx], nums[i]);
            // after swap with nums[idx], fix nums[0 ~ idx], swap for idx+1 ~ end
            perm(nums, idx+1, res);
            // reset before work on i+1
            swap(nums[idx], nums[i]);
        }
    }
Solution 2.
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.size() == 0) return {};
        vector<vector<int>> res;
        res.push_back(nums);
        perm(nums, res, 1);
        return res;
    }
    void perm(vector<int>&nums, vector<vector<int>>& res, int idx) {
        if(idx == nums.size()) return;
        int N = res.size();
        for(int j=0; j<N; j++)
            for(int i=0; i<idx; i++) {
                vector<int> r = res[j];
                swap(r[i], r[idx]);
                res.push_back(r);
            }
        perm(nums, res, idx+1);
    }
Solution 3.
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while(next_permutation(nums.begin(), nums.end()));
        return res;
    }

715. Range Module

https://leetcode.com/problems/range-module/description/
Solution 1. Use map
class RangeModule {
    map<int,int> m;
public:
    RangeModule() {
       
    }
   
    void addRange(int left, int right) {
        auto l = m.upper_bound(left), r = m.upper_bound(right);
        if(l != m.begin()) {
            l--;
            if(l->second < left) l++;
        }
        if(l != r) {
            left = min(left, l->first);
            r--;
            if(right < r->second) right = r->second;
            r++;
            m.erase(l,r);
        }
        m[left] = right;
    }
   
    bool queryRange(int left, int right) {
        auto l = m.upper_bound(left);
        if(l!=m.begin()) {
            l--;
            return l->second >= right;
        }
        return false;
    }
   
    void removeRange(int left, int right) {
        auto l = m.upper_bound(left), r = m.upper_bound(right);
        if(l != m.begin()) {
            l--;
            if(l->second < left) l++;
        }
        if(l==r) return;
        int l1 = min(l->first, left);
        r--;
        int r1 = max(r->second, right);
        r++;
        m.erase(l,r);
        if(l1 < left) m[l1] = left;
        if(right< r1) m[right] = r1;
    }
};

Solution 2. Use vector<int> (196 ms)
class RangeModule {
    vector<int> v;
public:
    RangeModule() {
     
    }
 
    void addRange(int left, int right) {
        if(v.empty()) { v= {left, right}; return;}
        auto l = lower_bound(v.begin(), v.end(), left);
        auto r = upper_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        int j = r - v.begin();
        if(l == r) {
            if(i%2 == 0) {
                l = v.insert(l, right);
                v.insert(l, left);
            }
            return;
        }
        if(i%2 == 0) { *l = left; l++;}
        if(j%2 == 0) { *l = right; l++; }
        else { *l = *r; l++; r++;}
        if(l<r) v.erase(l, r);
    }
 
    bool queryRange(int left, int right) {
        // note that here l = upper_bound(..., left) and r = lower_bound(..., right)
        auto l = upper_bound(v.begin(), v.end(), left);
        auto r = lower_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        return (i%2 != 0) && l == r;
    }
 
    void removeRange(int left, int right) {
        if(v.empty()) { return;}
        auto l = lower_bound(v.begin(), v.end(), left);
        auto r = upper_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        int j = r - v.begin();
        if(l==r) {
            if(i%2 != 0) {
                l = v.insert(l, right);
                v.insert(l, left);
            }
            return;
        }
        if(j%2 != 0) { r--; *r = right;}
        if(i%2 != 0) { *l = left; l++;}
        if(l<r) v.erase(l,r);
    }
};

713. Subarray Product Less Than K

https://leetcode.com/problems/subarray-product-less-than-k/description/
Solution 1. Count from 0 to i
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k==0) return 0;
        int res = 0, N = nums.size();
        for(int i=0, j=0, s=1; i<N; i++) {
            s *= nums[i];
            while(j <= i && s>=k) s /= nums[j++];
            res += i-j+1;
        }
        return res;
    }
Solution 2. Count from i to N
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k==0) return 0;
        int res = 0, N = nums.size();
        for(int i=0, j=0, s=1; i<N; i++) {
            if(i > 0 && i <= j) s /= nums[i-1];
            else j = i;
            while(j<N && s*nums[j]<k) s *= nums[j++];
            res += j-i;
        }
        return res;
    }

712. Minimum ASCII Delete Sum for Two Strings

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
Solution 1.
int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m+1, vector<int> (n+1, 0));
        dp[0][0] = 0;
        for(int i=1; i<m+1; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for(int j=1; j<n+1; j++) dp[0][j] = dp[0][j-1] + s2[j-1];
        for(int i=1; i<m+1; i++) {
            for(int j=1; j<n+1; j++) {
                if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
                }
            }
        }
        return dp[m][n];
    }

714. Best Time to Buy and Sell Stock with Transaction Fee

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
There could be two possible states after visiting prices[i-1]:
1. hold: there is 1 share of stock at hand. The total cash is named hold.
2. sold: there is 0 share of stock at hand. The total cash is named sold.
After visiting prices[i], the states are
1. hold = max(hold at i-1, sold at i-1 and buy 1 share at i)
2. sold = max(sold at i-1, hold at i-1 and sell 1 share at i)
    int maxProfit(vector<int>& prices, int fee) {
        // at i=0, the total cash at hand could be sold or hold:
        int sold = 0, hold = -prices[0];
        for(int i=1; i<prices.size(); i++) {
            int h = max(hold, sold - prices[i]);
            int s = max(sold, hold + prices[i] - fee);
            sold = s;
            hold = h;
        }
        return sold;
    }
or, check local min and max
    int maxProfit(vector<int>& prices, int fee) {
        prices.push_back(-50000);
        int hold = -prices[0], cash = 0;
        for(int i=1; i<prices.size()-1; i++) {
            if(prices[i]<=prices[i-1] && prices[i]<prices[i+1]) {
                // local minimum
                hold = max(hold, cash - prices[i]);
            }
            else if(prices[i]>=prices[i-1] && prices[i]>prices[i+1]) {
                // local maximum
                cash = max(cash, hold + prices[i] -fee);
            }
        }
        return cash;
    }

378. Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int NI = matrix.size(), NJ = matrix[0].size();
        int lo = matrix[0][0], hi = matrix[NI-1][NJ-1];
        while(lo<hi) {
            int mid = lo + (hi - lo) / 2;
            int cnt = 0;
            for(int i=0; i<NI; i++)
                cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid)
                            - matrix[i].begin();
            if(cnt < k) lo = mid+1;
            else hi = mid;
        }
        return lo;
    }

486. Predict the Winner

https://leetcode.com/problems/predict-the-winner/description/
Solution 1. Recursion.
s1: score of player 1
s2: score of player 2
player 1's turn: t1 is true, player 1 wins if s1>=s2 for one of the two cases.
player 2's turn: t1 is false, player 1 wins if s1>=s2 for both of the two cases.
    bool PredictTheWinner(vector<int>& nums) {
        return predict(nums, 0, nums.size()-1, 0, 0, true);
    }
    bool predict(vector<int>& nums, int i, int j, int s1, int s2, bool t1) {
        if(i>j) {
            return s1>=s2;
        }
        if(t1) return predict(nums, i+1, j, s1+nums[i], s2, false)
            || predict(nums, i, j-1, s1+nums[j], s2, false);
        else return predict(nums, i+1, j, s1, s2+nums[i], true)
            && predict(nums, i, j-1, s1, s2+nums[j], true);
    }
Solution 2. Dynamic programming. 
dp[i][j] stores the score difference between player 1 and 2, when the numbers left are from index i to j, and player 1 is the next to play. See discussion session of LeetCode.
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int> (n));
        for(int i=0; i<n; i++) dp[i][i] = nums[i];
        for(int j=1; j<n; j++) {
            for(int i=j-1; i>=0; i--) {
                dp[i][j] = max(nums[j]-dp[i][j-1], nums[i]-dp[i+1][j]);
            }
        }
        return dp[0][n-1] >= 0;

    }

12. Integer to Roman

https://leetcode.com/problems/integer-to-roman/description/
    string intToRoman(int num) {
        map<int, string, greater<int>> I2R = {
            {1000, "M"}, {500, "D"}, {100, "C"}, {50, "L"}, {10, "X"}, {5, "V"}, {1, "I"},
            {900, "CM"}, {400, "CD"}, {90, "XC"}, {40, "XL"}, {9, "IX"}, {4, "IV"}
        };
        string res;
        for(auto const& r : I2R) {
            int c = num/r.first;
            if(c==1) { res += r.second; num -= r.first;}
            else if(c>1) { res += string(c, r.second[0]); num -= c*r.first;}
        }
        return res;
    }
or,
    string intToRoman(int num) {
        string res;
        vector<string> M = {"", "M", "MM", "MMM"};
        vector<string> C = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> X = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> I = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }

481. Magical String

https://leetcode.com/problems/magical-string/description/
    int magicalString(int n) {
        if(n == 0) return 0;
        string ms = "122";
        int res = 1;
        for(int i = 2; i<n; i++) {
            if(ms.size()<n)
                ms += string(ms[i]-'0', ms.back()=='1'? '2':'1');
            res += (ms[i] == '1');
        }
        return res;
    }
or,
    int magicalString(int n) {
        if(n == 0) return 0;
        string ms = "122";
        int res = 1;
        for(int i = 2; i<n; i++) {
            if(ms.size()<n)
            if(ms[i] == '1') {
                if(ms.back() == '1') ms += "2";
                else ms += "1";
            }
            else {
                if(ms.back() == '1') ms += "22";
                else ms += "11";
            }
            res += (ms[i] == '1');
        }
        return res;
    }

554. Brick Wall

https://leetcode.com/problems/brick-wall/description/
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int> mp;
        for(auto & v : wall) {
            int w = 0;
            for(int i=0; i<v.size()-1; i++) {
                w += v[i];
                mp[w]++;
            }
        }
        int NW = wall.size(), res = NW;
        for(auto &m: mp) {
            int n = NW - m.second;
            if(n<res) res = n;
        }
        return res;
    }

144. Binary Tree Preorder Traversal

https://leetcode.com/problems/binary-tree-preorder-traversal/description/
Solution 1. Recursion
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preOrder(root, res);
        return res;
    }
    void preOrder(TreeNode* node, vector<int>& res) {
        if(!node) return;
        res.push_back(node->val);
        preOrder(node->left, res);
        preOrder(node->right, res);
    }
Solution 2. Iteration
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        TreeNode* node;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            node = st.top();
            res.push_back(node->val);
            st.pop();
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return res;
    }

216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/description/
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        bt(k, 1, n, {}, res);
        return res;
    }
    void bt(int k, int imin, int s, vector<int> v, vector<vector<int>>& res) {
        if(s<0 || k<0) return;
        if(k==0 && s==0) {
            res.push_back(v);
            return;
        }
        for(int i=imin; i<=9; i++) {
            v.push_back(i);
            bt(k-1, i+1, s-i, v, res);
            v.pop_back();
        }
    }

539. Minimum Time Difference

https://leetcode.com/problems/minimum-time-difference/description/
    int findMinDifference(vector<string>& timePoints) {
        sort(timePoints.begin(), timePoints.end());
        int h0 = stoi(timePoints.back().substr(0,2));
        int m0 = stoi(timePoints.back().substr(3));
        int h1, m1, dif, res = 12*60;
        for(auto &s : timePoints) {
            h1 = stoi(s.substr(0,2));
            m1 = stoi(s.substr(3));
            dif = abs(h1*60+m1 - (h0*60+m0));  
            if(dif>12*60) dif = 24*60 - dif;
            if(dif<res) res = dif;
            h0 = h1;
            m0 = m1;
        }
        return res;
    }

498. Diagonal Traverse

https://leetcode.com/problems/diagonal-traverse/description/
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(matrix.size() == 0) return {};
        int M = matrix.size();
        int N = matrix[0].size();
        int K = M+N-2;
        vector<int> res;
        for(int k=0; k<=K; k++) {
            int i=0, j=0, d;
            if(k%2 == 0) {
                i = k<M? k:M-1;
                j = k-i;
                d = -1;
            }
            else {
                j = k<N? k:N-1;
                i = k-j;
                d = 1;
            }
            while(i>=0 && i<M && j>=0 && j<N) {
                res.push_back(matrix[i][j]);
                i += d;
                j -= d;
            }
        }
        return res;
    }

626. Exchange Seats

https://leetcode.com/problems/exchange-seats/description/

From the discussion section of LeetCode:
select
if(id < (select count(*) from seat), if(id mod 2=0, id-1, id+1), if(id mod 2=0, id-1, id)) as id, student
from seat
order by id;

--------

/* get all the even numbered rows as odd numbered rows */ SELECT s1.id - 1 as id, s1.student FROM Seat s1 WHERE s1.id MOD 2 = 0 UNION /* get all the odd numbered rows as even numbered rows */ SELECT s2.id + 1 as id, s2.student FROM Seat s2 WHERE s2.id MOD 2 = 1 AND s2.id != (SELECT MAX(id) FROM Seat) /* Just don't get the last row as we will handle it in the next UNION */ UNION /* get the last row if odd and don't change the id value */ SELECT s3.id, s3.student FROM Seat s3 WHERE s3.id MOD 2 = 1 AND s3.id = (SELECT MAX(id) FROM Seat) /* Order the result by id */ ORDER BY id ASC;


-------

select id, case when id%2 = 0 then (select student from seat where id = (i.id-1) ) when id%2 != 0 and id<(select count(student) from seat) then (select student from seat where id = (i.id+1) ) else student end as student from seat i