KnowledgeHash2.md

1D

Heap

Stack

• Functions: peek(), pop(), push()

Queue

• Functions: peek(), poll(), add()/offer()
• Linked List
• PriorityQueue: new Comparator 很重要

Tree

Tree

Depth-first Search

Breadth-first Search

Binary Search Tree

• If BST not given, can use TreeSet

Binary Indexed Tree

Segment Tree

Union Find

Trie

Graph

Graph

Topological Sort

Array

Array

• Arrays.asList([1,2,3]);

Two Pointers

Binary Search

Sort

Hash

Map

Hash Table

HashSet

• contains: O(1)
• set.add(...) returns false if there is duplicate. This operation won't change the existing set.

Basics

Math

• 转换成string
• % mod, 除法
• Integer.MAX_VALUE, Integer.MIN_VALUE; if overflow, use long

String

• s.toCharArray()
• String.valueOf(charArrary)
• sb = new StringBuffer()
• sb.reverse(), sb.append(), sb.deleteCharAt(), sb.length()

Bit Manipulation

• Bit OR |, AND &, XOR ^
• Bit shift: <<, >>

DP

Dynamic Programming

Optimization problems:

• memoization && subproblems
• Fibonacci
• Shortest paths
• guessing && DAG View

Backtracking

• Finding all (or some) solutions to some computational problems, notebaly constraint satisfaction problems
• It attemps to build/find all candidates and abandon partial candidate when the candidates appears not to be suitable(backtracking, backing off from wrong candidates)

Fancy

Memoization

Minimax

Reservoir Sampling

Geometry

Brainteaser

Approach

Greedy

Divide and Conquer

Recursion

• ex: dfs
• always find the entry point or terminating point
• watch out for the return or result of recursed function

Design