算法整理

2021-09-20

 图

每个节点有2种状态，不要boolean[] isVisited, boolean[] isEnd两个数组

直接int[] status，用2种数字来表示状态

dfs

递归的思想有2种：

  1. 对自己进行条件判断，对下面的小弟无脑入
  2. 不必判断自己，对下面的小弟进行条件判断后，筛选进入

dfs或者递归的思路是从f(n)推向f(n+1)的各种情况

即：发散

dp

动态规划就是总结有哪些f(n-1)的情况会导致f(n+1)

即：归纳

注意在使用dfs或者dp时，尽量用“状态”而非“操作”

因为：由于某个“操作”导致某个“状态”，所以只要把最后的状态保留即可

数组

数组链表

数组nums的长度为n

但是里面的数字范围为1-n，其中n表示末尾（因为nums[n]就超出了）

这种情况下，这个链表是没有“环”的

什么情况下会有环？

数字范围1 ~ (n-1) ，

因为如果有数字等于n的话，就跳出去了

int[] nums = {1,2,3,4,5}; //没有环
int[] nums2 = {1,4,5,2,3}; //没有环
int[] nums3 = {1,4,3,2,2}; //有环

i = 0;
while(i != nums.length) {
    i = nums[i];
}

排序

快排

partition流程：

  1. 选一个标兵p

  2. i从左往右找到比p大的

  3. j从右往左找到比p小的

  4. swap（i，j），回到步骤2

  5. 上述的流程保证了i之前的元素（不包括i）都是小于等于p的

    而j之后的元素（不包括j）都是大于等于p的

  6. 最后j在i左边，把标兵和i-1的位置上的元素交换一下

import java.util.Arrays;

public class QuickSort {


    public static void main(String[] args) {
        int[] data = {10, 3, 15, 5, 18};
//        int[] data = {10};

//        partition(data,0,data.length-1);
        qsort(data, 0, data.length - 1);

        System.out.println(Arrays.toString(data));


    }


    public static void qsort(int[] data, int left, int right) {
        if(left>=right){
            return;
        }
        
        int i = partition(data, left, right);
        qsort(data, left, i - 1);
        qsort(data, i + 1, right);

    }


    public static int partition(int[] data, int left, int right) {
        int p = data[left];
        int i = left;
        int j = right;

        while (i <= j) {
            while (i <= j && data[i] <= p) {
                i++;
            }
            while (i <= j && data[j] >= p) {
                j--;
            }

            if (i < j) {
                swap(data, i, j);
                ++i;
                ++j;
            }
        }

        swap(data, left, i - 1);
        return i - 1;
    }


    public static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

插入排序

public static void insertSort(int[] a){
    for(int i=1;i<a.length;++i){
        int tmp = a[i];
        int j=i-1;
        for(;j>=0&&a[j]>tmp;--j){
            a[j+1] = a[j];
        }
        a[j+1] = tmp;
    }
}

希尔排序

public static void shellSort(int[] a){
    for(int gap=a.length/2;gap>=1;gap/=2){
        for(int i=gap;i<a.length;++i){
            int tmp = a[i];
            int j = i-gap;
            for(;j>=0&&a[j]>tmp;j-=gap){
                a[j+gap] = a[j];
            }
            a[j+gap] = tmp;
        }
    }
}

排序技巧

场景:

背包问题

有一个代表物品价值的数组

int[] values;

有一个代表物品重量的数组

int[] weights;

现在我建造想让这两个数组按照**单位价值(value/weight)**排序

写法1: 放到一个类里面

// 放到一个类里面
class Thing{
    int value;
    int weight;
    double density;
    Thing(int value, int weight, double density){
        this.value = value;
        this.weight = weight;
        this.density = density;
    }
}

int limit = 15;
int[] values = {4,5,23,7};
int[] weights = {3,7,10,3};

Thing[] things = new Thing[valus.length];
for(int i=0;i<things.length;++i){
    things[i] = new Thing(values[i],weight[i], values[i]/(double)weight[i]);
}

Arrays.sort(things, Comparator.compareDouble(a->a.density));

// 这样写一般是可以的
// 唯一的缺点是: 我不知道原来的下标跟现在的下标的对应关系

// 比如说:我想用一个向量表示物品被选取了多少
double[] res = new double[values.length];
// 现在下标乱掉了, 对应不起来

写法2: 对下标进行排序

int limit = 15;
int[] values = {4,5,23,7};
int[] weights = {3,7,10,3};


Integer[] idx = new Integer[values.length]; //每个物品的下标
for(int i=0;i<idx.length;++i){
    idx[i] = i;
}

// 对下标进行排序, ok
Arrays.sort(idx, Comparator.comparingDouble(i->values[i]/(double)weights[i]));


// 答案下标
double[] res = new double[values.length];
for(int i : idx){
    if(weight[i] < limit){
        limit -= weight[i];
        res[i] = 1;
    }else{
        limit = 0;
        res[i] = limit/(double)weight[i];
        break;
    }
}

System.out.println(Arrays.toStrig(res));

最长回文子串

贪心算法

通常需要进行排序

特点:

