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

Split string

C
#include <cstring>
#include <iostream>
int main() {
    char input[100] = "A bird, came. down; the. walk";
    char *token = std::strtok(input, " ,.;");
    // string token = std::strtok(input, " ,.;");
    while (token != NULL) {
        std::cout << token << '\n';
        token = std::strtok(NULL, " ,.;");
    }
}

C++ STL
The first puts the results in a pre-constructed vector, the second returns a new vector.

#include <string>
#include <sstream>
#include <vector>
#include <iterator>

template<typename Out>
void split(const std::string &s, char delim, Out result) {
    std::stringstream ss;
    ss.str(s);
    std::string item;
    while (std::getline(ss, item, delim)) {
        *(result++) = item;
    }
}

std::vector<std::string> split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    split(s, delim, std::back_inserter(elems));
    return elems;
}

Boyer–Moore majority vote algorithm

169. Majority Element
Wiki: Boyer–Moore majority vote algorithm
http://www.geeksforgeeks.org/majority-element/

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

Fenwick (Binary Indexed) Trees

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/