LeetCode Solutions
    Common STL Operations

    Common STL Operations

    Split String 

    #include <sstream>
stringstream ss (s);
getline(ss, sno, ':');
// Result goes in string sno

    Pair 

    pair<int, int> p;
p.first
p.second
make_pair(1, 2)
// <1, 2>

    Type Conversion 

    stoi("123")  // 123  string -> int
to_string(123) // "123" int -> string

    Enumerate Array Elements 

    // next_permutation
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  do {
    // ...
  } while ( std::next_permutation(myints,myints+3) );

  return 0;
}

    Set and Multiset

    • Set containers arrange inserted elements in a specific order, default is ascending
    • The difference between set and multiset: multiset allows duplicate elements

    Good side: Implemented with red-black tree, search operations have good performance Insert, lookup, delete all have time complexity O(log n)

    // Insert elem, return position of new element, pos indicates search start point
// If pos is appropriate it can speed things up
c.insert(pos,elem)
c.insert(elem)
// Delete
c.erase(beg, end)

    Set Intersection, Union, and Difference 

    // Intersection, common elements go into X
set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
// Union, all unique elements go into X
set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
// Difference
set_difference(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));

    Priority Queue 

    priority_queue<int, vector<int>, greater<int>> pq;

pq.push(elem);
elem = pq.top();
pq.pop();

    Merge Two Vectors 

    AB.reserve(A.size() + B.size());	// pre-allocate capacity
AB.insert(AB.end(), A.begin(), A.end());
AB.insert(AB.end(), B.begin(), B.end());

// In-place merge
A.insert(A.end(), B.begin(), B.end());

    Not Less Than and Not Greater Than

    lower_bound(ForwardIterator first, ForwardIterator last, val) finds the position not less than this element from first to last, stops when equal

    upper_bound finds the first position greater than the element, when equals exist it returns the first position greater than the element, so you need to go back one step to reach the equal position, use prev() to go back If nothing found, the iterator stays at end()

    Max Heap and Min Heap 

    // Max heap
priority_queue<int> q;
// Min heap
priority_queue<int, vector<int>, greater<int> > q;

    #enumeration #strings

    Combination Sum SeriesCompare Version Numbers with StringStream