Chapter 4 Introduction

Rank in github by forks:

by stars:

by trending:


WKT(Well-known text):

T - Time Complexity Big O

S - Space Complexity Big O

ET - Expected T

WT - Worst T

S - Subsequence, s - substring

LPS - Longest Palindromic Subsequence

lps - Longest Palindromic Substring

LCS - Longest Common Subsequence

lcs - Longest Common Substring




Morris and iterative(stack):







  • leetcode account:
    henrymoo shadowwalker2718

source code reference:

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

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

  • Master Theorem

  • Online Judge

  • Interview Questions

  • C++ Convention

After the while block, count is -1;

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.2 C++ string split

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


Bit is a bit; BIT is binary index tree.

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

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

[cling]$ (1L<<31)-1
(long) 2147483647
[cling]$ string s="2147483647";
[cling]$ s.size()
[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

4.3 C++ language tips


  1. lambda function其实是一个object.要得到其type可以用decltype().

  2. 分清楚object和type, template里面要传type, constructor里面要传object.

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

看这道题: linkedin-2016-11


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

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


4.4 Complexity

  • 复杂度不能想当然

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

  • DFS的复杂度

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

  • 复杂度不确定


4.5 C++ Deadloop Trap

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.

4.9 template used in online contest

#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...);
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.11 about this website

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