算法

加油！！！

递归改写迭代

引入队列是递归改写程序常做方法，然后借助循环

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
//递归
public boolean isSymmetric(TreeNode root) {
    return check(root,root);
}

public boolean check(TreeNode left,TreeNode right){
    if (left==null&&right==null){
        return true;
    }
    if (left==null||right==null){
        return false;
    }
    return left.val== right.val&&check(left.left,right.right)&&check(left.right,right.left);
}


//上面递归方法改写成迭代，借助队列
public boolean isSymmetric(TreeNode root) {
    return check(root, root);
}

public boolean check(TreeNode u, TreeNode v) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(u);
    q.offer(v);
    while (!q.isEmpty()) {
        u = q.poll();
        v = q.poll();
        if (u == null && v == null) {
            continue;
        }
        if ((u == null || v == null) || (u.val != v.val)) {
            return false;
        }

        q.offer(u.left);
        q.offer(v.right);

        q.offer(u.right);
        q.offer(v.left);
    }
    return true;
}

分治法（递归）

分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

\1) 该问题的规模缩小到一定的程度就可以容易地解决

\2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

\3) 利用该问题分解出的子问题的解可以合并为该问题的解；

\4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

汉诺塔问题

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
package SuanFa.DiGuiFenZhi.HanNuoTa;

import java.util.Scanner;

public class HanNuoTa {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[1];
        hanoi(n,'a','b','c',ints);
        System.out.format("移动%d个盘子总共需要移动%d次盘子",n,ints[0]);
    }
    /*一个直接移动到c即可；两个就先把一个移动到b，再把最下面一个移动到c，然后把b上的移动到c即可；
    * 三个怎么办呢，可以想办法把最大的移动到c，再把剩下的移动到最大的上面，那怎么把最大的移动到c呢，
    * 要先把上面的都移动到b，怎么把上面的移动到b呢，
    * 这不就是只有两个的时候的情况吗，这样来看就是递归了*/

    //a为一开始在的柱子，b为中间柱子，c为最终放在的柱子,n为几个盘子
    public static void hanoi(int n,char a,char b,char c,int[] ints){
        //只有一个就从a直接移动到c
        if (n==1){
            move(n,a,c,ints);
            return;
        }
        //大于1个就把n-1个盘子借助c从a移动到b，之后递归了
        hanoi(n-1,a,c,b,ints);
        //然后把最下面也就是第n个盘子移动到c
        move(n,a,c,ints);
        //之后把b柱子上的盘子借助a柱子移动到c，也是递归
        hanoi(n-1,b,a,c,ints);
    }

    public static void move(int n,char a,char c,int[] ints){
        //一秒移动一个盘子，要把64个盘子移动完都可以移动到宇宙毁灭了
//        System.out.format("编号为：%d的盘子正在从%c柱子移动到%c柱子\n",n,a,c);
        ints[0]++;
    }
}

斐波那契

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构晶体结构、化学等领域，斐波那契数列都有直接的应用

  • 楼梯问题
  • 兔子繁殖问题（不死亡）
  • 兔子繁殖问题（会死亡）
  • 求解质数（基本方法有试除法和筛法，试除法除到根号n就好，规律），这里有斐波那契质数（ 若某Fibonacci数与任何比它小的Fibonacci数互质，那么它就是Fibonacci质数。可以保存到一个数组然后开始一个个推）

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
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
//1.爬楼梯问题（solve3）
package LeeCode;


/*假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？*/

import java.util.Scanner;

public class exercise70 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(solve1(n));
        System.out.println(solve2(n));
        System.out.println(solve3(n));
    }

    //动态规划
    //斐波那契问题除了爬楼梯还有兔子繁殖问题，满足f(n) = f(n-1) + f(n-2)就是

    //无脑，递归，能一次上3步同理,很耗时，超时，O(2^n),能一次上3步就是3^n
    public static int solve1(int n) {
        //0台阶一步
        if (n == 0) {
            return 1;
        }
        //1台阶就只有一种情况，爬一步
        if (n == 1) {
            return 1;
        }
        //2台阶两种情况，一种每次爬1步，一种直接爬2步
        if (n == 2) {
            return 2;
        }
        //多于2楼梯的就根据当前选择有不同情况，如爬了1级，那么剩下n-1
        int first = solve1(n - 1);
        //爬了2级,剩下n-2
        int second = solve1(n - 2);
        return first + second;
    }


    //通过分析上4次楼梯有多少情况发现有问题重叠计算了、
    //同斐波那契数列，可以用一个数组存结果，原理也同其实，4阶楼梯上法可以由3阶上楼梯方法推出来，3阶可以由2阶上楼梯方法推出来

    public static int solve2(int n) {
        //这里由于输入的n为1的话新建的数组根本没这么大，直接ints[2]直接错，
        // 可以做个判断或者把数组直接new很大出来，也可以直接new n+3长度就行，让数组最短都有3个格子
        int[] ints = new int[n+3];
        ints[0] = 1;
        ints[1] = 1;
        ints[2] = 2;

        for (int i = 3; i <= n ; i++) {
            ints[i] = ints[i-1] + ints[i-2];
        }
        return ints[n];
    }

    //上面还要建数组根本就不需要，就跟斐波那契一样，根本不需要去建数组，直接3个数轮换就可以求出来
    public static int solve3(int n){
        if (n==0){
            return 1;
        }
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        //n3表示第三个数，第三个数是前2个数n1和n2相加，然后把下次要相加的两个数往后移动n2变为n3，n1变为n2
        int n1 = 1, n2 = 2, n3 = 0;
        for (int i = 3; i <= n ; i++) {
            n3 = n2 + n1;
            n1 = n2;
            n2 = n3;
        }
        return n3;
    }

}

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
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
//2.兔子繁殖（会死亡），不死亡同前面其实
package SuanFa.FeiBoNaQie;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;


/*题目

有一对兔子，从出生后，
第 1、2 月为 幼年期
第 3 月开始，进入了 成年期，每个月都生一对 兔子
小兔子 长到 第3月 后，每个月又生一对兔子
当 一对兔子 在 第5月 时，他们产完仔之后，就会死亡*/

public class RabbitProblemWillDie {
    private static class Rabbit{

        int age = 1;

        void growUp() {
            this.age++;
        }
    }

    public int count(int month){
        //用队列很容易理解且比递归快
        Queue<Rabbit> queue = new ArrayDeque<>();
        queue.add(new Rabbit());
        int monthNow = 1;
        while (monthNow<month){
            int count = queue.size();
            while (count>0){
                Rabbit rabbit = queue.remove();
                switch (rabbit.age){
                    case 1:
                        rabbit.growUp();
                        queue.add(rabbit);
                        break;
                        //一起写就可以
                    case 2:
                    case 3:
                        rabbit.growUp();
                        queue.add(rabbit);
                        queue.add(new Rabbit());
                        break;
                        //4个月这个月变成5个月会死，并且生一只兔子
                    case 4:
                        queue.add(new Rabbit());
                        break;
                }
                count--;
            }
            monthNow++;
        }
        return queue.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        RabbitProblemWillDie dd = new RabbitProblemWillDie();
        System.out.println(dd.count(scanner.nextInt()));
    }

}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//3.求解质数
package SuanFa.FeiBoNaQie;

import java.util.Scanner;

//求解质数
public class Prime {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        System.out.println(isPrime(num));


        int range = scanner.nextInt();
        byte[] date = getAllPrime(range);
        for (int i = 2; i < date.length; i++) {
            if (date[i]==0){
                System.out.print(i+" ");
            }
        }
    }

    //试除法，优化除到根号n即可
    public static boolean isPrime(int num) {
        if (num==0||num==1){
            return false;
        }
        for (int i = 2; i<=Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    //筛法,返回一个范围内所有质数
    /*全称：The Sieve of Eratosthens（爱拉托逊斯筛选法），简称为筛法
    筛法就是把每一个质数的倍数去掉 余下的数就是质数
    2 是最小的质数，将 2 的所有倍数去掉，然后找 2 的下一个质数：3 ，将 3 的所有倍数去掉，寻找下一个质数：5 , 去掉 5 的所有倍数…以此类推*/
    public static byte[] getAllPrime(int range){
        byte[] date = new byte[range+1];
        for (int i = 2; i <= range ; i++) {
            if (date[i]==0){
                for (int j = 2; i*j <=range ; j++) {
                    date[i*j]=1;
                }
            }
        }
        //返回值为一个byte数组
        //从下标为2的值开始，值为0说明该下标数是质数
        return date;
    }
}

二分法

二分搜索算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//length是数组长度（数组有序，这里是升序，降序自己给一下变化就行），target是要查找的值
public static int BinarySearch(int[] ints,int length,int target){
        int left = 0,right = length-1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if (ints[mid]==target){
                return mid;
            }
            if (ints[mid]>target){
                right = mid-1;
            }
            if (ints[mid]<target){
                left = mid+1;
            }
        }
        return -1;
    }

排序算法

1.冒泡排序

数量少时选择，每轮把最大的数放在数组最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//冒泡排序 传入数组长度
   public static void BubbleSort(int[] ints, int length) {
       if (ints.length <= 1) {
           return;
       }
       //每次把最大的数放在最后一个
       for (int i = 0; i < length - 1; i++) {
           for (int j = 0; j < length - i - 1; j++) {
               if (ints[j] > ints[j + 1]) {
                   swap(ints, j, j + 1);
               }
           }
       }
   }
