4. Median of Two Sorted Arrays

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);
        nums1.insert(nums1.begin(), INT_MIN);
        nums2.insert(nums2.begin(), INT_MIN);
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);
        m = nums1.size();
        n = nums2.size();
        int il = 0, ih = m-1;
        int i, j;
        while(il<=ih) {
            i = (il + ih)/2;           
            j = (m+n+1)/2 - i;           
            if(nums1[i-1]>nums2[j]) {
                ih = i-1;
            }
            else if(nums2[j-1]>nums1[i]) {
                il = i+1;
            }
            else break;
        }
        if((m+n)%2==0) return (max(nums1[i-1],nums2[j-1]) + min(nums1[i],nums2[j]))/2.;
        return max(nums1[i-1], nums2[j-1]);
    }

740. Delete and Earn

https://leetcode.com/problems/delete-and-earn/description/
    int deleteAndEarn(vector<int>& nums) {
        vector<int> ns(100001, 0);
        for(int i: nums) ns[i]++;
        int skip = 0, keep = 0;
        for(int i=1; i<ns.size(); i++) {
            int keepi = skip + i * ns[i];
            skip = max(keep, skip);
            keep = keepi;
        }
        return max(keep, skip);
    }

516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/description/
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int> (n, 0));
        for(int j=0; j<n; j++) {
            dp[j][j] = 1;
            for(int i=j-1; i>=0; i--) {
                if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }

312. Burst Balloons

https://leetcode.com/problems/burst-balloons/description/
DP
For each len = ir - il +1,
scan the array with k = il, ... , ir, where k is the last to burst
coin_k = nums[il-1] {nums[il] ... nums[k-1]} nums[k] {nums[k+1] ... nums[ir]} nums[ir+1],
dp[il][ir] = max of coin_k:

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        vector<vector<int>> dp(nums.size(), vector<int> (nums.size(), 0));
        for(int len=1; len<=n; len++) {
            for(int il=1; il <= n-len+1; il++) {
                int ir = il+len-1;
                for(int k=il; k<=ir; k++)
                    dp[il][ir] = max(dp[il][ir], nums[il-1]*nums[k]*nums[ir+1] + dp[il][k-1] + dp[k+1][ir]);
            }
        }
        return dp[1][n];
    }

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

750. Number Of Corner Rectangles

    int countCornerRectangles(vector<vector<int>>& grid) {
        if(grid.size() <= 1) return 0;
        if(grid[0].size() <= 1) return 0;
        int NI = grid.size(), NJ = grid[0].size();
        int res=0;
        for(int i=0; i<NI; i++) {
            for(int ii=i+1; ii<NI; ii++) {
                int n=0;
                for(int j=0; j<NJ; j++) {
                    n += grid[i][j]*grid[ii][j];
                }
                res += n*(n-1)/2;
            }
        }
        return res;
    }

748. Shortest Completing Word

    string shortestCompletingWord(string lp, vector<string>& words) {
        transform(lp.begin(), lp.end(), lp.begin(), ::tolower);
        string res;
        int sz = 16;
        unordered_map<char,int> lm;
        for(char c: lp) {
            if(c>='a' && c<='z') lm[c]++;
        }
        for(auto &s: words) {
            if(s.size()<sz) {
                unordered_map<char,int> tm = lm;
                for(char c : s) if(tm.count(c)) tm[c]--;
                bool complete = true;
                for(auto &m: tm) {
                    if(m.second>0) {complete = false; break;}
                }
                if(complete) {
                    res = s;
                    sz = s.size();
                }
            }
        }
        return res;
    }

746. Min Cost Climbing Stairs

    int minCostClimbingStairs(vector<int>& cost) {
        int N = cost.size();
        if(N == 0) return 0;
        if(N == 1) return cost[0];
        if(N == 2) return min(cost[0], cost[1]);

        int c0 = cost[0], c1 = cost[1], c;
        for(int i=2; i<N; i++) {
            c = min(c0, c1) + cost[i];
            c0 = c1;
            c1 = c;
        }
        return min(c0, c1);
    }

638. Shopping Offers

https://leetcode.com/problems/shopping-offers/description/
bool operator<(vector<int>& s, vector<int>& n) {
    for(int i=0; i<n.size(); i++) {
        if(s[i]>n[i]) return false;
    }
    return true;
}
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int res = INT_MAX;
        shop(price, special, 0, needs, res, 0);
        return res;
    }
    void shop(vector<int>& price, vector<vector<int>>& special, int s, vector<int> needs, int&res, int sum){
        int I = price.size();
        if(s == special.size()) {
            for(int i=0; i<I; i++) sum += price[i] * needs[i];
            if(sum < res) res = sum;
            return;
        }
        shop(price, special, s+1, needs, res, sum);
        if(special[s]<needs)
        do {
            for(int i=0; i<I; i++) {
                needs[i] -= special[s][i];
            }
            sum += special[s][I];
            shop(price, special, s+1, needs, res, sum);
        } while(special[s]<needs);
       
    }
};

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

744. Find Smallest Letter Greater Than Target

    char nextGreatestLetter(vector<char>& letters, char target) {
        if(letters.back() <= target || letters.front()> target) return letters.front();
        int lo = 0, hi = letters.size() - 1, mi;
        while(lo<hi) {
            mi = (lo + hi) /2;
            if(mi == lo) break;
            if(target < letters[mi]) hi = mi;
            else if(target >= letters[mi]) lo = mi;
        }
        return letters[hi];
    }

