1 排序

1.1 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void sort(int[] arr, int start, int end) {
	if (start >= end)
		return;

	if (start < end) {
		// 记录比pivot小的坐标
		int i = start;
		// 记录比pivot大的坐标
		int j = end;
		int pivot = arr[start];
		int temp;
		//此循环是把所有大于pivot的数放到右边，小于的放左边
		while (i != j) {
			while (i<j && pivot <= arr[j]){
				j--;
			}
			while (i<j && pivot >= arr[i]){
				i++;
			}
			if (i<j){
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		// 将pivot放入中间
		temp = arr[i];
		arr[i] = pivot;
		arr[start] = temp;

		// 递归处理子数组
		sort(arr,start,i-1);
		sort(arr,i+1,end);
	}
}

1.2 计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] sortArray(int[] nums) {
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;

	for (int num : nums) {
		min = Math.min(min, num);
		max = Math.max(max, num);
	}

	int[] count = new int[max - min + 1];
	for (int num : nums) {
		count[num - min]++;
	}

	int i = 0;
	for (int num = min; num <= max; num++) {
		while (count[num - min] > 0) {
			nums[i++] = num;
			count[num - min]--;
		}
	}
	return nums;
}

1.3 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] sort(int[] arr) {
	if (arr.length < 2) return arr;
	int size = arr.length / 2;
	int[] left = Arrays.copyOfRange(arr,0,size);
	int[] right = Arrays.copyOfRange(arr,size,arr.length);
	arr = merge(sort(left),sort(right));
	return arr;
}

private static int[] merge(int[] left, int[] right) {
	int[] result = new int[left.length + right.length];
	int leftIndex = 0;
	int rightIndex = 0;
	for (int i = 0; i < result.length;i++){
		if (leftIndex >= left.length){
			result[i] = right[rightIndex++];
		} else if (rightIndex >= right.length) {
			result[i] = left[leftIndex++];
		} else if (left[leftIndex] <= right[rightIndex]) {
			result[i] = left[leftIndex++];
		} else {
			result[i] = right[rightIndex++];
		}
	}
	return result;
}

2 链表

2.1 哨兵插入

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode append(ListNode head, int value) {
	ListNode dummy = new ListNode(0);
	dummy.next = head;

	ListNode node = dummy;
	while (node.next != null) {
		node = node.next;
	}

	ListNode newNode = new ListNode(value);
	node.next = newNode;
	return dummy.next;
}

2.2 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
	ListNode prev = null;
	ListNode cur = head;
	while (cur != null) {
		ListNode next = cur.next;  // 保存下一个节点
		cur.next = prev;
		prev = cur;
		cur = next;
	}

	return prev;
}

3 搜索算法

3.1 bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> bfs(TreeNode root) {
	Queue<TreeNode> queue = new LinkedList<>();
	if (root != null) {
		queue.offer(root);
	}

	List<Integer> result = new ArrayList<>();
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		result.add(node.val);
		if (node.left != null) {
			queue.offer(node.left);
		}
		if (node.right != null) {
			queue.offer(node.right);
		}
	}
	return result;
}

3.2 前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static List<Integer> preOrderTraversal(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	preOrderDfs(root, result);
	return result;
}

private static void preOrderDfs(TreeNode root, List<Integer> result) {
	if (root != null) {
		result.add(root.val);
		preOrderDfs(root.left, result);
		preOrderDfs(root.right, result);
	}
}
====================循环实现======================================
public static List<Integer> preOrderTraversalCycle(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = root;
	while (cur != null || !stack.isEmpty()) {
		while (cur != null) {
			// 先保存中
			result.add(cur.val);
			stack.push(cur);
			cur = cur.left;
		}
		cur = stack.pop();
		cur = cur.right;
	}
	return result;
}

3.3 中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static List<Integer> inOrderTraversal(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	inOrderDfs(root, result);
	return result;
}

public static void inOrderDfs(TreeNode root, List<Integer> result) {
	if (root != null) {
		inOrderDfs(root.left, result);
		result.add(root.val);
		inOrderDfs(root.right, result);
	}
}
====================循环实现======================================
public static List<Integer> inOrderTraversalCycle(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = root;
	while (cur != null || !stack.isEmpty()) {
		// 遍历左边
		while (cur != null) {
			stack.push(cur);
			cur = cur.left;
		}

		cur = stack.pop();  // 拿出中间
		result.add(cur.val);
		cur = cur.right;
	}
	return result;
}

3.4 后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static List<Integer> postOrderTraversal(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	postOrderDfs(root, result);
	return result;
}

public static void postOrderDfs(TreeNode root, List<Integer> result) {
	if (root != null) {
		postOrderDfs(root.left, result);
		postOrderDfs(root.right, result);
		result.add(root.val);
	}
}
====================循环实现======================================
public static List<Integer> postOrderTraversalCycle(TreeNode root) {
	List<Integer> result = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	TreeNode cur = root;
	TreeNode prev = null;
	while (cur != null || !stack.isEmpty()) {
		while (cur != null) {
			stack.push(cur);
			cur = cur.left;
		}
		cur = stack.peek();
		if (cur != null && cur.right != prev) {
			cur = cur.right;  // 如果没有遍历过右子树，就先遍历
		} else {
			cur = stack.pop();
			result.add(cur.val);
			prev = cur;
			cur = null;
		}
	}
	return result;
}

3.5 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int BinarySearch(int[] arr,int value) {
	int start = 0;
	int end = arr.length -1;
	int mid ;
	while (start <= end) {
		mid = (start + end) / 2;
		if (value > arr[mid]) {
			start = mid+1;
		} else if (value < arr[mid]) {
			end = mid -1;
		} else {
			return mid;
		}
	}
	return -1;
}

4 堆

4.1 最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class KthLargest {

    private PriorityQueue<Integer> minHeap;
    private int size;

    public KthLargest(int[] nums, int size) {
        this.size = size;
        minHeap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    private int add(int num) {
        if (minHeap.size() < size) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(num);
        }
        return minHeap.peek();
    }
}

5 前缀树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Trie {

    static class TrieNode {
        TrieNode children[];
        boolean isWord;

        public TrieNode() {
            children = new TrieNode[26];
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                node.children[ch - 'a'] = new TrieNode();
            }

            node = node.children[ch - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return node.isWord;
    }

    public boolean startWith(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return true;
    }
}