416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/
DP1.
    bool canPartition(vector<int>& nums) {
        int sm = accumulate(nums.begin(), nums.end(), 0);
        if(sm&1) return false;
        bitset<10001> bs(1);
        for(int n: nums)
            bs |= (bs<<n);
        return bs[sm/2];
    }
DP2.
    bool canPartition(vector<int>& nums) {
        int sm = accumulate(nums.begin(), nums.end(), 0);
        if(sm & 1) return false;
        vector<bool> dp(sm+1, false);
        dp[0] = true;
        for(auto n: nums) {
            for(int i=dp.size()-1; i>=0; i--) {
                if(dp[i]) dp[i+n] = true;
            }
        }
        return dp[sm/2];
    }

494. Target Sum

https://leetcode.com/problems/target-sum/description/
Solution 1. DP
    int findTargetSumWays(vector<int>& nums, int S) {
        int sm =accumulate(nums.begin(), nums.end(), 0);
        if(sm < S) return 0;
        int target = sm + S;
        if(target & 1) return 0;
        target >>= 1;
        vector<int> dp(sm+1, 0);
        dp[0] = 1;
        for(auto n:nums) {
            for(int i=sm; i>=0; i--) {
                if(dp[i]) {
                    dp[i+n] += dp[i];
                }
            }
        }
        return dp[target];
    }

743. Network Delay Time

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int dmax = 1e7;
        vector<bool> used(N+1, false);
        vector<int> d(N+1, dmax);
        vector<vector<pair<int,int>>> u2v(N+1);
        for(int i=0; i<times.size(); i++) {
            u2v[times[i][0]].push_back({times[i][1], times[i][2]});
        }
        queue<int> q;
        q.push(K);
        d[K] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
// make current node available because signal delay may be smaller through a different path that has not been counted
            used[u] = false;
            for(auto &p: u2v[u]){
                int v = p.first, w = p.second;
                int dv = d[u] + w;
                if(dv < d[v]) {
                    d[v] = dv;
                    if(!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }   
        }
        int res = 0;
        for(int i=1; i<N+1; i++) {
            if(d[i]>=dmax) return -1;
            res = max(res, d[i]);
        }
        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;
    }

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

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

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,1);
        int forward = 1, backward = 1;
       
        for(int i=0; i<n; i++) {
            res[i] *= forward;
            res[n-1-i] *= backward;
            forward *= nums[i];
            backward *= nums[n-1-i];
        }
        return res;
    }

655. Print Binary Tree

https://leetcode.com/problems/print-binary-tree/description/
Solution 1. Always think in the computer way. Figure out the repeating pattern.
    int height(TreeNode* node) {
        if(!node) return 0;
        int l = height(node->left), r = height(node->right);
        return max(l, r) + 1;
    }
    int width(TreeNode* node) {
        if(!node) return 0;
        int l = width(node->left), r = width(node->right);
        return max(l, r) * 2 + 1;
    }
    void print(TreeNode* node, vector<vector<string>>& res, int level, int l, int r) {
        if(!node) return;
        int mid = l + (r - l)/2;
        res[level][mid] = to_string(node->val);
        print(node->left, res, level+1, l, mid-1);
        print(node->right, res, level+1, mid+1, r);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root);
        //int w = pow(2,h) - 1;
        int w = width(root);
        vector<vector<string>> res(h, vector<string> (w,""));
        print(root, res, 0, 0, w-1);
        return res;
    }
Solution 2. Convert location to index.
    void visit(TreeNode* node, vector<vector<pair<int,int>>>& t, int level, int idx) {
        if(!node) return;
        if(t.size()==level) t.push_back({});
        t[level].push_back({idx, node->val});
        visit(node->left, t, level+1, 2*idx);
        visit(node->right, t, level+1, 2*idx+1);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        vector<vector<pair<int,int>>> t;
        visit(root, t, 0, 0);
        int r = t.size();
        int c = pow(2,r) - 1;
        vector<vector<string>> res(r, vector<string> (c, ""));

        for(int i=r-1; i>=0; i--) {
            int k0 = pow(2, r-i-1) - 1;
            int dk = pow(2, r-i);
            for(int j=0; j<t[i].size(); j++) {
                int k = k0 + dk*t[i][j].first;
                res[i][k] = to_string(t[i][j].second);
            }
        }
        return res;
    }

462. Minimum Moves to Equal Array Elements II

https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/description/
Find the median instead of the mean.
    int minMoves2(vector<int>& nums) {
        int N = nums.size();
        if(N<2) return 0;
        auto it = nums.begin() + N/2;
        // nth_element is a partial sorting algorithm
        nth_element(nums.begin(), it, nums.end());
        int median = *it;
        int res = 0;
        for(int n : nums) res += abs(n - median);
        return res;
    }

260. Single Number III

https://leetcode.com/problems/single-number-iii/description/

    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res;
        int x = 0;
        for(int n: nums) {
            x ^= n;
        }
        int b = 1;
        while((b&x) == 0) b <<= 1;
      // explanation in link
      //  // Get the XOR of the two numbers we need to find
      //  int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
      //  // Get its last set bit,  diff &= ~(diff-1) is slower
      //  diff &= -diff; 

        int y = 0, z = 0;
        for(int n: nums) {
            if(b&n) y ^= n;
            else z ^= n;
        }
        return {y, z};
    }

689. Maximum Sum of 3 Non-Overlapping Subarrays

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/
Constructs arrays ia, and ib:
ia[i] stores the beginning index of the largest sum with index <= i;
ib[i] stores the beginning index of the largest sum with index >= i;
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int nk = n-k+1;
        vector<int> s(nk, 0);
        for(int i=0; i<k; i++) s[0] += nums[i];
        for(int i=1; i<nk; i++) s[i] = s[i-1] + nums[i+k-1] - nums[i-1];
     
        vector<int> ia(nk, 0);
        ia[0] = 0;
        for(int i=1; i<nk; i++) {
            if(s[i]>s[ia[i-1]]) ia[i] = i;
            else ia[i] = ia[i-1];
        }
        vector<int> ic(nk, 0);
        ic[nk-1] = nk-1;
        for(int i=nk-2; i>=0; i--) {
            if(s[i]>=s[ic[i+1]]) ic[i] = i;
            else ic[i] = ic[i+1];
        }
        int best = 0;
        vector<int> res;
        for(int i=k; i<nk-k; i++) {
            int tmp = s[ia[i-k]] + s[i] + s[ic[i+k]];
            if(tmp>best) {
                best = tmp;
                res = {ia[i-k], i, ic[i+k]};
            }
        }
        return res;
    }

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

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

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

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

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

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