public static void swap(int[] ints, int left, int right) {
       int temp = ints[left];
       ints[left] = ints[right];
       ints[right] = temp;
   }

2.选择排序

选择排序就是每轮把剩余中最小的往前面已经放好的后面放，相对冒泡就是少了频繁交换,每次大循环就交换数组里面的值一次，每次把最小的放前面，用min保存当前循环的最小数值的下标就好，每轮循环min开始置为当前循环的i值就好，因为上一轮把最小的放在这里了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void SelectSort(int[] ints, int length) {
        for (int i = 0; i < length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < length; j++) {
                if (ints[min] > ints[j]) {
                    min = j;
                }
            }
            swap(ints, min, i);
        }
    }

public static void swap(int[] ints, int left, int right) {
        int temp = ints[left];
        ints[left] = ints[right];
        ints[right] = temp;
    }

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
31
32
33
34
35
36
//归并排序（合并排序） 需要同等大小的复制控件 传入数组的下标
    public static void MergeSort(int[] ints, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //不断划分子问题（分治思想）
            MergeSort(ints, left, mid, temp);
            MergeSort(ints, mid + 1, right, temp);
            //解决子问题并且把子问题的值从临时数组复制回原数组
            Merge(ints, left, mid, right, temp);
        }
    }

    public static void Merge(int[] ints, int start, int mid, int end, int[] temp) {
        int left = start, right = mid + 1, t = 0;
        //这里的循环条件考虑递归到最小的时候，也就是只有两个数的时候
        //下面是把两个有序数组进行合并
        while (left <= mid && right <= end) {
            if (ints[left] < ints[right]) {
                temp[t++] = ints[left++];
            } else {
                temp[t++] = ints[right++];
            }
        }
        while (left <= mid) {
            temp[t++] = ints[left++];
        }
        while (right <= end) {
            temp[t++] = ints[right++];
        }
        //临时数组保存的是当前这个子问题这个小段的正确顺序
        //下面是把临时数组中排好序的数组复制回原数组
        t = 0;
        for (int i = start; i <= end; i++) {
            ints[i] = temp[t++];
        }
    }

归并算法求逆序对

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
//
// Created by GTR on 2022/11/19.
//
#include <bits/stdc++.h>

using namespace std;

int sum = 0;//保存交换次数

//归并排序借助另一个数组合并的过程,先把两个串按照顺序合并放到临时数组再放回去
void merge(int *ints, int *temp, int start, int mid, int end) {
    int left = start, right = mid + 1, t = 0;
    while (left <= mid && right <= end) {
        if (ints[left] <= ints[right]) {
            //因为是最小，等会的情况不交换
            temp[t++] = ints[left++];
        } else {
            temp[t++] = ints[right++];
            sum+=(mid-left+1);
        }
    }
    while (left <= mid) {
        temp[t++] = ints[left++];
    }
    while (right <= end) {
        temp[t++] = ints[right++];
    }
    t = 0;
    for (int i = start; i <= end; ++i) {
        ints[i] = temp[t++];
    }
}

//归并排序
void mergeSort(int *ints, int *temp, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(ints, temp, left, mid);
        mergeSort(ints, temp, mid + 1, right);
        merge(ints, temp, left, mid, right);
    }
}


int main() {
    int n;
    cin >> n;
    int *ints = new int[n];
    int *temp = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> ints[i];
    }
    mergeSort(ints, temp, 0, n - 1);
    cout << sum << endl;
}

4.快速排序（双指针递归实现）

数量多时选择，一开始把基准值设为数组第一个值，每轮把基准值放在对的位置并把交换得到的值作为基准值

变形问题：

设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。（因为每轮的right值都会是放在正确位置的值，看right这个是不是对应下标，对可以直接返回了，根本不用全排序完，如果right大了递归左边的那段，小了递归右边半段，因为这时候左边的数都小于right下标的值，右边都大于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
//快速排序(递归) 传入数组的下标
    public static void QuickSort(int[] ints, int start, int end) {
        //一开始start<end记得写
        if (start < end) {
            int left = start, right = end, base = ints[left];
            while (left < right) {
                //这两个while都有等于作为判断条件
                //这里之所以写<=base是因为在交换一次不对的数字后没有把left和right直接改变，而是在下次的while中改变
                while (left <= end && ints[left] <= base) {
                    left++;
                }
                while (right > start && ints[right] >= base) {
                    //right>start其实可以不用写，因为前面有基准值堵住，不会超出去
                    right--;
                }
                //如果不是left<right说明序列正确
                if (left < right) {
                    swap(ints, left, right);
                }
            }
            //这里是遍历基准值后面的数结束了，这时候right在左边，left在右边或者left=right，
            // 这时候把基准值跟小的值交换才对，自己写个数组就明白了，小的值就是right对应的值
            swap(ints, start, right);
            //然后递归已经放置正确的值的左边和右边，也就是right这个值的左边和右边，
            // start衡为数组界限，如果right-1小于这个值不会进行循环，不会越界，right+1同理
            QuickSort(ints, start, right - 1);
            QuickSort(ints, right + 1, end);
        }
    }

    public static void swap(int[] ints, int left, int right) {
        int temp = ints[left];
        ints[left] = ints[right];
        ints[right] = temp;
    }

5.堆排序

数多时选择，每次都形成大顶堆，也就是数字最大的在父节点，每轮得到最大的放在数组最后并进行交换

首先要了解一下一些关系，下标为i的节点的父节点的下标为（i-1）/2,下标为i的节点的左孩子节点的下标为ix2+1,右孩子节点下标为ix2+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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//堆排序
	//方法入口
    public static void HeapSort(int[] ints, int length) {
        //建堆,一开始先把堆建好，之后递归就好
        int i;
        for (i = length / 2 - 1; i >= 0; i--) {
            //倒着建堆，根据规律父节点为（n-1）/2,注意这个方法传入的不是下标是长度，n要减多一个1
            Heap(ints, length, i);
        }

        //排序
        for (i = length - 1; i >= 0; i--) {
            //最后一个元素和第一个元素交换，就是把最大的数放到最后,swap方法在这个类最后面
            swap(ints, i, 0);
            //交换完成最大元素在最后，之后从堆顶开始维护堆，这里容易错，长度改变了
            Heap(ints, i, 0);
        }
    }

    public static void Heap(int[] ints, int length, int i) {
        //维护堆,length为数组长度,i为维护的目标节点

        //要把最大的那个数放在父节点
        int largest = i;
        //假设目前最大的是父节点，根据规律看哪个节点最大就记录它的下标
        int lson = i * 2 + 1, rson = i * 2 + 2;
        if (lson < length && ints[lson] > ints[largest]) {
            largest = lson;
        }
        if (rson < length && ints[rson] > ints[largest]) {
            largest = rson;
        }
        //判断最大节点是不是已经在父节点，不是就进行交换，并且要递归调整下面的堆
        if (largest != i) {
            swap(ints, largest, i);
            //这时候的largest记录的是被交换过来的不是最大的值的父节点的下标，容易出错
            Heap(ints, length, largest);
        }
    }

    public static void swap(int[] ints, int left, int right) {
        int temp = ints[left];
        ints[left] = ints[right];
        ints[right] = temp;
    }

线性时间选择算法

如果要要在一个数组中找到最大或者最小的数是可以轻易做到O(n)时间完成的，但如果要寻找中位数或者说寻找第几大的数看起来是非常难在O(n)时间完成的，但事实上从渐近的意义上来看，它们是一样的（线性时间选择算法是在快排的基础上实现的，也叫快速选择算法）

看了一下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
46
47
48
49
50
51
52
//设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。
#include<bits/stdc++.h>
using namespace std;

void swap(int *ints,int left,int right){
    int temp = ints[left];
    ints[left] = ints[right];
    ints[right] = temp;
}

void solve(int *ints,int target,int start,int end){
    if(start<end){
        int left = start,right = end,base = ints[left];
        while(left<right){
            while(left<end&&ints[left]<=base){
                left++;
            }
            while(right>start&&ints[right]>=base){
                right--;
            }
            if(left<right){
                swap(ints,left,right);
            }
        }
        swap(ints,start,right);
        //前面都是跟快排一样的，这里不同而已
        
        //这里通过下标看中间值也就是right值，right左边比right小，右边比right大，
        //如果要找到第几小的值在right左边就递归左边，反之递归右边
        if(right==target){
            return;
        }
        if(right<target){
            solve(ints,target,right+1,end);
        }
        if(right>target){
            solve(ints,target,start,right-1);
        }
    }
}

int main(){
    int length,target;
    cin >> length >> target;
    int *ints = new int[length];
    for(int i =0;i<length;i++){
        cin >> ints[i];
    }
    solve(ints,target-1,0,length-1);
    cout << ints[target-1] << endl;
    return 0;
}
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
#include <bits/stdc++.h>

using namespace std;

int n;//有n场比赛

int quickSort(int *ints, int start, int end, int target) {
    int left = start, right = end, base = ints[left];
    while (left < right) {
        while (left <= end && ints[left] <= base) {
            left++;
        }
        while (right > start && ints[right] >= base) {
            right--;
        }
        if (left < right) {
            swap(ints[left], ints[right]);
        }
    }
    swap(ints[start], ints[right]);
    if (right == target - 1) {
        return ints[right];
    } else if (right > target - 1) {
        return quickSort(ints, start, right - 1, target);
    } else {
        return quickSort(ints, right + 1, end, target);
    }
}


