1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* *
 * Definition for a binary tree node.
 * From LeetCode.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right)
 *       : val(x), left(left), right(right) {}
 * };
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

TreeNode* delete_node(TreeNode* root, int key) {
    if(root==nullptr) return nullptr;
    else if(root->val>key) {
        root->left=delete_node(root->left, key);
    }
    else if(root->val<key) {
        root->right=delete_node(root->right, key);
    }
    else {
        if(root->left==nullptr) return root->right;
        else if(root->right==nullptr) return root->left;
        else {
            TreeNode* new_root=root->right;
            while(new_root->left!=nullptr) new_root=new_root->left;
            new_root->right=delete_node(root->right, new_root->val);
            new_root->left=root->left;
            return new_root;
        }
    }
    return root;
}

1
2
3
4
5
6
7
8
9

vector<string> split(string str, char c) {
    stringstream ss(&str);
    vector<string>res;
    string temp;
    while(getline(ss, temp, c)){
        res.emplace_back(temp);
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<int>longest_prefix_array;
void compute_longest_prefix_array(const string& pattern) {
    longest_prefix_array.resize(pattern.size(), -1);
    for(int i=1; i<pattern.size(); i++) {
        int j=longest_prefix_array[i-1];
        while(j!=-1&&pattern[j+1]!=pattern[i]) {
            j=longest_prefix_array[j];
        }
        if(pattern[j+1]==pattern[i]) {
            longest_prefix_array[i]=j+1;
        }
    }
}

bool kmp_search(const string& str, const string& pattern) {
    compute_longest_prefix_array(pattern);
    for(int i=1, j=-1; i<str.size()-1; i++) {
        while(j!=-1&&pattern[j+1]!=str[i]) {
            j=longest_prefix_array[j];
        }
        if(pattern[j+1]==str[i]) {
            j++;
            if(j==str.size()-1) return true;
        }
    }
    return false; // mismatch
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void insertion_sort(vector<int>& arr) {
    for(int i=1; i<arr.size(); i++) {
        int temp=arr[i], j=i;
        // Move greater elements to positions of greater indexes
        while(arr[j]>temp) {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=temp;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

vector<int>arr;
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition(int low, int high) {
    int pivot=arr[high]; // pivot
    // Index of smaller element 
    // and indicates the right position of pivot found so far
    int i=(low-1); 
    for (int j=low; j<=high-1; j++) {
        // If current element is smaller than the pivot
        if (arr[j]<pivot) {
            i++; // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int low, int high) {
    if (low < high) {
        /* pi is partitioning index, arr[p] is now
        at right place */
        int pi = partition(low, high);
        // Separately sort elements before
        // partition and after partition
        quickSort(low, pi - 1);
        quickSort(pi + 1, high);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <ctime> 
#include <iostream>
#include <random>
using namespace std;
int main() {
  // Using the constructor to
  // initialize with a seed value
  mt19937 mt(time(nullptr));
  // Operator() is used to 
  // generate random numbers
  cout << mt();
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// assume target in candidates
vector<int>candidates;
// return index of target in candidates
int binary_search(int target) {
    int low=0, high=candidates.size();
    while(low<high) {
        int mid=(high-low)/2+low;
        if(candidates[mid]==target) {
            return mid;
        } else if(candidates[mid]>target) {
            high=mid;
        } else {
            low=mid+1;
        }
    }
    return low;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class UnionFind {
public:
    UnionFind(int n) {
        for(int i=0; i<n; i++) {
            parent.push_back(i);
            rank.push_back(0);
        }
    }
    int find(int x) {
        if(parent[x]!=x) {
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) {
            parent[x]=y;
        } else {
            parent[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }
    bool same(int x, int y) {
        return find(x)==find(y);
    }  
private:
    vector<int>parent;
    vector<int>rank;
};