Algorithm Tips
Great Common Divisor
Euclid Algorithm is the most famous algorithm for the GCD.
int generateGCD(int a,int b){
if (b == 0) return a;
return generateGCD(b, a % b);
}
Get Digits of Positive Int
while (number > 0) {
print( number % 10);
number = number / 10;
}
Two’s Exponent
2^x = 1 << x;
Get Kth (start form 0) binary digital
return (num >> k) & 1;
Binary Tree’s Height
public int height(TreeNode root){
if(root == null)
return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
Split with Lookahead example
String[] strs = equation.split("(?=[+-])");
Naive Tree BFS
public void bfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>() ;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
// Do your business here, e.g., System.out.print(node.element + " ");
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
Naive Tree Level Order BFS
public void levelBfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
//Do your business
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
//Do your business
}
}
Get Top 3 elements in O(n) time
public int[] top3(int[] nums) {
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;
for(int num:nums){
if(num > max1){
max3 = max2;
max2 = max1;
max1 = num;
}else if (num > max2){
max3 = max2;
max2 = num;
}else if (num > max3){
max3 = num;
}
}
return new int[]{max3, max2, max1};
}
Binary search
If the value is found, return the index; else return -(low + 1)
while low
is the insert position
private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
Union-Find
Union-Find
is used to solve the nework connectivity, e.g., to check if there is cycle in set, to find disjoint sets.
Union
command is to conenct to sets. Union by rank
always attaches the shorter tree to the root of the taller tree.
Find
command is to find the parent of a node.
public class UnionFind {
private int[] parent;
private int[] size;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 0;
}
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
}