int main() {
    cin >> n;
    int *ints = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> ints[i];
    }
    int target;//目标寻找第target大的值
    cin >> target;
    cout << quickSort(ints, 0, n - 1, target);
    return 0;
}

贪心算法

贪心算法（greedy algorithm [8] ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。

把求解的问题分成若干个子问题，对每个子问题求解，得到子问题的局部最优解，把子问题的解局部最优解合成原来解问题的一个解。（贪心算法一般用来解决求最大或最小解，贪心算法只能确定某些问题的可行性范围，不能保证最佳，因为贪心算法总是从局部出发，并没从整体考虑）

  • 题目：121，找零问题（注意贪心是不是有最优解）（从大的零钱开始找）

  • 题目:删数问题（给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。）（从头开始，递减段的第一个数字删掉，因为这样会让后面小的数字上来顶替它）

  • 题目：最优分解问题（设 n 是一个正整数。现在要求将 n 分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。）

（整数的一个性质：若 a + b =N(常数)，则| a - b |越小， a * b 越大，因为要使乘积最大，所以要尽量分解为相似大小的数。 分解时，因数从2开始，每次加1，n=n-a[i]，保证剩下的数比下一次的数大。 否则从后往前循环（从前往后会出现相同数字，拿去10来看就知道了）已经出现的数a[i]，一次加1，知道n=0为止。 例如： 分解13 分解为 2 3 4 ，还剩下 4 ，不够继续分解的下一个数”5”，就把 4 依次分配给前面的因子， 分配顺序是 4 => 3 => 2 。所以最终结果为 3 4 6，这就是最大乘积的因子。 （分配顺序为从大到小，如果还剩下，就继续从大到小分配））

  • 在0-1背包的贪心算法模型中把物品质量和价格初始化为double类型最好，不然会因为int类型保存时有误差导致sort排序有时候不对

活动安排问题

学校的礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

输入格式：

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)

输出格式：

对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行

输入样例：

1
2
3
4
5
6
7
8
2
2
1 10
10 11
3
1 10
9 11
11 20

输出样例：

1
2
2
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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>

using namespace std;

int m;//m组测试数据
int n;//每组数据有n个活动

struct ac {
    int start;
    int end;
};

bool cmp(ac ac1, ac ac2) {
    return ac1.end < ac2.end;
}

int main() {
    cin >> m;
    int result, flag = 0;
    for (int i = 0; i < m; i++) {
        cin >> n;
        ac *p = new ac[n];
        for (int j = 0; j < n; j++) {
            cin >> p[j].start >> p[j].end;
        }
        sort(p, p + n, cmp);
        result = 1;
        int temp = 0;
        for (int j = 1; j < n; j++) {
            if (p[j].start >= p[temp].end) {
                result++;
                temp = j;
            }
        }
        if (!flag) {
            cout << result;
            flag = 1;
        } else {
            cout << endl << result;
        }
    }
    return 0;
}

活动安排进阶（需保存状态）

  • 保存状态的这个思想很重要，有些贪心的题目也用得上

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的
贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个
顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小
会场数。）

输入格式

第一行有 1 个正整数k，表示有 k个待安排的活动。
接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间
以 0 点开始的分钟计。

输出格式

输出最少会场数。

输入样例：

1
2
3
4
5
6
5
1 23
12 28
25 35
27 80
36 50

输出样例

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
36
37
38
39
40
41
42
43
44
45
46
//
// Created by GTR on 2022/10/29.
//
#include <bits/stdc++.h>

using namespace std;

int n;//代安排的活动数量

struct ac {
    int start;
    int end;
};

bool cmp(ac ac1, ac ac2) {
    return ac1.start < ac2.start;
}

int solve(ac *p) {
    sort(p, p + n, cmp);
    int *target = new int[n]{0};//保存当前会场信息
    int result = 0;//保存开了多少个会场
    for (int i = 0; i < n; ++i) {
        //j从会场0号下标开始遍历到result，如果能安排进去就结束了，如果不能就会到下标result对应会场，表示要新开会场
        for (int j = 0; j <= result; ++j) {
            if (j == result) {
                result++;
            }
            if (p[i].start >= target[j]) {
                target[j] = p[i].end;
                break;
            }
        }
    }
    return result;
}

int main() {
    cin >> n;
    ac *p = new ac[n];
    for (int i = 0; i < n; ++i) {
        cin >> p[i].start >> p[i].end;
    }
    cout << solve(p) << endl;
    return 0;
}

最优合并问题（借助优先队列）

  • 有时候借助优先队列解决更快和方便

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。
假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设
计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

输入格式：

第一行有 1 个正整数k，表示有 k个待合并序列。
第二行有 k个正整数，表示 k个待合并序列的长度。

输出格式：

输出最多比较次数和最少比较次数。

输入样例：

1
2
4
5 12 11 2

输出样例：

1
78 52

代码：

次数最少的情况就是尽量减少长的序列的比较次数(每次都让短的两个序列先比较)，而最大的情况就是尽量增加长的序列的比较次数(每次都让最长的两个序列比较)

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
//
// Created by GTR on 2022/11/5.
//
#include <bits/stdc++.h>

using namespace std;

void solve(priority_queue<int, vector<int>, greater<int>> small, int &small_result,
           priority_queue<int, vector<int>, less<int>> big, int &big_result) {
    int temp1, temp2;
    while (small.size() > 1) {
        temp1 = small.top();
        small.pop();
        temp2 = small.top();
        small.pop();
        small_result += (temp1 + temp2 - 1);
        small.push(temp1 + temp2);
        temp1 = big.top();
        big.pop();
        temp2 = big.top();
        big.pop();
        big_result += (temp1 + temp2 - 1);
        big.push(temp1 + temp2);
    }
}

int main() {
/*次数最少的情况就是尽量减少长的序列的比较次数(每次都让短的两个序列先比较),
    而最大的情况就是尽量增加长的序列的比较次数(每次都让最长的两个序列比较)*/
    int k, temp, small_result = 0, big_result = 0;
    cin >> k;
    priority_queue<int, vector<int>, greater<int>> small;
    priority_queue<int, vector<int>, less<int>> big;
    for (int i = 0; i < k; ++i) {
        cin >> temp;
        small.push(temp);
        big.push(temp);
    }
    solve(small, small_result, big, big_result);
    cout << big_result << " " << small_result << endl;
    return 0;
}

####图最短问题（迪杰斯特拉算法）

  • 单源最短路径

  • 迪杰斯特拉要求的图的权值要为正数

(26条消息) 算法之迪杰斯特拉（dijkstra）非常详细介绍_PRML_MAN的博客-CSDN博客_迪杰斯特拉

城市的道路四通八达，我们经常需要查找从某地出发到其他地方的路径，当然我们希望能最快到达。现得到去每个地方需要花费的时间，现请你编写程序，计算从特定地点出发到所有城市之间的最短时间。

输入格式：

输入的第一行给出城市数目N (1≤N≤10)和道路数目M和1（表示有向图）或0（表示无向图）；

接下来的M行对应每个城市间来往所需时间，每行给出3个正整数，分别是两个城市的编号（从1编号到N）和来往两城市间所需时间。最后一行给出一个编号，表示从此编号地点出发。

输出格式：

输出从特定地点出发到达所有城市（按编号1-编号N顺序输出）的距离（用编号1->编号**: 表示 ），如果无路，请输出no path。每个城市占一行。

输入样例：

1
2
3
4
5
6
4 4 1
1 2 2
1 4 8
3 2 16
3 4 10
1

输出样例：

1
2
3
4
1->1:0
1->2:2
1->3:no path
1->4:8

代码

//迪杰斯特拉算法,每次寻找图中到某个点最小的距离，更新和这个点相连的且没有被访问过的点，并把这个点置为已访问过，如果要知道具体路径就可以再增加一个数组保存前驱点（这个点最小值出现的时候也就是要刷新这个点的值的时候改变前驱点）,根据目的地一直往前驱找到起始点就是具体路径

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
//
// Created by GTR on 2022/11/9.
//

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;//邻接矩阵两个点没有相连定义初始化的值
int n;//城市数目1<=n<=10
int m;//图中路的条数
int target;//一开始指定的点
int kind;//表示图的种类，1表示有向图，0表示无向图，根据这个初始化邻接矩阵
int g[11][11];//邻接矩阵
int dist[11];//保存特殊路径长度，一开始初始化为定义的目标点到每个点的距离
bool visit[11];//是否被加进去集合遍历过

void Dijkstra() {
    //初始化
    for (int i = 1; i <= n; ++i) {
        visit[i] = false;
        dist[i] = g[target][i];
    }
    for (int t = 1; t <= n; ++t) {
        int point = -1, min = INF;//一开始让point为-1，如果在下面的循环中point依然为-1说明dist一开始全保存为INF，就是图所有点都是不相通的
        for (int i = 1; i <= n; ++i) {
            if (!visit[i] && dist[i] < min) {
                min = dist[i];
                point = i;
            }
        }
        if (point == -1) {
            break;
        }
        visit[point] = true;//加进集合，visit[point]置为true
        for (int i = 1; i <= n; ++i) {
            //之前遍历过的点就不用遍历了，因为已经保存了目标值到这个点的最小值了
            if (!visit[i] && dist[point] + g[point][i] < dist[i]) {
                dist[i] = dist[point] + g[point][i];
            }
        }
    }
}

