算法 解题思路与模板

链表

递归反转整个链表

1
2
3
4
5
6
7
8
ListNode reverse(ListNode head){
	if(head == null|| head.next == null)
        return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

双指针

  • 求倒数N个：一个先走N步，然后同时走。
  • 求中点：快慢指针。
  • 合并链表：一个指当前已合并链表的末尾，一个指向待处理的节点。
  • 求环起点：当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
  • 是否相交：让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1。
  • 回文：递归，或者中点-反转。

数组

双指针

  • 去重、修改：快慢指针

  • 二分：左右指针

  • 反转：左右指针

  • 回文：左右指针

  • 最长回文：左右指针从中心向两端扩展

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串   应对奇偶长度的情况
    String palindrome(String s, int l, int r) {
        // 防止索引越界
    	while (l >= 0 && r < s.length()&& s.charAt(l) == s.charAt(r)) {       
           // 双指针，向两边展开        
    		l--; r++;    
    	}     
        return s.substring(l + 1, r); // 返回以 s[l] 和 s[r] 为中心的最长回文串
    }

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

1
2
3
4
5
6
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+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
27
28
29
30
31
32
33
34
35
// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;
    
    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

动态规划

核心

  • 动态规划的一般形式是求最值
  • 求解动态规划的核心问题是穷举
  • 状态转移方程+最优子结构
  • 动态规划的核心设计思想是数学归纳法。
  • 明确base case -> 明确状态 -> 明确选择 -> 定义DP

数学运算技巧

位运算

  1. 利用或操作 | 和空格将英文字符转换为小写

    1
    2
    ('a' | ' ') = 'a'
    ('A' | ' ') = 'a'

  2. 利用与操作 & 和下划线将英文字符转换为大写

    1
    2
    ('b' & '_') = 'B'
    ('B' & '_') = 'B'

  3. 利用异或操作 ^ 和空格进行英文字符大小写互换

    1
    2
    ('d' ^ ' ') = 'D'
    ('D' ^ ' ') = 'd'

  4. 判断两个数是否异号

    1
    2
    3
    4
    5
    int x = -1, y = 2;
    boolean f = ((x ^ y) < 0); // true

    int x = 3, y = 2;
    boolean f = ((x ^ y) < 0); // false

  5. 不用临时变量交换两个数

    1
    2
    3
    4
    int a = 1, b = 2;
    a ^= b;
    b ^= a;
    a ^= b;

  6. 加一

    1
    2
    3
    int n = 1;
    n = -~n;
    // 现在 n = 2

  7. 消除数字 n 的二进制表示中的最后一个 1

1
n & (n-1)
  1. 异或交换律
1
2
3
4
a ^ b = c;
//可以推出以下结论
a ^ c = b;
b ^ c = a;

阶乘算法题

计算阶乘 n! 的结果末尾有几个 0

解题思路：问题转化为：n! 最多可以分解出多少个因子 5？

1
2
3
4
5
6
7
8
9
int trailingZeroes(int n) {
    int res = 0;
    long divisor = 5;
    while (divisor <= n) {
        res += n / divisor;
        divisor *= 5;
    }
    return res;
}

高效寻找素数

Sieve of Eratosthenes算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countPrimes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i < n; i++) 
        if (isPrime[i]) 
            for (int j = i * i; j < n; j += i) 
                isPrime[j] = false;
    
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrime[i]) count++;
    
    return count;
}

模幂运算

  1. Mod运算

对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。

  1. 求幂（快速幂）

    1
    2
    3
    4
    5
    6
    int f(int x,int n){
    2     if(n==0) return 1;
    3     if(n==1) return x;
    4     if(n&1) return f(x,n>>1)*f(x,n>>1)*x;  //如果n是奇数
    5     else return f(x,n>>1)*f(x,n>>1);   //如果n是偶数
    6 }

基本排序算法

快速排序

三路快排
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 class QuickSort {
    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int lt = left - 1;
            int rt = right + 1;
            int curIndex = left;
            int curValue = nums[curIndex];
            int temp;
            while (curIndex < rt) {
                if (curValue > nums[curIndex]) {
                    temp = nums[++lt];
                    nums[lt] = nums[curIndex];
                    nums[curIndex++] = temp;
                } else if (curValue < nums[curIndex]) {
                    temp = nums[--rt];
                    nums[rt] = nums[curIndex];
                    nums[curIndex] = temp;
                } else {
                    curIndex++;
                }
            }
            quickSort(nums, left, lt);
            quickSort(nums, rt, right);
        }
    }
}
双轴快排
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
public class QuickSort {
    public static void main(String[] args){
    	int[] arr = new int[]{7,0,4,8,2,1};
        System.out.println(Arrays.toString(dualPivotQuickSort(arr)));
    }