  1. 最优子结构性质: 整体最优包含子结构最优

  2. 贪心选择性质: 一步步贪心选择可以达到最优解

动态规划

特点:

  1. 最优子结构性质: 整体最优包含子结构最优
  2. 子机构重叠&子结构空间小(所以可以遍历所有子结构来得到总体最优)

回溯 – dfs

全排列

给出平面上的n个点，现在需要你求出，在这n个点里选3个点能构成一个三角形的方案有几种。



输入描述:
第一行包含一个正整数n，表示平面上有n个点（n <= 100)
第2行到第n + 1行，每行有两个整数，表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100，且保证所有坐标不同）

输出描述:
输出一个数，表示能构成三角形的方案数。

输入例子1:
4
0 0
0 1
1 0
1 1

输出例子1:
4

例子说明1:
4个点中任意选择3个都能构成三角形
// 也就是说, 要从一堆点中拿出3个点
// 相当于C(3,n)
// 可以用dfs, 比如先拿第1个位置, 再在后面拿剩下的2个

public class Main{
    public static Point[] points; // 解空间(可以选的分支)
    public static ArrayList<Point> container = new ArrayList<>(); // 记录当前的搜索路径
    public static int count = 0;  // 可行路径的个数

	// k: 还要拿几个点
	// next_loc: 下一次从哪个位置开始拿
    public static void dfs(int k, int next_loc){
        // 终止条件
        if(k==0){
            if(isTriangle(container.get(0),container.get(1),container.get(2))){
                count++;//答案数量++
            }
        }

        // 剪枝: 要拿的点的数量超过了剩下的点的数量
        if( k > (points.length - next_loc)) return;


        //  dfs
        for (int i = next_loc; i < points.length; i++) {
            container.add(points[i]); //扩展搜索路径
            dfs(k-1, i+1);
            container.remove(container.size()-1); //回溯
        }
    }
    
}

图的最短路径(dijkstra)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main2 {

    public static void main(String[] args) {
        System.out.println(f());
    }

    public static HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>(); //用hash来存图, int[0]表示终点 int[1]表示边的权值
    public static int[] distance;  // 每个节点距离源点的距离
    public static boolean[] is_select;  // 是否已经被选入集合
    public static ArrayList<Integer> group = new ArrayList<>(); // 每次只考虑新加入集合的节点带来的影响(list中的最后一个)

    public static int f(){
        Scanner sc = new Scanner(System.in);
        int n_factory = sc.nextInt(); // 节点的数量
        int src = sc.nextInt();  // 源点
        int item = sc.nextInt();  //边的数量

        distance = new int[n_factory+1];
        is_select = new boolean[n_factory+1];
        
        for(int i=1;i<=n_factory;++i){
            is_select[i] = false;
            distance[i] = -1; // -1 代表无穷大, 这是一个坑, 最好用一个大数, 不然后面每次都要考虑特殊情况
        }

        for (int i = 0; i < item; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int time = sc.nextInt(); // 边的权值

            if(!graph.containsKey(start)){
                ArrayList<int[]> list_ = new ArrayList<>();
                int[] ints = {end, time};
                list_.add(ints);
                graph.put(start,  list_);
            }else{
                int[] ints = {end, time};
                graph.get(start).add(ints);
            }
        }

        dfs(src);

        for (int i=1;i<=n_factory;++i) {
            if(!is_select[i]) return -1; //表示有的边到不了
        }
		
        // 题目中就是要求边的最大权值
        int _max = -1;
        for (int d : distance) {
            _max = Math.max(_max,d);
        }

        return _max;

    }

	// 关键代码
    public static void dfs(int src){
        group.add(src);
        distance[src] = 0;
        is_select[src] = true;

        while(true){
            // 更新distance向量
            int fresh = group.get(group.size()-1);
            ArrayList<int[]> ints = graph.get(fresh);

            if(ints!=null){ // 注意如果这个节点没有出边的话, hash表中存的就是null	
                for(int[] int_ : ints){
                    if(distance[int_[0]]==-1 || distance[fresh] + int_[1] < distance[int_[0]]){
                        distance[int_[0]] = distance[fresh