int main() {
    cin >> n >> m >> kind;
    //初始化邻接矩阵
    for (int i = 0; i < 11; ++i) {
        for (int j = 0; j < 11; ++j) {
            g[i][j] = INF;
            if (i == j) {
                g[i][j] = 0;
            }
        }
    }
    //输入
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
        if (kind == 0) {
            g[b][a] = c;
        }
    }
    cin >> target;
    Dijkstra();
    for (int i = 1; i <= n; ++i) {
        if (dist[i] != INF) {
            cout << target << "->" << i << ":" << dist[i] << endl;
        } else {
            cout << target << "->" << i << ":" << "no path" << endl;
        }
    }
    return 0;
}

哈希映射

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

Example:

现在给出 n 个数(a[0],a[1],…,a[n-1])，且每个数的大小都是小于等于 10的10次方 的非负数(0<=a[i]<=1010)，现需要统计每个数的出现次数，并从小到大依次输出，且 n 是小于等于 100 的正整数(0<n<=100)。

基础解决方法：

对于这道题确实可以直接定义一个很长的数组，然后遍历输入的数，出现一次就在对应的下标的数组保存的值加1，这样子可以做到O(n)

的效率，算是优解了，但是这里的数最大为10的10次方，数组定义不了这么长

解决方法（发现问题）

那么就可以构造一个哈希函数通过一个映射关系压缩如此大的一个数组，因为这个数组里面很多值其实很多都是0来着，非常稀疏，例如H*(*k)=k mod m，取模，但是这种可能会出现碰撞冲突，如1%100=1，但101%100=1

解决问题（解决冲突）

解决碰撞冲突的思路有两个，其一是为冲突发生的情况下，设置新的规则来应对，比方说，如果出现冲突，那么就从冲突出现位置顺序往后找，直到找到一个空的位子，填上去；或者是隔几个位子跳着跳着找；又或者是在冲突出现的位置链接上一条链表，依次记录相同哈希值元素的出现次数。

1. 线性探测法

顾名思义，若出现冲突，则逐个往后或往前搜索，直到找到空的位子。假设现在又出现一个元素 20 经哈希函数后得到的映射结果也是位置 0 ，而发现该位置已被元素 10 所占据，那么就可以线性向后查找，直到找到第一个空的位置 2 ，然后放上去。(若找到了哈希表结尾，则回到开头继续向后查找，由于保证了哈希表的大小一定比元素总个数多，所以能保证每个元素都能找到自己的位置)

但这样有一个弊端就是，此时 20 占据了一个本不属于它的位置 2 ，如若下次来了一个本就映射到位置 2 的元素，那么它也只好继续向后探测，换句话说，虽然你解决了一个冲突，但同时又产生了另一个产生冲突的隐患，而且甚至还有可能出现无限冲突的情况。另一方面对于要在表中删除元素的情况，处理起来也不太方便。

2. 链地址法

这种思想是将所有映射到位置 i 的元素构建一条链表，并将单链表的头指针存在哈希表的第 i 个单元中，这样做的好处是一方面不会出现前面方法的那种解决一个哈希冲突，又带了新冲突隐患的问题，另一方面是在元素的删除上也能很好的处理，只需删除对应节点即可。但缺点也有，就是可能会在某个位置出现一条很长很长的链，增加了时间的开销。

3.再哈希法

这种方式是选取多个哈希函数，若第 j 个哈希函数出现了冲突，那么选用第 j+1 个哈希函数计算，直至找到不发生冲突的哈希函数。又或者使用同一个哈希函数，以上一轮产生的哈希值作为键值进行再次映射，直至找到可用的位置。

**4. 其他结局冲突方法 **

除了以上这些方法外，还有很多类似的方法，如平方探测法等等

解决问题（设计更好的哈希函数）

这类处理思路都是着重于当冲突发生的时候如何处理，此外，另一种解决冲突的思想便是在冲突发生之前尽可能的减少冲突的发生概率，即设计更好的哈希函数。

1. 使用更大的哈希表

不难想到，一张更大的哈希表能降低冲突发生的概率，以之前的简单哈希函数为例，极端情况是如果把 m 取得很大到 1010 时，那么显然就不会发生冲突了。一般而言，在经验和习惯上，会将哈希表的大小设置在元素个数的 1~10 倍之间，以实现在较小空间冗余的代价上，减小冲突的发生，提高时间效率。

2. 更好的哈希运算

之前提到的最简单的哈希函数，被称为除留余数法，可以说没有对键值 k 作任何的处理，直接进行了求余数，而如果我们加上些其它的运算，便能够使得映射更加复杂，以达到更随机的映射效果。例如下面的一阶线性映射：
H ( k ) = ( a × k + b ) m o d m ( a , m ∈ Z ) H(k) = (a×k + b)\ mod\ m (a,m \in Z)H(k)=(a×k+b) mod m(a,m∈Z)从理论上来说， a、b、m取不要太接近2的幂或10的幂的数会更好(同理前面简单取余的哈希函数里的 m 也一样)，冲突率更小，有兴趣的可以上网找找相关证明，这里之间简单说一下如果 m 取偶数，由于一个偶数对偶数取余结果仍然是偶数，这将导致所有的偶数元素只能映射到偶数位置，显然将会导致分布不均匀，容易出现冲突。
再来看看下面的乘法映射。
H ( k ) = ( A ⋅ k m o d 2 w ) r s h ( w − r ) H(k) = (A·k\ mod\ 2^w)\ rsh\ (w-r)H(k)=(A⋅k mod 2w) rsh (w−r)其中 m=2r ，w 表示计算机一个字的长度的bit位数，A 为奇数，且 2(w-r) < A < 2w(A不能太接近2w-r和2w)， rsh 指右移运算。
这是一个快速的哈希算法，介于编译器对这些二进制运算的优化，有兴趣的查阅相关资料，这里不做过多说明。

摩尔投票

摩尔投票法：摩尔投票法的核心思想为对拼消耗。首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数一半的数字（并且假设这个数字一定存在）。我们可以直接利用反证法证明这样的数字只可能有一个。

Example:

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

当然这题也可以直接sort排序然后因为最多的数超过一半长度，所以排序后中间的数一定是最大的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int majorityElement2(int[] nums,int length){
        if (length==1){
            return nums[0];
        }
        int result = nums[0],count = 1;
        for (int i = 1; i < length; i++) {
            if (count==0){
                result = nums[i];
                count = 1;
                continue;
            }
            if (nums[i]!=result){
                count--;
            }else {
                count++;
            }
        }
        return result;
    }

Example:

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/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
36
37
38
39
40
41
42
43
44
45
46
47
public static List<Integer> solve(int[] nums, int length){
        List<Integer> list = new ArrayList<>();
        if (nums==null||length==0){
            return list;
        }
        int count1 = 0,count2 = 0,result1 = nums[0],result2 = nums[0];
        for (int num:nums){
            //注意顺序逻辑，因为result1和result2一开始已经赋值了
            if (num==result1){
                count1++;
                continue;
            }
            if (num==result2){
                count2++;
                continue;
            }
            if (count1==0){
                result1=num;
                count1++;
                continue;
            }
            if (count2==0){
                result2 = num;
                count2++;
                continue;
            }
            count1--;
            count2--;
        }
        count1=0;
        count2=0;
        for (int i = 0; i < length; i++) {
            if (result1==nums[i]){
                count1++;
            }
            else if (result2==nums[i]){
                count2++;
            }
        }
        if (count1>length/3){
            list.add(result1);
        }
        if (count2>length/3){
            list.add(result2);
        }
        return list;

双指针技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 */

/*1、定义两个指针i和k，初始化i = 0，k = 0。
    2、i指针向后移动，遍整个nums数组，如果 nums[i] != 0，也就是说遇到了非0元素，此时我们就将nums[i]元素放置到nums[k]位置
    ，同时k++后一位。
    3、最后将k位置之后的元素都赋值为0。
    */
    public static void moveZeroes1(int[] nums, int length){
        int k=0;
        for (int i:nums){
            if (i!=0){
                nums[k++]=i;
            }
        }
        while (k<length){
            nums[k++]=0;
        }
    }
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
/*给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k 
，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。


输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
*/
public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        //如果length不大于三不会有三元组
        if (length <= 2) {
            return result;
        }
        //数组用Arrays.sort()排序，List用Collections.sort()排序
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            //当第一个数大于0，最后一个数为整数且是最大的，中间的数为多少三个数加起来都不会为0
            if (nums[i] > 0) {
                break;
            }
            //i=0时存在只有三个0的情况，这种情况满足，右边条件是去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //left为中间加数，i为左边加数，right为右边加数
            int left = i + 1, right = length - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    //下面两个while和left++，right--都是去重后得到正确的数
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (total < 0) {
                    left++;
                } else if (total > 0) {
                    right--;
                }

            }
        }
        return result;
    }

链表

####Floyd判圈算法（龟兔赛跑算法）

  • 可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法。
  1. 判断链表上是否存在环

设两个指针t和h已不同步伐（t一步h两步）从起点出发：如果快指针到达了链表尾部，两者都没相遇，则没有环。如果两个指针相遇，则有环。（快2步相当于快的走两圈，慢的走一圈，快的走一圈没有终点就会再走一圈跟慢的相遇）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle1(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}
  1. 求链表环的起点

两个指针相遇，设相遇点为M，让h指针留在M点，t指针回到原点head，两个指针同时已每次一步的步伐前进，再次相遇时即为环的起点。

  1. 链表环的长度

两个指针相遇，设相遇点为M，让h指针留在M点，t指针继续前进，每次一步。再次到达M点时，前进的步数即为环的长度。

