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;
    }

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;
    }

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);
}

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];
    }

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;
    }

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;
    }

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;

    }

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--];
        }    
    }

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;
    }

367. Valid Perfect Square

https://leetcode.com/problems/valid-perfect-square/description/
Solution 1. For 32 bit integer input num, sqrt(num) < pow(2,16). Let n=0, Start from 15th bit, n = n + pow(2,15). If num < n*n, decreasing n to pow(2,14), pow(2,13), ... until num > n*n, say n = pow(2,i). Then start again from i-1 bit.
     bool isPerfectSquare(int num) {
        vector<int> sq;
        int n = 0;
        for(int i=15; i>=0; i--){
            while(pow(n+(1<<i),2) > num && i>=0) i--;
            n += (1<<i);
            if(pow(n,2) == num) return true;
        }
        return false;
    }
Solution 2. 1 + 3 + 5 + ... + (2n-1) = n*n
     bool isPerfectSquare(int num) {
        int i = 1;
        while (num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;
    }

257. Binary Tree Paths

https://leetcode.com/problems/binary-tree-paths/description/
Solution 1. Iterative traversal.
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(!root) return res;
        stack<TreeNode*> st;
        stack<string> stp;
        st.push(root);
        stp.push(to_string(root->val));
        TreeNode* node;
        while(!st.empty()){
            node = st.top();
            st.pop();
            string path = stp.top();
            stp.pop();
            if(!node->left && !node->right) {
                res.push_back(path);
            }
            if(node->right){
                st.push(node->right);
                stp.push(path + "->" + to_string(node->right->val));
            }
            if(node->left) {
                st.push(node->left);
                stp.push(path + "->" + to_string(node->left->val));
            }
        }
        return res;
    }
Solution 2. Recursive traversal.
    void preOrder(TreeNode* node, vector<string>& res, string s) {
        if(!node->left && !node->right) {
            res.push_back(s);
            return;
        }
        if(node->left) preOrder(node->left, res, s + "->" + to_string(node->left->val));
        if(node->right) preOrder(node->right, res, s + "->" + to_string(node->right->val));
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(!root) return res;
        preOrder(root, res, to_string(root->val));
        return res;
    }

198. House Robber

https://leetcode.com/problems/house-robber/description/
    void robn(vector<int>& nums, vector<int>& res, int n) {
        if(n == 1) {
            res[1] = max(nums[0],nums[1]);
            return;
        }
        robn(nums, res, n-1);
        if(res[n-2] == res[n-1]) res[n] = res[n-2] + nums[n];
        else res[n] = max(res[n-2]+nums[n], res[n-1]);
    }
    int rob(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        vector<int> res(nums.size(), 0);
        res[0] = nums[0];
        robn(nums, res, nums.size()-1);
        return res.back();
    }

235. Lowest Common Ancestor of a Binary Search Tree

Solution 1. Use property of binary search tree. (Don't forget to use the conditions of the problem!)
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if(p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
Solution 2. Property of binary tree not used.
    int preOrder(TreeNode* node, const TreeNode* p, const TreeNode* q, TreeNode*& res) {
        if(!node || res) return 0;
        int n = 0;
        if(node == p || node == q) n = 1;
        n += preOrder(node->left, p, q, res);
        if(n == 2 && !res) res = node;
        n += preOrder(node->right, p, q, res);
        if(n == 2 && !res) res = node;
        return n;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = nullptr;
        preOrder(root, p, q, res);
        return res;
    }

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/description/
    int maxSubArray(vector<int>& nums) {
        int mx = nums[0], s = 0;
        for(int n: nums) {
            s += n;
            mx = max(s,mx);
            if(s<0) s = 0;
        }
        return mx;
    }

401. Binary Watch

https://leetcode.com/problems/binary-watch/description/
Solution 1. Loop through hour and minute, check the total bits
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        for(int h=0; h<12; h++) {
            for(int m=0; m<60; m++) {
                if(bitset<10> (h<<6 | m).count() == num)
                   res.push_back(to_string(h) + ":" + (m<10 ? "0":"") + to_string(m));
            }
        }
        return res;
    }
Solution 2. Get all possible numbers with num bits
    void combination(int n, int N, int s, vector<int>& c) {
        if(n>N || n==0) return;
        if(n==1) {
            for(int i=0;i<N;i++) {
                c.push_back(s + (1<<i));
            }
            return;
        }
        combination(n, N-1, s, c);
        combination(n-1, N-1, s + (1<<(N-1)), c);
    }
    vector<string> readBinaryWatch(int num) {
        if(num == 0) return vector<string> {"0:00"};
        vector<string> res;
        vector<int> c;
        combination(num, 10, 0, c);
        for(auto x : c) {
            int m = x & 15;
            int s = x >> 4;
            if(m<12 && s<60) res.push_back(to_string(m) + ":" + (s<10? "0":"") + to_string(s));
        }
        return res;
    }

447. Number of Boomerangs

https://leetcode.com/problems/number-of-boomerangs/description/
Solution 1. 
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(auto &x : points) {
            unordered_map<int,int> vm(points.size());
            for(auto &y : points) {
                d = pow(x.first - y.first, 2) + pow(x.second - y.second, 2);
                res += 2 * vm[d]++;
            }
        }
        return res;
    }
Solution 2.
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(int i=0; i<points.size(); i++) {
            unordered_map<int,int> vm(points.size());
            for(int j=0; j<points.size(); j++) {
                d = pow(points[i].first - points[j].first, 2) + pow(points[i].second - points[j].second, 2);
                vm[d]++;
            }
            for(auto &x: vm){
                res += x.second * (x.second - 1);
            }
        }
        return res;
    }