[20307][uu][2][bash](00:52:04)[0](root) : ~
$go get -u github.com/motemen/gore
[20308][uu][2][bash](00:52:12)[0](root) : ~
$gore 
gore version 0.3.0  :help for help
gore> lookup := make(map[int]int)
map[int]int{}
gore> lookup[3]=1
1
gore> lookup
map[int]int{3:1}
gore> lookup[2]
0
gore> lookup[3]
1
gore> lookup
map[int]int{3:1}
gore>

Cling:

https://root.cern.ch/download/cling/

$cling
****************** CLING ******************
* Type C++ code and press enter to run it *
*             Type .q to exit             *
*******************************************
[cling]$ __builtin_popcount(4)
(int) 1
[cling]$ #include <string>
[cling]$ using namespace std;
[cling]$ string s(5,'1');
[cling]$ s
(std::__cxx11::string &) "11111"
[cling]$ string w="hello";
[cling]$ int n=2;
[cling]$ for (int i = 0; i<5; ++i) if (n&(1<<i)) s[i] = w[i];
[cling]$ s
(std::__cxx11::string &) "1e111"
[cling]$

cling -std=c++17 for C++17.

https://repl.it/

Master Theorem

https://en.wikipedia.org/wiki/Master_theorem

Online Judge

http://www.practice.geeksforgeeks.org

https://leetcode.com/problemset/algorithms/

https://www.lintcode.com/en/

https://uva.onlinejudge.org/index.php?option=com_onlinejudge

Interview Questions

https://www.careercup.com/page

http://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=145

C++ Convention

using VB=vector<bool>;
using VVB=vector<VB>;
using VS=vector<string>;
using VVS=vector<VS>;

while (count--) xxx;

After the while block, count is -1;

while (count) xxx, count--;

After the while block, count is 0;

head, tail means inclusive. begin, end is the same like STL, end means pass-to-end.

For simplicity:

hd, tl means head and tail.
bn, ed means begin and end.

4.1 Create a 2-D empty square matrix:

// 1
vector<vector<bool>> M(L,vector<bool>(L, false));

// 2
bool** M = new bool*[L];
for(int row = 0, col = 0; row < L; ++row){
  M[row] = new bool[++col]();
  //M[row][col-1]=true;
}

// 3
bool M[L][L]; memset(M, 0, L*L*sizeof(bool));
for(int i=0;i<L;++i){M[i][i]=true;}

4.2 C++ string split

C++ has no split function. This one is a template. delimiter could be a char or string!!!

VS split(string s){
  VS r;
  int i = 0;
  while ((i = s.find(delimiter)) != s.npos)
      r.push_back(s.substr(0, i)), s.erase(0, i + delimiter.size());// or s=s.substr(i+delimiter.size())
  if(!s.empty()) r.push_back(s); //Don't forget this
  return r;
}

下面这样写也行,在循环里面处理最后那一块substring.

  while ((pos = s.find(delimiter)) != s.npos || !s.empty()) {
      if(pos!=s.npos){
        r.push_back(s.substr(0, pos));
        s.erase(0, pos + delimiter.size());// or s=s.substr(pos+delimiter.size())
      }else r.push_back(s),s="";
  }

Bit is a bit; BIT is binary index tree.

If possible, use bitset<N> instead of vector<bool>.

[cling]$ bitset<256> bitmap;
[cling]$ sizeof(bitmap)
(unsigned long) 32
[cling]$ vector<bool> vb(256);
[cling]$ sizeof(vb)
(unsigned long) 40

1000000007 == 10^9 + 7 is the first 10-digit prime.

[cling]$ (1L<<31)-1
(long) 2147483647
[cling]$ string s="2147483647";
[cling]$ s.size()
10
[cling]$ LLONG_MAX
(long long) 9223372036854775807
[cling]$ string s="9223372036854775807";
[cling]$ s.size()
(unsigned long) 19

Digit number of INT_MAX is 10, LLONG_MAX is 19.

In C++, a float divided by 0 is allowed, the result is inf. But an integer divided by 0 will crash the program immediately.

SIGFPE - The SIGFPE signal is sent to a process when it executes an erroneous arithmetic operation, such as division by zero (the name “FPE”, standing for floating-point exception, is a misnomer as the signal covers integer-arithmetic errors as well).

[cling]$ 1.2/0
(double) inf

Other Libs:

Facebook Folly

https://github.com/facebook/folly

4.3 C++ language tips

关于C++language的注意事项

lambda function其实是一个object.要得到其type可以用decltype().
分清楚object和type, template里面要传type, constructor里面要传object.

比如: priority_queue的comparator不接受lambda function,必须用functor或者decltype.

看这道题: linkedin-2016-11

http://stackoverflow.com/questions/5807735/c-priority-queue-with-lambda-comparator-error

如果是用的lambda函数对象,需要在priority_queue的constructor里面传递它.

auto comp = [](const my_pair_t& e1, const my_pair_t& e2) {
   return e1.first > e2.first; };
priority_queue<my_pair_t, my_container_t, decltype(comp)> queue(comp);

如果用的是function object,就不需要!!!

struct comp{
  bool operator()(const my_pair_t& e1, const my_pair_t& e2)
        { return e1.first > e2.first; };
};
priority_queue<my_pair_t, my_container_t, comp> queue;

后面这种方法其实更好,因为不需要create一个lambda function object. 比如priority_queue是class的一个成员变量,那么就必须用第二种方法.(比如在DelayQueue里面)