双指针解决求相交链表问题

相交链表 - 相交链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//返回两个链表相交的节点
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

翻转链表（逆序输出）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//无脑list倒序输出即可,借助空间了
public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode result = head;
        while (result != null) {
            list.add(result);
            result = result.next;
        }
        result = list.get(list.size() - 1);
        head = result;
        for (int i = list.size() - 2; i >= 0; i--) {
            result.next = list.get(i);
            result = result.next;
        }
        //注意一开始节点的next为第二个节点，倒序后原第一个节点next为null才对
        result.next = null;
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
//其实完全没必要借助list，可以用一个节点保存前一个，遍历到下一个的时候把next转为上一个（迭代）
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null;
        ListNode now = head;
        while (now != null) {
            ListNode temp = now.next;
            now.next = pre;
            pre = now;
            now = temp;
        }
        return pre;
    }

判断是否是回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//先把链表的值全部复制到list判断    
public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode now = head;
        while (now != null) {
            list.add(now.val);
            now = now.next;
        }
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (!Objects.equals(list.get(left), list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

二叉树

关于树的几个术语： 节点，根节点，父节点，子节点，叶子节点，节点的权（节点值），路径（从root找到该节点的路线），层，子树，树的高度（最大层数），森林（多棵子树构成森林）

二叉树： 每个节点最多只有两个子节点，分为左子节点和右子节点

满二叉树： 如果一棵二叉树的叶子节点都在最后一层，且节点总数为2^n-1，n为层数

完全二叉树： 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称这为完全二叉树

**二叉查找树:*二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。判断一棵二叉树是不是二叉搜索树用递归写法（遍历传参包括当前允许最小值和最大值和当前判断节点，如果不在允许范围就返回false，然后递归左右子树，遍历传参更改范围值即可，递归左子树更改最大值，递归右子树更改最小值，只能说设计很巧妙）。*

关于二叉树代码（有备注）

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
package ShuJuJieGou;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Tree {
    public static void main(String[] args) {
        //测试
        //创建二叉树
        BinaryTree binaryTree = new BinaryTree();

        //创建需要的节点
        Node root = new Node(1, "宋江");
        binaryTree.setRoot(root);
        Node node1 = new Node(2, "吴用");
        Node node2 = new Node(3, "卢俊义");
        Node node3 = new Node(4, "林冲");

        //设置节点的关系，二叉树一般是遍历创建，这里是测试就手动创建了，主要看三中遍历
        root.setLeft(node1);
        root.setRight(node2);
        node2.setRight(node3);

        //测试
        System.out.println("前序遍历：");//1 2 3 4
        binaryTree.preOrder1();
        System.out.print("\n");
        binaryTree.preOrder2();
        System.out.print("\n");

        System.out.println("中序遍历：");//2 1 3 4
        binaryTree.midOrder1();
        System.out.print("\n");
        binaryTree.midOrder2();
        System.out.print("\n");

        System.out.println("后序遍历：");//2 4 3 1
        binaryTree.postOrder1();
        System.out.print("\n");
        binaryTree.postOrder2();
        System.out.print("\n");

        System.out.println("层次遍历：");//1 2 3 4
        binaryTree.floorOrder();
        System.out.print("\n");

        System.out.println("树的深度：");
        binaryTree.getDeep1();
        binaryTree.getDeep2();
    }
}

//二叉树类
class BinaryTree {
    //只要有根节点就可以进行遍历
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    //这个数的root节点是Node类型，带有Node类型的方法，也就是说只要把root确定就可以开始遍历
    /*递归*/
    //先序遍历
    public void preOrder1() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.preOrder1();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }

    //中序遍历
    public void midOrder1() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.midOrder1();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }


    }

    //后序遍历
    public void postOrder1() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.postOrder1();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }


    //这个数的root节点是Node类型，带有Node类型的方法，也就是说只要把root确定就可以开始遍历
    /*递归*/
    //先序遍历
    public void preOrder2() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.preOrder2();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }

    //中序遍历
    public void midOrder2() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.midOrder2();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }

    //后序遍历
    public void postOrder2() {
        //不为空才调用方法
        if (this.root != null) {
            this.root.postOrder2();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }

    /*层次遍历*/
    public void floorOrder() {
        if (this.root != null) {
            this.root.floorOrder();
        } else {
            System.out.println("当前二叉树为空，不能进行遍历");
        }
    }

    /*求树的最大深度*/
    //层次遍历基础上演变
    public void getDeep1() {
        if (this.root != null) {
            System.out.println(this.root.getDeep1());
        } else {
            System.out.println("当前树为空");
        }
    }

    //递归求解子树最大深度加1就是整棵树的最大深度
    public void getDeep2() {
        if (this.root != null) {
            System.out.println(this.root.getDeep2(this.root));
        } else {
            System.out.println("当前树为空");
        }
    }
}

