[c++] Leetcode

[Type]

[useful tools]

• [example url]

Hash

• map (stl): map<string, string> map;
• map.insert(pair<string, string>("yeah", "wow")): key"yeah" is mapped to value"wow"
  map["yeah"] = "wow"
• map.find("yeah"): return the pointer pointing to slot with key "yeah"
• map.find("yeah")->second: value of the slot with key "yeah"
• REF: http://mropengate.blogspot.tw/2015/12/cc-map-stl.html

• set (stl): set<string> set; // only key only, no key-value pair

•   std::set<int> myset;
    std::set<int>::iterator itlow,itup;
  
    for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
  
    itlow=myset.lower_bound (30);                //       ^
    itup=myset.upper_bound (60);                 //                   ^
  
    myset.erase(itlow,itup);                     // 10 20 70 80 90

• task-scheduler
• binary-tree-zigzag-level-order-traversal
• group-anagrams // use prime to solve might be faster!
• contains-duplicate-iii
• word-pattern

String Operating

• min(a, b): return smaller one
• max(a, b): return larger one
• reverse(s.begin(), s.end): void, reverse string s
• a.compare(b): return 0 if a==b, 1 if a!=b
• a.substr(begin, length): return a[begin:begin+length]
• a.erase(a.begin(),a.end()) == a.clear() : clear all content
• istringstream fin: fin>>word, or get line(fin, word, delimiter) 

• reverse-string-ii
• repeated-dna-sequences
• reverse-words-in-a-string-iii
• is-subsequence
• decode-string
• find-the-difference: (very easy)

Vector Operating

• std::vector<int> v { 34,23 };
  // or
  // std::vector<int> v = { 34,23 };

• push_back(a): void
• pop_back(a): void
• vector<T>::iterator: the pointer points to the vector
• vector.begin(): return the pointer points to the first element
• vector.end(): return the pointer points to last+1 position
• vector.front(): return the value of first element
• vector.back(): return the value of last element
• vector.empty(): return boolean
• vector.insert(a.begin(), value): insert value at a.begin(), return void
• vector.insert(a.end(), b.begin(), b.end()): append b after a, return void
• vector.erase(a.begin()+pos): erase the item of the pos
• reverse(s.begin(), s.end): void, reverse vector s
• std::random_shuffle(s.begin(), s.end()): void, inlace shuffling

• rotate-array
• remove-element: (easy)
• shuffle-an-array
• pascals-triangle: (easy)
• plus-one: (easy)

DFS

• unordered_set.find(a): return a's reference
• unordered_set.find(a)==unordered_set.end() -> a doesn't exist in the hash
• diameter-of-binary-tree
• Increasing Subsequences
• path-sum-ii
• convert-bst-to-greater-tree: good exercise!!
• maximum-depth-of-binary-tree: (easy)
• combination_sum: good

BFS

• queue<template> q
• q.push(): push back
• q.pop(): pop front
• q.back(): return last value
• q.front(): return first value

• find-largest-value-in-each-tree-row

Quick Sort

• sort-colors

Binary Sort 

• search-a-2d-matrix

Useful Tips

• for(auto e: <iterable class>) //<iterable class>-> list, vector, map, set...etc
  traverse through the whole class
• sort(<iterable class>.begin(), <iterable class>.end()) : void, directly sort inline        vector<string> test;
  test.push_back("ab");
  test.push_back("ac");
  test.push_back("aa");
  sort(test.begin(), test.end());
  test-> aa, ab, ac (sorted)
• INT: 4 bytes/2 = 16 bits
• INT_MAX: 2^15 - 1 = 32767
• INT_MIN: -2^15 + 1 = -32767

• maximum-product-of-three-numbers (easy)

Math Libs

• pow(a, b): return a to the power of a

Algorithm by self-thinking

• elimination-game: thinking of mod 4
• minimum-moves-to-equal-array-elements-ii: find median
• permutations: recursive
• remove-duplicates-from-sorted-list: Linked List
• merge-two-sorted-lists: linked list, basic

Dynamic Programming

• climbing-stairs: fibonacci
• maximum-subarray: easy level but good practicing example
• ones-and-zeroes: 
• perfect-squares
• longest-increasing-subsequence
• 2-keys-keyboard: factor decomposition

Algorithm

• range-sum-query-mutable: segment tree (log n to sum over given range)
• valid-perfect-square: binary search O(logN)
• search-for-a-range: binary search O(logN)

Conversion

• isdigit(int c): check whether character c is decimal digit or not. 

REF

• https://github.com/chychen/leetcode_cpp