LeetCode C++ Solutions List

1. Two Sum
7. Reverse Integer
9. Palindrome Number
12. Integer to Roman
13. Roman to Integer
14. Longest Common Prefix
20. Valid Parentheses
21. Merge Two Sorted Lists
26. Remove Duplicates from Sorted Array
27. Remove Element
28. Implement strStr()

35. Search Insert Position
38. Count and Say
46. Permutations
53. Maximum Subarray
58. Length of Last Word
66. Plus One
69. Sqrt(x)

67. Add Binary
70. Climbing Stairs
83. Remove Duplicates from Sorted List
88. Merge Sorted Array
94. Binary Tree Inorder Traversal

100. Same Tree

725. Split Linked List in Parts

    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> nd(k, root);
        if(root == nullptr) return nd;
        ListNode* p = root;
        int N=0;
        while(p) {
            N++;
            p = p->next;
        }
        int n2 = N/k, n1 = n2+1;
        int k1 = N - n2*k, k2 = k - k1;
        p = root;
        for(int i=0; i<k; i++) {
            if(i<k1) {
                nd[i] = p;
                int j=0;
                while(j<n1-1) {
                    p=p->next;
                    j++;
                }
                ListNode* q = p;
                p = p->next;
                q->next = nullptr;
            }
            else {
                nd[i] = p;
                if(p==nullptr) continue;
                int j=0;
                while(j<n2-1) {
                    p=p->next;
                    j++;
                }
                ListNode* q = p;
                p = p->next;
                q->next = nullptr;
            }
        }
        return nd;
    }

724. Find Pivot Index

    int pivotIndex(vector<int>& nums) {
        if(nums.size() == 0) return -1;
        if(nums.size() == 1) return 0;
        int l = 0, r = 0;
        for(int i=1; i< nums.size(); i++) r += nums[i];
        int i = 0;
        while(l != r) {
            l += nums[i];
            i++;
            if(i == nums.size()) break;
            r -= nums[i];
        }
        if(i == nums.size()) return -1;
        else return i;
    }

727. Minimum Window Subsequence

    string minWindow(string S, string T) {
        int NS = S.size(), NT = T.size();
        vector<vector<int>> dp(NT, vector<int> (NS, -1));
        string res;
        for(int i=0; i<NT; i++) {
            for(int j=i; j<NS; j++) {
                if(T[i] == S[j]) {
                    if(i == 0)
                        dp[i][j] = j;
                    else {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    if(i == NT - 1 && dp[i][j] != -1){
                        string s = S.substr(dp[i][j], j - dp[i][j] + 1);
                        if(res.empty()) res = s;
                        else if(s.size() < res.size()) res = s;
                    }
                }
                else if(j>0){
                    dp[i][j] = dp[i][j-1];
                }
                if(j == NS-1 && dp[i][j] == -1) return "";
            }
        }
        return res;
    }

721. Accounts Merge

https://leetcode.com/problems/accounts-merge/description/
    vector<vector<string>> accountsMerge(vector<vector<string>>& a) {
        int N = a.size();
        if(N<=1) return a;
        vector<int> person(N);
        for(int i=0; i<N; i++) person[i] = i;
        unordered_map<string, int> m1;
        for(int i=0; i<N; i++) {
            vector<string> vs = a[i];
            for(int j=1; j<vs.size(); j++) {
                if(m1.count(vs[j])) {
                    int k = m1[vs[j]];
                    while(k != person[k]) k = person[k];
                    person[k] = i;
                }
                m1[vs[j]] = i;
            }
        }
        unordered_map<int, set<string>> m2;
        vector<int> id(N, -1);
        for(int i=0; i<N; i++) {
            int k = person[i];
            while(k!=person[k]) k=person[k];
            for(int j=1; j<a[i].size(); j++) m2[k].insert(a[i][j]);
        }
        vector<vector<string>> res;
        for(auto& m : m2) {
            vector<string> vs;
            vs.push_back(a[m.first][0]);
            for(auto& s: m.second) {
                vs.push_back(s);
            }
            res.push_back(vs);
        }
        return res;
    }

720. Longest Word in Dictionary

struct comp {
    bool operator() (const std::string& a, const std::string& b) const{
        if(a.size() == b.size()) {
            return a<b;
        }
        return a.size() > b.size();
    }
    };
    string longestWord(vector<string>& words) {
        set<string, comp> st;
        for(auto s: words) st.insert(s);
       
        for(auto &s: st) {
            int i = s.size()-1;
            for(; i>=1; i--) {
                if(!st.count(s.substr(0,i))) break;
            }
            if(i==0) return s;
        }
        return "";
    }

Customized hash function

You need to provide a suitable hash function for your key type. A simple example:
https://stackoverflow.com/questions/32685540/c-unordered-map-with-pair-as-key-not-compiling

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

Customized compare

struct comp {
    bool operator() (const std::string& a, const std::string& b) const{
        if(a.size() == b.size()) {
            return a<b;
        }
        return a.size() > b.size();
    }
};
set<string, comp> st;

///////
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;
});
or,
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);