//节点类
class Node {
    private int id;
    private String name;
    //不构造left和right，让左右节点默认为空,当然也可以构建，这样子就不需要left和right的get和set方法了，都一样其实
    private Node left;
    private Node right;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }


    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" + "id=" + id + ", name='" + name + '\'' + '}';
    }

    /*递归写法*/
    //前序遍历
    public void preOrder1() {
        //能进这个方法说明这个节点不为空
        //先输出父节点
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder1();
        }
        if (this.right != null) {
            this.right.preOrder1();
        }
    }

    //中序遍历
    public void midOrder1() {
        if (this.left != null) {
            this.left.midOrder1();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder1();
        }
    }

    //后序遍历
    public void postOrder1() {
        if (this.left != null) {
            this.left.postOrder1();
        }
        if (this.right != null) {
            this.right.postOrder1();
        }
        System.out.println(this);
    }

    /*迭代写法，借助栈*/
    //前序遍历,直接写法虽然简单，但为了统一还是用两个while这种吧，方便记忆，不过感觉都行
    public void preOrder2() {
        Stack<Node> stack = new Stack<>();

    /*        stack.push(this);
        while (!stack.empty()){
            Node node = stack.pop();
            System.out.format("%d %s\n",node.getId(),node.getName());
            //栈先进后出，为了让左孩子先出来就得让左孩子后入栈
            if (node.right!=null){
                stack.push(node.right);
            }
            if (node.left!=null){
                stack.push(node.left);
            }
        }*/

        Node node = this;
        while (node != null || !stack.empty()) {
            //这里输出过的节点要保存在栈中，因为还要回溯回来得到它的右节点，可以先得到它但不输出直接通过它拿到右节点
            while (node != null) {
                System.out.format("%d %s\n", node.getId(), node.getName());
                stack.push(node);
                node = node.left;
            }
            //左边输出完了要回溯右边，结束一次循环，换一棵子树
            node = stack.pop();
            node = node.right;
        }
    }

    //中序遍历
    public void midOrder2() {
        Stack<Node> stack = new Stack<>();
        Node node = this;
        while (node != null || !stack.empty()) {
            //每次都把最左边的节点放在最后
            //节点不为空时，把左子树的所有结点都入栈，因为栈是后进先出的，所以最后一个入栈的一定是当前二叉树左子树的最后一个结点
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            System.out.format("%d %s\n", node.getId(), node.getName());
            node = node.right;
        }
    }

    //后序遍历
    public void postOrder2() {
        Stack<Node> stack = new Stack<>();
        Node node = this;
        Node pre = null;//pre代表上一次已经处理完的节点
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (node.right == null || node.right == pre) {
                //此时右边树已经处理完，可以输出这个节点了
                System.out.format("%d %s\n", node.getId(), node.getName());
                pre = node;//node此时为处理完的节点
                node = null;//node处理完了要处理其他子树了，把node变成null，去获取栈里面上个节点
            } else {
                //说明这个节点右边有树要处理，把这个节点存起来先，且这个节点没有左树了，因为一开始一路向左，
               //这个节点是一棵树最左边那个
                stack.push(node);
                node = node.right;
            }
        }
    }

    /*层次遍历*/
    public void floorOrder() {
        Queue<Node> queue = new ArrayDeque<>();
        Node node = this;
        queue.offer(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.println(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /*求树的深度*/
    //在层次遍历的基础上求树的最大深度
    public int getDeep1() {
        Queue<Node> queue = new ArrayDeque<>();
        int count = 0;
        Node node = this;
        queue.offer(node);
        while (!queue.isEmpty()) {
            //next队列是存放下一层节点的，每存一层count++最后就可以根据count的数值知道树的深度
            Queue<Node> next = new ArrayDeque<>();
            //能进入循环说明存当前这层数据的队列不为空，层数+1
            count++;
            //队列被一直抛出，长度在减少，如果用队列长度判断是否结束会出错，可以一开始作为
            for (int i = queue.size(); i > 0; i--) {
                node = queue.poll();
                if (node.left != null) {
                    next.offer(node.left);
                }
                if (node.right != null) {
                    next.offer(node.right);
                }
                queue = next;
            }
        }
        return count;
    }

    //第二种求解深度的方法是得到最长的左右子数的深度加1即可，递归实现，深度更快
    public int getDeep2(Node node) {
        //判断传入的这个节点是否为空，为空返回0，不为空继续求这个节点的子树的深度
        if (node == null) {
            return 0;
        }
        return Math.max(getDeep2(node.left), getDeep2(node.right)) + 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
//层次遍历按照层添加节点值到list
public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue_now = new ArrayDeque<>();
        if (root != null) {
            queue_now.add(root);
            while (!queue_now.isEmpty()) {
                Queue<TreeNode> queue_next = new ArrayDeque<>();
                List<Integer> list = new ArrayList<>();
                int num = queue_now.size();
                while (num != 0) {
                    TreeNode node = queue_now.poll();
                    list.add(node.val);
                    if (node.left != null) {
                        queue_next.add(node.left);
                    }
                    if (node.right != null) {
                        queue_next.add(node.right);
                    }
                    num--;
                }
                queue_now = queue_next;
                result.add(list);
            }
        }
        return result;
    }

动态规划DP

首先认识备忘录方法

矩阵连乘问题

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
#include <bits/stdc++.h>

using namespace std;

//可以多建一个数组用来保存k的位置，也就是断开的位置

int DP_Solve(int *p, int n) {
    //从1开始填
    int target[n + 1][n + 1];
    //这里可以一开始初始斜对角为0也可以后面填充的时候再添加0
//    for (int i=1;i<=n;i++){
//        target[i][i]=0;
//    }
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            if (i == j) {
                target[i][j] = 0;
                continue;
            }
            target[i][j] = target[i][i] + target[i + 1][j] + p[i - 1] * p[i] * p[j];
            for (int k = i + 1; k < j; ++k) {
                int temp = target[i][k] + target[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (temp < target[i][j]) {
                    target[i][j] = temp;
                }
            }
        }
    }
    return target[1][n];
}

int main() {
    int n;
    cin >> n;
    int *p = new int[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        cin >> p[i];
    }
    cout << DP_Solve(p, n) << endl;
    return 0;
}

最长公共子序列，最长公共子串

  • 子串是连在一起的数字，而子序列是可以断开的

​ ababc和cbaab最长公共子串为2，而最长子序列为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
36
//最长子序列
#include <bits/stdc++.h>

using namespace std;

const int LENGTH = 101;

/*
 * 递归公式(target[i][j]表示第一个串长度为i,第二个串长度为j时最长子序列长度),i=1,j=1开始填表
 * 两个串最后一个值相等就相当于看前面n-1个子串最长子串值就是数组的值加1,否则就是第一个串减1长度保存的值或者第二个串减1长度保存的值
 * 当i=0时整一行为0,当j=0时整一列为0,递归先添加边界值,斜边从小到大添加
 * 当string1[i-1]=string2[j-1]时(i和j表示长度),target[i][j]=target[i-1][j-1]+1
 * 否则target[i][j] = max(target[i - 1][j], target[i][j - 1])
 */

int DP_Solve(string string1, string string2) {
    int target[LENGTH][LENGTH] = {0};
    for (int i = 1; i <= string1.size(); ++i) {
        for (int j = 1; j <= string2.size(); ++j) {
            if (string1[i - 1] == string2[j - 1]) {
                target[i][j] = target[i - 1][j - 1] + 1;
            } else {
                target[i][j] = max(target[i - 1][j], target[i][j - 1]);
            }
        }
    }
    return target[string1.size()][string2.size()];
}

int main() {
    string string1, string2;
    cin >> string1 >> string2;
    cout << DP_Solve(string1, string2) << endl;
    return 0;
}

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
//最长子串，可以用来优化前面的最长子序列，空间上更合理
#include <bits/stdc++.h>

using namespace std;


/*
 * 递归公式(target[i][j]表示第一个串下标为i,第二个串下标为j时最长子序列长度),i=0,j=0开始填表
 * 两个串最后一个值相等就相当于看前面n-1个子串最长子串值就是数组的值加1,否则就是0
 * 一开始把整个表初始化为0
 * 当string1[i]=string2[j]且i！=0,j!=0时(i和j表示下标),target[i][j]=target[i-1][j-1]+1
 * 当string1[i]=string2[j]且i和j有0时时(i和j表示下标),target[i][j]=1
 * 否则target[i][j] = 0*/

int DP_Solve(string string1, string string2) {
    int length1 = string1.size(), length2 = string2.size(), max = 0;
    int **target = new int *[length1];
    for (int i = 0; i < length1; ++i) {
        target[i] = new int[length2]{0};
    }
    for (int i = 0; i < length1; ++i) {
        for (int j = 0; j < length2; ++j) {
            if (string1[i] == string2[j]) {
                if (i != 0 && j != 0) {
                    target[i][j] = target[i - 1][j - 1] + 1;
                } else {
                    target[i][j] = 1;
                }
                if (target[i][j] > max) {
                    max = target[i][j];
                }
            }
        }
    }
    return max;
}

int main() {
    string string1, string2;
    cin >> string1 >> string2;
    cout << DP_Solve(string1, string2) << endl;
    return 0;
}

0-1背包问题

给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式：

共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式：

输出装入背包中物品的最大总价值。

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
//输入格式
5 10
2 6
2 3
6 5
5 4
4 6
//输出格式
15

    
//
#include<bits/stdc++.h>
using namespace std;

int n;//有n种物品
int c;//背包容量为n
int w[101];//物品i的重量
int v[101];//物品i的价值
int target[101][1001];/*
保存当前判断到第i个物品且剩余容量为j时最优值*/

/*(背包能装时，不能装直接跳过)target[i][j]=max(target[i+1][j],target[i+1][j-w[i]]+v[i]);
当只有一个物品时
target[n][j]=v[n];(还能装的时候)
target[n][j]=0(不能装了)*/

int DP_Solve(){
    for(int j=0;j<=c;j++){
        if(w[n]>j){
            target[n][j]=0;
        }else{
            target[n][j]=v[n];
        }
    }
    for(int i=n-1;i>=1;i--){
        for(int j=0;j<=c;j++){
            if(w[i]<=j){
                target[i][j]=max(target[i+1][j],target[i+1][j-w[i]]+v[i]);
            }else{
                target[i][j]=target[i+1][j];
            }
        }
    }
    return target[1][c];
}

int main(){
    cin >> n >> c;
    for(int i=1;i<=n;i++){
        cin >> w[i] >> v[i];
    }
    cout << DP_Solve();
    return 0;
}

图最短路问题（弗洛伊德算法）

回溯算法Backtrack

  • 回溯算法有“通用的解题法”之称，回溯实际上是一种试探算法，这种算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去，也就是说，它可以帮助我们避免走很多的弯路。

  • 回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。这也就意味着，想要采用回溯算法，就必须保证，每次都有多种尝试的可能。这种以深度优先方式系统搜索问题的算法称为回溯法，适合解组合数较大的问题

步骤

  • 定义解空间

​ 可以通过一维的向量来保存结果和要试的数

  • 试解

​ 试解的这个过程最主要的是要把这些数组织起来，一般是以解空间树这种形式组织起来，对于有n个数这棵树就会有n层，每层的这 个值有加进去结果集和不加进去两中情况并且是在上一层各个节点的情况下继续的，这样就形成了一棵能表示所有组合的一棵满二叉 树，只要以深度优先遍历整棵树就能得到所有的组合（这个解空间树是不用以一个数据结构搭建出来的）

​ 而仅仅知道解空间树还没有用，还需要避免在搜索结果都过程中避免无效搜索，这个过程叫剪枝，剪枝有两种方式，一种是约束函数 （扩展节点时剪去不满足约束的子树），一种是限界函数（剪去得不到最优解的子树）

​ 解空间树有三种典型的解空间树（三种问题种类）

子集树就是每个物品都去看选择与否组成最优解，而排列树是看n个点按照顺序不同有多少种的排列组合

    1. 子集树（0-1背包问题）
    2. 排列树（旅行售货员）

递归回溯写法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Backtrack(int t){
    //t表示当前为第几层(深度)
    //if为递归结束条件(t > n即为叶子节点)
    if(t > n){
        Output(x);
    }else{
        //f(n, t)，g(n, t)分别表示扩展结点的子树的起始编号和终止编号，尝试这些解
        for(int i = f(n, t); i <= g(n, t); i++){
            x[t] = h(i);//h(i)表示第i个可选值
            if(Constraint(t) && Bound(t)){
                //Constraint和Bound分别表示约束函数和限界函数
                Backtrack(t+1);//通过全局变量了解当前状态知道遍历到是哪个孩子节点
            }
        }
    }
}

子集树（0-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
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
//
// Created by GTR on 2022/11/19.
//
#include <bits/stdc++.h>

using namespace std;

struct good {
    int weight;
    int value;
};

int n;//n件物品
int c;//c为背包容量
int max_value = -1;//最大价值
int c_temp = 0, v_temp = 0;//存当前装入容量和价值
good *goods;//存货物信息
bool *result_max;//保存最优结果时这个点选不选，当到叶子节点时如果最大值被刷新就要更新这个数组
bool *visited;//保存遍历过程中这个点是否选择

//回溯算法
void Backtrack(int t) {
    //t>n表示走到叶子节点了
    if (t > n) {
        if (v_temp > max_value) {
            max_value = v_temp;
            //当最大价值被刷新才复制选择结果到最佳选择情况数组，不然就会到叶子节点就复制了
            for (int i = 1; i <= n; ++i) {
                result_max[i] = visited[i];
            }
        }
        return;
    } else {
        //else这一块代码也可以用一个循环来弄，n从0到1的循环，visited[t]=0表示不放，处理，visited[t]=1表示放，处理
        //选这个点，判断装进去会不会超，会肯定只能不选了，约束函数(条件)
        if (goods[t].weight + c_temp <= c) {
            c_temp += goods[t].weight;
            v_temp += goods[t].value;
            visited[t] = true;//选了它
            Backtrack(t + 1);
            //下面是递归回来，要回溯把选上的值全部不要了
            c_temp -= goods[t].weight;
            v_temp -= goods[t].value;
        }
        //不选这个点,那种就直接跳到下一层就可以了
        visited[t] = false;
        Backtrack(t + 1);
    }
}

int main() {
    cin >> n >> c;
    goods = new good[n + 1];
    result_max = new bool[n + 1];
    visited = new bool[n + 1];
    //从1号下标开始存东西
    for (int i = 1; i <= n; ++i) {
        cin >> goods[i].weight >> goods[i].value;
        result_max[i] = false;
        visited[i] = false;
    }
    Backtrack(1);
    cout << max_value << endl;
    for (int i = 1; i <= n; ++i) {
        if (result_max[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

有剪枝，约束函数(条件)加限界函数

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
//
// Created by GTR on 2022/11/19.
//
#include <bits/stdc++.h>

using namespace std;

struct good {
    int weight;
    int value;
    double unit_price;//单位价格
};

int n;//n件物品
int c;//c为背包容量
int max_value = -1;//最大价值
int c_temp = 0, v_temp = 0;//存当前装入容量和价值
good *goods;//存货物信息
bool *result_max;//保存最优结果时这个点选不选，当到叶子节点时如果最大值被刷新就要更新这个数组
bool *visited;//保存遍历过程中这个点是否选择

//排序规则，单位价值高的在前面
bool cmp(good good1, good good2) {
    return good1.unit_price > good2.unit_price;
}

/*限界函数，原理其实也很简单，就在一开始按照跟贪心一样的单位价格进行排序，
把剩下的要处理的点里面把单位价格高的物品装进去背包肯定能得到最高的价值，
虽然题目原本是不允许装一部分物品的，但如果最大可能性都比之前保存的最高价值小那肯定不用处理这棵子树了，处理了也是浪费时间*/
bool Bound(int t) {
    int temp = c_temp;
    double value = v_temp;
    for (int i = t; i <= n; ++i) {
        if (temp + goods[i].weight <= c) {
            temp += goods[i].weight;
            value += goods[i].value;
        } else {
            value += (c - temp) * goods[i].unit_price;
            break;
        }
    }
    if (value > max_value) {
        return true;
    }
    return false;
}

//回溯算法
void Backtrack(int t) {
    //t>n表示走到叶子节点了
    if (t > n) {
        if (v_temp > max_value) {
            max_value = v_temp;
            //当最大价值被刷新才复制选择结果到最佳选择情况数组，不然就会到叶子节点就复制了
            for (int i = 1; i <= n; ++i) {
                result_max[i] = visited[i];
            }
        }
        return;
    } else {
        //else这一块代码也可以用一个循环来弄，n从0到1的循环，visited[t]=0表示不放，处理，visited[t]=1表示放，处理
        //选这个点，判断装进去会不会超，会肯定只能不选了，约束函数(条件)
        if (goods[t].weight + c_temp <= c) {
            c_temp += goods[t].weight;
            v_temp += goods[t].value;
            visited[t] = true;//选了它
            Backtrack(t + 1);
            //下面是递归回来，要回溯把选上的值全部不要了
            c_temp -= goods[t].weight;
            v_temp -= goods[t].value;
            visited[t] = false;
        }
        //不选这个点,那种就直接跳到下一层就可以了,限界函数Bound
        if (Bound(t + 1)) {
            Backtrack(t + 1);
        }
    }
}

int main() {
    cin >> n >> c;
    goods = new good[n + 1];
    result_max = new bool[n + 1];
    visited = new bool[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> goods[i].weight >> goods[i].value;
        goods[i].unit_price = (double) goods[i].value / (double) goods[i].weight;
        result_max[i] = false;
        visited[i] = false;
    }
    sort(goods + 1, goods + n + 1, cmp);
    Backtrack(1);
    cout << max_value << endl;
    for (int i = 1; i <= n; ++i) {
        if (result_max[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

####排列树（旅行售货员）

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。

输入格式:

第一行为城市数n

下面n行n列给出一个完全有向图，如 i 行 j 列表示第 i 个城市到第 j 个城市的距离。

输出格式:

一个数字，表示最短路程长度。

输入样例:

1
2
3
4
3
0 2 1
1 0 2
2 1 0

输出样例:

1
3

理解：

这道题和前面的子集树最明显的不同就是子集树主要是针对某个点的选择与不选，是一颗满二叉树，但这题就不是了，这道题要知道的是n个点的排列组合（这里假设都是从点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
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
//
// Created by GTR on 2022/11/23.
//
#include <bits/stdc++.h>

using namespace std;

int n;//城市点的个数
int *best;//记录最短路径的排列
int dis_min = 0x3f3f3f3f;//记录最短路径的长度

int *dis;//记录遍历过程中保存的节点和路径信息
int *vist;//记录遍历过的信息
int dis_temp = 0;
int **g;//保存图

//递归到第t层
void backTrack(int t) {
    //叶子节点
    if (t > n) {
        //注意这里是g[dis[t-1]][1]或者g[dis[n]][1],最后一个点，而不是直接n
        if (dis_temp + g[dis[t-1]][1] < dis_min) {
            dis_min = dis_temp + g[dis[t-1]][1];//判断条件和这一句可以写g[dis[n]][1]的，一样的，dis是保存这次遍历的路径信息的，
            // 可以通过dis[t]确认当前添加到点，那么dis[t-1]自然就是上次添加到点了
            for (int i = 1; i <= n; ++i) {
                best[i] = dis[i];
            }
        }
        return;
    }
    //代码初始化后都以第一个点为起始点，并把visit[1]置为1了，这个循环是按照题目来的，把每个点都当做第二个点为开始遍历点，
    //遍历到就把visit中对应的点置为1即可，在递归中就不会再查找找过的点，这样子就能遍历完所有的点，最后回溯即可换另一个点进行遍历了
    for (int i = 1; i <= n; ++i) {
        if (vist[i] == 0) {
            vist[i] = 1;
            dis[t] = i;
            dis_temp += g[dis[t-1]][i];
            //约束函数
            if (dis_temp < dis_min) {
                backTrack(t + 1);
            }
            //回溯
            vist[i] = 0;
            dis_temp -= g[dis[t - 1]][i];
        }
    }
}

int main() {
    cin >> n;
    g = new int *[n + 1];//从1开始
    best = new int[n + 1]{0};
    dis = new int[n + 1]{0};
    vist = new int[n + 1]{0};
    for (int i = 0; i <= n; ++i) {
        g[i] = new int[n + 1];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
        }
    }
    best[1] = 1;
    dis[1] = 1;
    vist[1] = 1;//这个很容易忘记
    backTrack(2);
//    for (int i = 1; i <= n; ++i) {
//        cout << best[i] << " ";
//    }
    cout << dis_min << endl;
    return 0;
}

k叉树（n后问题）

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上

输入格式:

一个数字n

输出格式:

按照深度优先输出所有可行的解

输入样例:

1
4

输出样例:

1
2
2 4 1 3 
3 1 4 2

理解

对于每一行都可以把棋子放在任何一个地方，这样可以构成一棵n叉树

我们从第一行开始放皇后，每一行只能放一个皇后，这样就不用考虑行会冲突了，而列就可以通过路径数组（result数组）来判断前面有没有放过这一列，斜线的话就可以根据三角形性质，当两个点的横坐标的相差（就是绝对值）和纵坐标相差相等就在一条斜线上来判断（这两个条件构成约束函数），当到达最后一行直接输出路径即可

其实也可以用求排列的思想来实现，行和列都不同，那所有点就是一个排列，最后判断是不是所有点都不在斜线上即可

代码:

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
//
// Created by GTR on 2022/11/30.
//
#include <bits/stdc++.h>

using namespace std;

int n;//有几个皇后
int *result;//保存结果，下标从1开始

//判断本次这一行把这个数字放进能不能成立
bool check(int t) {
    for (int i = 1; i < t; ++i) {
        if ((result[i] == result[t]) || (abs(result[t] - result[i]) == abs(t - i))) {
            return false;
        }
    }
    return true;
}

void backTrack(int t) {
    if (t > n) {
        for (int i = 1; i <= n; ++i) {
            cout << result[i] << " ";
        }
        cout << endl;
        return;
    }
    //n叉树
    for (int i = 1; i <= n; ++i) {
        //一行一行放的，一行放一个，所以不用考虑有行冲突
        result[t] = i;
        if (check(t)) {
            backTrack(t + 1);
        }
    }
}

int main() {
    cin >> n;
    //result[i]表示第i行放在哪一列
    result = new int[n + 1]{0};
    backTrack(1);
    return 0;
}

二维递归回溯（求解数独）

  • 本身也是k叉树，但是比n后问题多一个维度，因为n后问题每次递归其实就是完成一行，递归可以看成是行遍历，而递归中填写这一行是遍历这一行中每个点，可以看成是列遍历，对于每个点就是简单的放与不放皇后（一个循环就可以解决），但数独还要看是填哪个数字

返回值为bool类型，因为其实只要得到一个数独的解就可以返回了

终止条件其实也在下面的处理逻辑中给包含了，只有放满才会返回true，否则就返回false，一定会有返回值

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
//判断数独填写过程中这个数字能不能填
//line第一行,row第几列
bool isWriteAvailable(int line, int row, int **target) {
    //同列不能有相同数字，i==line就是同个格子来的
    for (int i = 1; i <= ROW_NUM; ++i) {
        if (i != line && target[i][row] == target[line][row]) {
            return false;
        }
    }
    //同行不能有相同数字，j==row就是同个格子来的
    for (int j = 1; j <= ROW_NUM; ++j) {
        if (j != row && target[line][j] == target[line][row]) {
            return false;
        }
    }
    //规定的九个格子里面数字各不相同,可以找到这个格子所在的块的左上角这个坐标
    //根据这个格子是第几行求出对于九个格子其实点的行坐标
    int temp1 = line / 3;
    int temp2 = line % 3;
    int start1;
    if (temp2 > 0) {
        start1 = temp1 * 3 + 1;
    } else {
        start1 = (temp1 - 1) * 3 + 1;
    }
    //根据这个格子是第几列求出对于九个格子其实点的列坐标
    int temp3 = row / 3;
    int temp4 = row % 3;
    int start2;
    if (temp4 > 0) {
        start2 = temp3 * 3 + 1;
    } else {
        start2 = (temp3 - 1) * 3 + 1;
    }
    //开始判断所在块是否符合,不在目标格子并且周围的数字跟它相同就不能放进去
    for (int i = start1; i < start1 + 3; ++i) {
        for (int j = start2; j < start2 + 3; ++j) {
            if (i != line && j != row && target[i][j] == target[line][row]) {
                return false;
            }
        }
    }
    //上面条件都满足就走到这里，返回true即可
    return true;
}

//求解算法
bool solveSudoku(int **target) {
    //两层循环去找哪个格子未填数字就去填这个格子
    for (int i = 1; i <= ROW_NUM; ++i) {
        for (int j = 1; j <= ROW_NUM; ++j) {
            if (target[i][j] == 0) {
                //填数字,1到9
                for (int k = 1; k <= ROW_NUM; ++k) {
                    target[i][j] = k;//先填，填完去判断填进去成不成立，成立递归
                    if (isWriteAvailable(i, j, target)) {
                        if(solveSudoku(target)){
                            return true;
                        }
                    }
                    //如果下一层没有得到结果就要回到这里，那么就找另一个数字去填看能不能成功，如果下一层成功就直接return了，走不到这里
                    target[i][j] = 0;//回溯
                }
                return false;
            }
        }
    }
    //所有格子能填完直接返回true
    return true;
}

一些例题（这里是很典型能看出区别的）

子集合问题（子集树）

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。

输入格式:

输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出格式:

输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。

输入样例:

在这里给出一组输入。例如：

1
2
5 10
2 2 6 5 4

输出样例:

在这里给出相应的输出。例如：

1
2 2 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
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
//
// Created by GTR on 2022/11/19.
//
#include <bits/stdc++.h>

using namespace std;

int n;//集合元素个数
int target;//目标子集合的合
int temp = 0;
int *ints;//保存集合
bool *result;//保存结果
bool *visited;//保存递归过程中的状态
bool flag = false;

//遍历右子树也就是不选时如果所有值加起来都没有目标值大就没必要递归了，限界函数
bool Bound(int t) {
    int sum = temp;
    for (int i = t; i < n; ++i) {
        sum += ints[i];
    }
    if (sum < target) {
        return false;
    }
    return true;
}

void Backtrack(int t) {
    if (temp == target) {
        flag = true;
        for (int i = 0; i < n; ++i) {
            result[i] = visited[i];
        }
        return;
    }
    //约束函数
    if (t < n && !flag && temp < target) {
        temp += ints[t];
        visited[t] = true;
        Backtrack(t + 1);
        temp -= ints[t];
        visited[t] = false;
        if (Bound(t + 1)) {
            Backtrack(t + 1);
        }
    }
}

int main() {
    cin >> n >> target;
    ints = new int[n];
    result = new bool[n];
    visited = new bool[n];
    for (int i = 0; i < n; ++i) {
        cin >> ints[i];
        result[i] = false;
        visited[i] = false;
    }
    Backtrack(0);
    if (flag) {
        for (int i = 0; i < n; ++i) {
            if (result[i]) {
                cout << ints[i] << " ";
            }
        }
    } else {
        cout << "No Solution!";
    }
    return 0;
}

全排列

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1,a2,⋯,a**n排在序列b1,b2,⋯,b**n之前，如果存在k使得a1=b1,⋯,a**k=b**k 并且 a**k+1<b**k+1。

输入样例：

1
3

输出样例：

1
2
3
4
5
6
123
132
213
231
312
321

代码：

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
//
// Created by GTR on 2022/11/23.
//
#include <bits/stdc++.h>

using namespace std;

int n;//从1到n全排列
int *visited;//标记是否遍历过，这题就从大到小假设一开始就进入一个点然后递归遍历其他点即可
int *temp;//保存遍历过程结果
int flag = 0;//标记要不要输出回车的


void backTrack(int t) {
    //遍历到最后一层，直接输出即可
    if (t > n) {
        if (!flag) {
            flag = 1;
        } else {
            cout << endl;
        }
        for (int i = 1; i <= n; ++i) {
            cout << temp[i];
        }
        return;
    }
    //不是最后一层就是遍历其他点
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            visited[i] = 1;
            temp[t] = i;
            backTrack(t + 1);
            visited[i] = 0;//回溯
        }
    }
}

int main() {
    cin >> n;
    visited = new int[n + 1]{0};
    temp = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
        visited[i] = 1;
        temp[1] = i;
        backTrack(2);
        visited[i] = 0;//这轮结束把一开始的点改为未访问，下一轮换点为初始点
    }
    return 0;
}

回溯法总结

  • 求子集：从n个元素的集合S中找出满足某个性质的子集。（每个节点都是可选或者不选的）其搜索树称为子集树，是典型的二叉树，通常有2^n个叶子节点，遍历时间为O（2^n）

  • 求排列：n个节点的排列组合。（每个节点都包括在内，顺序不同罢了）其中搜索树称为排列树，通常有n!个叶子节点，因此遍历排列树需要时间为O（n!），这个算法有两种书写方法，还是习惯用visit数组保存遍历过节点信息的方法，都是从第二层开始遍历

  • 求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为k叉树，其节点总数为k^(n+1)-1，遍历的时间为O（k^n）,每层都可以选n个点中的任意一个，以n后问题来看，其实也可以用求排列的思想来实现，行和列都不同，那所有点就是一个排列，最后判断是不是所有点都不在斜线上即可

分支限界法

相较于回溯法就是广度优先遍历

  • 队列式分支限界法

  • 优先队列式分支限界法

0-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
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
//
// Created by GTR on 2022/12/10.
//
#include <bits/stdc++.h>

using namespace std;

struct good {
    int weight;
    int value;
    double average;
};//物品信息
struct node {
    int temp_value;//当前价值
    int remain;//剩余
    int deep;//层数
};//扩展节点
int n;//物品个数
int c;//背包容量
good *goods;//保存物品信息
int max_value = 0;//最大价值

//sort排序规则
bool cmp(good good1, good good2) {
    return good1.average > good2.average;
}

//减枝，限界函数
bool bound(node *node) {
    double sum = node->temp_value;
    int temp = node->remain;
    for (int i = node->deep + 1; i <= n; ++i) {
        if (goods[i].weight <= temp) {
            temp -= goods[i].weight;
            sum += goods[i].value;
        } else {
            sum += goods[i].average * temp;
            break;
        }
    }
    if (sum < max_value) {
        return false;
    }
    return true;
}

//分支限界法
void dfs(node *head) {
    queue<node *> queue;
    queue.push(head);
    while (!queue.empty()) {
        node *temp = queue.front();
        queue.pop();
        max_value = max(max_value, temp->temp_value);
        if (temp->deep < n && goods[temp->deep + 1].weight <= temp->remain) {
            node *left_child = new node;
            left_child->deep = temp->deep + 1;
            left_child->remain = temp->remain - goods[left_child->deep].weight;
            left_child->temp_value = temp->temp_value + goods[left_child->deep].value;
            queue.push(left_child);
            max_value = max(max_value, left_child->temp_value);
        }
        if (temp->deep < n && bound(temp)) {
            node *right_child = new node;
            right_child->deep = temp->deep + 1;
            right_child->remain = temp->remain;
            right_child->temp_value = temp->temp_value;
            queue.push(right_child);
        }
    }
}

int main() {
    cin >> n >> c;
    goods = new good[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> goods[i].weight >> goods[i].value;
        goods[i].average = double(goods[i].value) / goods[i].weight;
    }
    sort(goods + 1, goods + n + 1, cmp);
    node *head = new node;
    head->deep = 0;
    head->temp_value = 0;
    head->remain = c;
    dfs(head);
    cout << max_value << endl;
    return 0;
}

八数码问题八重境界

境界二（广搜+哈希（康托展开））：

力扣做题遇到技巧总结

借助前面的数求解当前值，时间为1

338题

如果题目叫尝试空间复杂度为1的话要记录可以借助题目给定范围之外的数字

448题

备注一下

贪心算法和动态规划有个不同的就是动态规划后面的子问题不会影响前面子问题，但贪心算法就会，比如力扣121很明显最小值会改变并且后面的结果依靠新的最小值，后面的子问题跟前面的就没关系了

11题自己想用贪心写不出来，后面回去看看

79回溯

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

src:源数组;

srcPos:源数组要复制的起始位置;

dest:目的数组;

destPos:目的数组放置的起始位置;

length:复制的长度.