Algorithm
算法复杂性分析
常数阶(1)
1
2
3
4
5
| public void sum(int n) {
int sum = 0;
sum = n*2;
System.out.println(sum);
}
|
对数阶(logN)
多少个2相乘后其结果值会大于n，即2^x=n。由2^x=n可以得到x=logn，所以这段代码时间复杂度是O(logn)
1
2
3
4
5
6
| public void logarithm(int n) {
int count = 1;
while (count <= n) {
count = count*2;
}
}
|
线性阶(n)
1
2
3
4
5
| public void circle(int n) {
for(int i = 0; i < n; i++) {
System.out.println(i);
}
}
|
对数阶(n*logN)
1
2
3
4
5
6
7
8
| public void logarithm(int n) {
int count = 1;
for(int i = 0; i < n; i++) {
while (count <= n) {
count = count*2;
}
}
}
|
平方阶(n2)
1
2
3
4
5
6
7
| public void square(int n) {
for(int i = 0; i < n; i++){
for(int j = 0; j <n; j++) {
System.out.println(i+j);
}
}
}
|
常见算法
冒泡排序算法
1
2
3
4
5
6
7
8
9
10
11
| public static void bubbleSort(int[] input) {
for (int i = 0; i < input.length - 1; i++) {
for (int j = 0; j < input.length - i - 1; j++) {
if (input[j] > input[j+1]) {
int tmp = input[j];
input[j] = input[j+1];
input[j+1] = tmp;
}
}
}
}
|
快速排序算法
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
52
53
54
55
56
57
58
59
60
61
62
63
| import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] nums = new int[]{5, 7, 89, 6, 4};
System.out.println("Unsorted array: " + Arrays.toString(nums));
quicksort(nums, 0, nums.length - 1);
System.out.println("\n\nSorted array: " + Arrays.toString(nums));
}
public static void quicksort(int[] arr, int low, int high) {
if (arr == null || arr.length <= 0) return;
if (high - low < 1) {
return;
} else {
int partitionIndex = partition(arr, low, high);
if (partitionIndex > low && partitionIndex < high) {
quicksort(arr, low, partitionIndex - 1);
}
if (partitionIndex + 1 < high) {
quicksort(arr, partitionIndex + 1, high);
}
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[(high + low) / 2];
int start = low;
int end = high;
while (start <= end) {
while (end > start && arr[end].compareTo(pivot) >= 0) {
end--;
}
if (arr[start].compareTo(pivot) < 0) {
swap(&arr[start], &arr[end]);
start++;
} else {
end--;
}
}
swap(&arr[start], &arr[high]);
return start;
}
private static void swap(Object x, Object y) {
if (x instanceof Integer) {
Integer temp = (Integer) x;
(y).intValue();
x.intValue(temp.intValue());
(y).intValue(temp.intValue() ^ 1);
} else if (x instanceof Integer[]) {
((int[]) x)[0])];
}
}
}
|
二分查找算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (arr.length - 1) / 2;
if (key < arr[mid]) {
high = mid - 1;
} else if (key > arr[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return -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
| import java.lang.*;
class ListNode{
public int val;
public ListNode next;
public ListNode prev;
}
public ListNode reverseList(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode first = head;
ListNode second = head.next;
while(second != null){
ListNode tempNext = second.next;
second.next = first;
last = second;
last.prev = first;
first = second;
second = tempNext;
}
return head;
}
|
动态规划
斐波那契数列
从第三项开始，每一项都等于前两项之和。具体来说，数列的前几项是：1、1、2、3、5、8、13、21、34、……
暴力递归
1
2
3
4
5
6
7
8
|
public static int fib(int number) {
if (number == 1 || number == 2) {
return number;
}
int count = fib(number - 1) + fib(number - 2);
return count;
}
|
复杂度为2^n^
1
2
3
4
5
6
7
8
9
10
| F5
F4 F3
F3 F2=1 F2=1 F1=1
F2=1 F1=1
分析暴力递归写法的执行流程
例如：我们计算f(5) 需要计算f(4) + f(3)
计算f(3) = f(3) + f(2)
发现没 f(3) 就要跑了两次。因此我们就想到可以用缓存把状态记录下来
|
第一次优化 记忆化递归(有备忘录的递归)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static int dfs(int n, int[] mem) {
if (n == 1 || n == 2) {
return n;
}
if (mem[n] != -1) {
return mem[n];
}
int count = dfs(n - 1, mem) + dfs(n - 2, mem);
mem[n] = count;
return mem[n];
}
public static int fib2(int n) {
int[] mem = new int[n + 1];
Arrays.fill(mem, -1);
return dfs(n, mem);
}
|
记忆化递归是一种从顶到底的方法，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。
之后，通过回溯逐层收集子问题的解，构建出原问题的解。
复杂度n
第二次优化 动态规划
动态规划是一种从底至顶的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。
由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。
在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了与记忆化搜索中数组 mem 相同的记录作用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static int fib3(int number) {
if (number == 1 || number == 2) {
return number;
}
int[] dp = new int[number + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= number; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[number];
}
|
复杂度n
第三次优化 动态规划(执行空间优化版本)
缓存表的最终值是前两项的和(dp[i]只与dp[i-1]和dp[i-2]有关)，因此无需数值，只用两个变量滚动前进即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static int fib4(int number) {
if (number == 1 || number == 2) {
return number;
}
int a = 1;
int b = 2;
for (int i = 3; i <= number; i++) {
int tmp = b;
b = a + b;
a = tmp;
}
return b;
}
|
复杂度1
爬楼梯
题目：https://leetcode.cn/problems/climbing-stairs/
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int climbStairs(int n) {
int a = 1, b = 1, sum;
for(int i = 0; i < n - 1; i++){
sum = a + b;
a = b;
b = sum;
}
return b;
}
}
|
打家劫舍
题目：https://leetcode.cn/problems/house-robber/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int a = 0;
int b = 0;
int result = 0;
for (int i = 0; i < nums.length; i++) {
int c = Math.max(nums[i] + a, b);
a = b;
b = c;
result = Math.max(result, c);
}
return result;
}
}
|