    public static int[] dualPivotQuickSort(int[] arr) {
        if (arr.length < 2) return arr;
        dualPivotQuickSort(arr, 0, arr.length - 1); 
        return arr;
    }
    private static void dualPivotQuickSort(int[] arr, int left, int right) {
        if(left < right) { 
            if(arr[left] > arr[right]) {
                swap(arr, left, right);
            }
            int index = left + 1; // 当前考察元素下标
            int lower = left + 1; // 用于推进到pivot1最终位置的动态下标，总有[left, lower)确定在区间1中
            int upper = right - 1; // 用于推进到pivot2最终位置的动态下标，总有(upper, right]确定在区间3中
            
            while(index <= upper) {
                if (arr[index] < arr[left]) {
                    swap(arr, index, lower); 
                    lower++;
                }
                else if(arr[index] > arr[right]) {
                    while(arr[upper] > arr[right] && index < upper) {
                        upper--;
                    }
                    swap(arr, index, upper);
                    upper--;
                    if(arr[index] < arr[left]) {
                        swap(arr, index, lower);
                        lower++;
                    }
                }
                index++; 
            }
            lower--;
            upper++;
            swap(arr, left, lower);
            swap(arr, upper, right);
            dualPivotQuickSort(arr, left, lower - 1); // 区间1
            dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2
            dualPivotQuickSort(arr, upper + 1, right); // 区间3
        }
    }
    
    public static void swap(int[] arr,int a,int b) {
    	if(a == b)return;
		arr[a] = arr[a]^arr[b];
		arr[b] = arr[a]^arr[b];
		arr[a] = arr[a]^arr[b];
	}
}

堆排序

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
import java.util.Arrays;

public class heap {
	public static void main(String[] args) {
		int[] arr = {8,4,5,9,11,40,5,9,16,85,32,47,99};
		heapsort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	private static void heapsort(int[] arr) {
		if(arr == null||arr.length<2)
			return;
		for(int i =1;i<arr.length;i++)
			heapInsert(arr, i);
	}
	private static void heapInsert(int[] arr,int i) {
		while (arr[i]>arr[(i-1)/2]) {
			swap(arr, i, (i-1)/2);
			i = (i-1)/2;
		}
	}
	public static void heapify(int[] arr,int index,int size) {
		int left = index*2+1;
		
		while (left<size) {
			int largest = left;
			if(left+1<size&&arr[left]<arr[left+1])
				largest = left+1;
			if(arr[index]>=arr[largest])
				break;
			swap(arr, index, largest);
			index = largest;
			left = index*2+1;
		}
	}
	
	
	public static void swap(int[] arr,int i,int j) {
		if(i == j)
			return;
		arr[i] = arr[i]^arr[j];
		arr[j] = arr[j]^arr[i];
		arr[i] = arr[j]^arr[i];
	}
}

字典树/前缀树

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
class Trie {

    class TireNode {
        private boolean isEnd;
        TireNode[] next;

        public TireNode() {
            isEnd = false;
            next = new TireNode[26];
        }
    }

    private TireNode root;

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