check: https://repl.it/F8GL

4.4 Complexity

复杂度不能想当然

比如CLRS P157 的build max heap函数.一个for loop套一个LogN的函数结果复杂度不是\(O(NLogN)\)而是\(O(N)\).

DFS的复杂度

解的个数 x 得到一个解经过的步数

复杂度不确定

根据输入的不同可以变

4.5 C++ Deadloop Trap

4.5.1 Comparison of `unsigned expression` >= 0 is always true

[cling]$ c=12;
[cling]$ for (unsigned int i = 10; i >= 0; i--){ printf("%u,",i); if(c--==0)break;}
input_line_9:2:30: warning: comparison of unsigned expression >= 0 is always true [-Wtautological-compare]
 for (unsigned int i = 10; i >= 0; i--){ printf("%u,",i); if(c--==0)break;}
                           ~ ^  ~
10,9,8,7,6,5,4,3,2,1,0,4294967295,4294967294,

In 122. Best Time to Buy and Sell Stock II, the following solution makes program crash!!!

int maxProfit(vector<int>& prices) {
    int r=0;
    for(int i=0;i<prices.size()-1;++i){
        int d = prices[i+1]-prices[i];
        if(d>0) r+=d;
    }
    return r;
}

prices.size() returns a size_t, which is unsinged int: http://en.cppreference.com/w/cpp/types/size_t, unsinged int - 1 will also be an unsigned int.

Line 3 should be:

    for(int i=0;i<(int)prices.size()-1;++i){

4.5.2 如何在循环中从STL container删除元素

Bug多发地段之一.

http://en.cppreference.com/w/cpp/container/set/erase http://en.cppreference.com/w/cpp/container/unordered_set/erase

auto it=ms.begin();
while(it!=ms.end())
  if(xxx)
    it=ms.erase(it);
  else it++;

http://www.cnblogs.com/grandyang/p/5000291.html

Check 310. Minimum Height Trees

Java

Map<String, String> map = new HashMap<>() {{
  put("test", "1"); put("test2", "2"); put("test3", "3");}};
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while(it.hasNext()){if(it.next().getKey().equals("test2")) {it.remove();}}

or even simpler:

Iterator it=map.keySet().iterator();
while(it.hasNext()){
  if(it.next().equals("test2")){
    it.remove();
  }
}

4.6 array boundary check

[cling]$ #include "henry.h"
[cling]$ vector<int> d;
[cling]$ d.resize(10);
[cling]$ d[-1]
(int) 0
[cling]$ d.at(-1)
>>> Caught a std::exception!
>>> vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 10)
[cling]$ int dp[10][10];
[cling]$ dp[-1][-1]
input_line_10:2:2: warning: array index -1 is before the beginning of the array [-Warray-bounds]
 dp[-1][-1]
 ^      ~~
input_line_9:2:2: note: array 'dp' declared here
 int dp[10][10];
 ^
(int) 32764
[cling]$

4.7 nth_element in java

STL源码解析 - nth_element: http://blog.csdn.net/lifesider/article/details/6580240

https://github.com/codestream/algorithms/blob/master/java/org/my/algo/one/NthElement.java

public class NthElement {
  static Random rnd = new Random(1);

    // analog of C++ nth_element()
    public static int nth_element(int[] a, int low, int high, int n) {
      if (low == high - 1)
        return low;
      int q = randomizedPartition(a, low, high);
      int k = q - low;
      if (n < k)
        return nth_element(a, low, q, n);
      if (n > k)
        return nth_element(a, q + 1, high, n - k - 1);
      return q;
    }

    static int randomizedPartition(int[] a, int low, int high) {
      swap(a, low + rnd.nextInt(high - low), high - 1);
      int x = a[high - 1];
      int i = low - 1;
      for (int j = low; j < high; j++) {
        if (a[j] <= x) {
          ++i;
          swap(a, i, j);
        }
      }
      return i;
    }

    static void swap(int[] a, int i, int j) {
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
    }

    static int[] getRandomPermutation(int n, Random rnd) {
      int[] res = new int[n];
      for (int i = 0; i < n; i++)
        res[i] = i;
      for (int i = res.length - 1; i > 0; i--)
        swap(res, i, rnd.nextInt(i + 1));
      return res;
    }

    // Usage example
    public static void main(String[] args) {
      for (int step = 0; step < 100000; step++) {
        int n = rnd.nextInt(10) + 1;
        int[] p = getRandomPermutation(n, rnd);
        int k = rnd.nextInt(n);
        int res = nth_element(p, 0, n, k);
        if (res != k) {
          System.err.println(res + " " + k);
        }
      }
    }
}

4.8 Java Length and Size

size() is a method specified in java.util.Collection, which is then inherited by every data structure in the standard library. length is a field on any array (arrays are objects, you just don’t see the class normally), and length() is a method on java.lang.String, which is just a thin wrapper on a char anyway.

https://stackoverflow.com/questions/20192843/difference-between-size-and-length-methods

4.9 template used in online contest

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef int64_t LL;
typedef uint64_t ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
template<class T, class... U> void DEBUG(const T &head, const U &... tail) { 
#ifdef HOME
    _W('#'); _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...);
#endif
}
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;

4.10 Python

http://docs.python-guide.org/en/latest/writing/gotchas/

4.11 about this website

edit /usr/local/lib/R/site-library/bookdown/resources/gitbook/css/style.css ‘page-inner’ for width of the page

Chapter 4 Introduction