    public void insert(String word) {
        TireNode node = root;
        for (char c : word.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TireNode();
            }
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TireNode node = root;
        for (char c : word.toCharArray()) {
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TireNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        return true;
    }
}

AC自动机

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package 模板;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
public class ACauto {
    /*本示例中的AC自动机只处理英文类型的字符串，所以数组的长度是128*/
    private static final int ASCII = 128;
    /*AC自动机的根结点，根结点不存储任何字符信息*/
    private Node root;
    /*待查找的目标字符串集合*/
    private List<String> target;
    /*表示在文本字符串中查找的结果，key表示目标字符串， value表示目标字符串在文本串出现的位置*/
    private HashMap<String, List<Integer>> result;
    /*内部静态类，用于表示AC自动机的每个结点，在每个结点中我们并没有存储该结点对应的字符*/
    private static class Node{
        /*如果该结点是一个终点，即，从根结点到此结点表示了一个目标字符串，则str != null, 且str就表示该字符串*/
        String str;
        /*ASCII == 128, 所以这里相当于128叉树*/
        Node[] table = new Node[ASCII];
        /*当前结点的孩子结点不能匹配文本串中的某个字符时，下一个应该查找的结点*/
        Node fail;
        public Boolean isWord(){
            return str != null;
        }
    }
    /*target表示待查找的目标字符串集合*/
    public ACauto(List<String> target){
        root = new Node();
        this.target = target;
        buildTrieTree();
        build_AC_FromTrie();
    }
    /*由目标字符串构建Trie树*/
    private void buildTrieTree(){
        for (String targetStr : target){
            Node curr = root;
            for (int i = 0; i < targetStr.length(); i++){
                char ch = targetStr.charAt(i);
                if(curr.table[ch] == null){
                    curr.table[ch] = new Node();
                }
                curr = curr.table[ch];
            }
            /*将每个目标字符串的最后一个字符对应的结点变成终点*/
            curr.str = targetStr;
        }
    }
    /*由Trie树构建AC自动机，本质是一个自动机，相当于构建KMP算法的next数组*/
    private void build_AC_FromTrie(){
        /*广度优先遍历所使用的队列*/
        LinkedList<Node> queue = new LinkedList<Node>();
        /*单独处理根结点的所有孩子结点*/
        for (Node x : root.table){
            if(x != null){
                /*根结点的所有孩子结点的fail都指向根结点*/
                x.fail = root;
                queue.addLast(x);
                /*所有根结点的孩子结点入列*/
            }
        }
        while(!queue.isEmpty()){
            /*确定出列结点的所有孩子结点的fail的指向*/
            Node p = queue.removeFirst();
            for (int i = 0; i < p.table.length; i++){
                if(p.table[i] != null){
                    /*孩子结点入列*/
                    queue.addLast(p.table[i]);
                    /*从p.fail开始找起*/
                    Node failTo = p.fail;
                    while(true){
                        /*说明找到了根结点还没有找到*/
                        if(failTo == null){
                            p.table[i].fail = root;
                            break;
                        }
                        /*说明有公共前缀*/
                        if(failTo.table[i] != null){
                            p.table[i].fail = failTo.table[i];
                            break;
                        } else{
                            /*继续向上寻找*/
                            failTo = failTo.fail;
                        }
                    }
                }
            }
        }
    }
    /*在文本串中查找所有的目标字符串*/
    public HashMap<String, List<Integer>> find(String text){
        /*创建一个表示存储结果的对象*/
        result = new HashMap<String, List<Integer>>();
        for (String s : target){
            result.put(s, new LinkedList<Integer>());
        }
        Node curr = root;
        int i = 0;
        while(i < text.length()){
            /*文本串中的字符*/
            char ch = text.charAt(i);
            /*文本串中的字符和AC自动机中的字符进行比较*/
            if(curr.table[ch] != null){
                /*若相等，自动机进入下一状态*/
                curr = curr.table[ch];
                if(curr.isWord()){
                    result.get(curr.str).add(i - curr.str.length()+1);
                }
                /*这里很容易被忽视，因为一个目标串的中间某部分字符串可能正好包含另一个目标字符串，
         * 即使当前结点不表示一个目标字符串的终点，但到当前结点为止可能恰好包含了一个字符串*/
                if(curr.fail != null && curr.fail.isWord()){
                    result.get(curr.fail.str).add(i - curr.fail.str.length()+1);
                }
                /*索引自增，指向下一个文本串中的字符*/
                i++;
            } else{
                /*若不等，找到下一个应该比较的状态*/
                curr = curr.fail;
                /*到根结点还未找到，说明文本串中以ch作为结束的字符片段不是任何目标字符串的前缀，
         * 状态机重置，比较下一个字符*/
                if(curr == null){
                    curr = root;
                    i++;
                }
            }
        }
        return result;
    }
    public static void main(String[] args){
        List<String> target = new ArrayList<String>();
        target.add("abcdef");
        target.add("abhab");
        target.add("bcd");
        target.add("cde");
        target.add("cdfkcdf");
        String text = "bcabcdebcedfabcdefababkabhabk";
        ACauto aca = new ACauto(target);
        HashMap<String, List<Integer>> result = aca.find(text);
        System.out.println(text);
        for (Entry<String, List<Integer>> entry : result.entrySet()){
            System.out.println(entry.getKey()+" : " + entry.getValue());
        }
    }
}

洗牌算法

1
2
3
4
5
6
7
8
9
10
public static void xipai(int[] arr) {
	Random random = new Random();
	for(int i =arr.length-1;i>=1;i--) {
		int r = random.nextInt(i);
		System.out.println(arr[r]);
		int temp =  arr[r];
		arr[r] = arr[i];
		arr[i] = temp;
	}
}

并查集

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
public class 并查集 {
	static int[] arr;
	public static void main(String[] args) {
		arr = new int[10];
		init(arr.length);
		System.out.println(find(1)); //1
		union(1, 3);
		union(1, 5);
		if(find(1)==find(3)&&find(3)==find(5))
			System.out.println(find(1));//连上了
	}
	
	private static void init(int n) {
		for(int i =0;i<n;i++) {
			arr[i] = i;
		}
	}
	
	private static int find(int i) {
		if(arr[i] == i)
			return i ;
		else {
			arr[i] = find(arr[i]);
			return arr[i];
		}		
	}
	
	private static void union(int i,int j) {
		int i_fa = find(i);
		int j_fa = find(j);
		arr[i_fa] = j_fa;
	}
}

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家