算法小笔记

背景(闲话)

好久没更了，这不到年底了。想想马上2024了，干脆把之前的东西整理整理吧

向上取整技巧 $x \div y$

一般来说，刚开始都会想到两种方法：

1	res = x % y == 0 ? x / y : x / y + 1;

或者

1	res = Math.ceil(x / y);

实际上，第一种还行，但是稍显啰嗦；第二种容易出bug，而且调用消耗高。

有更简单的：

1	res = (x + y - 1 ) / y

简单证一下：

假设 :
$x \div y = a \cdots b$,
那么:
$x = a \cdot y + b$,
则
$(x + y - 1 ) \div y$
$= (a \cdot y + y + b - 1 ) \div y $
$= a + (y + b - 1) \div y$
如果 $b = 0 $，

那么后半部分就是 $0$ 了;

如果 $b \geq 1 $，

也就是不能整除，$a$ 就会 $+ 1$;

二分板子

nnd, 今天每日一题有思路，知道拿二分，也肯定能过但是居然卡二分实现这儿了

/**
 * nums为查找范围(升序排列)， target即目标
 * 现在查找nums数组中大于等于target的第一个数的下标
 */
pubulic int dichotomy(int [] nums , int target){
    int n = nums.length;
    int left = 0 , right = n - 1;
    int resLabel = -1;
    while(left <= right){
        /* 循环条件注意 = ，即某一个位置需要判断是否符合*/
        int mid = left + (right - left) / 2;
        /* 注意防溢出，也可以写成：
        int mid = left + (right - left >> 1) 
           注意移位运算符的优先级*/
        if(nums[mid] >= target){
            resLabel = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
        /* 有时候也根据需要直接把 mid 赋给 left/right */
    }
    return resLabel;
}

我之前老想不清的是找到第一个满足条件的数，需要借助前一次查找的标记。但是实际上，在窗口移动的过程中，范围一直在缩小、寻找满足条件且最靠前的数，缩到最小(到达最优解)后下次就会不满足条件直接跳出了。

求解最短路

1. `floyd`(弗洛伊德算法)

floyd算法是把一个图里边的各个点之间的最短路都算出来，适合多源最短路问题

就是每拿到一个点，就借助这个点建立其他点之间的联系，更新其他点之间的最短路

朴素floyd实现：

    /**
     * 弗洛伊德算法朴素式，借助矩阵实现
     * 给定一个 n 节点的图，
     * 且参数包含边权矩阵 edges[][]，其内层大小为 3 , 分别表示 起点，终点，路径长度
     */
public int [][] floydSimplicity(int n, int[][] edges)
{
    // 建立并初始化距离矩阵
    int[][] dis = new int[n][n];
    for(int i = 0 ; i < n ; i ++){
        Arrays.fill(dis[i], Integer.MAX_VALUE / 2);
    }

    // 将距离加入
    for(int [] edge : edges){
        int from = edge[0], to = edge[1], len = edge[2];
        dis[from][to] = len;
        dis[to][from] = len;
    }

    // 三层遍历得到所有点之间的最短路
    for(int k = 0 ; k < n ; k ++){
        dis[k][k] = 0;
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < n ; j ++){
                dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    return dis;
}

2. `dijkstra`(迪杰斯特拉算法)

dijkstra算法是从一个点出发，不断更新此点到其他点的最短路，直到所有点都到达或者遍历完。适合单源最短路问题，但同样也可用于多源

    // 下面先针对多源最短路问题给出dijkstra朴素实现，条件同上
public int [][] dijkstraSimplicity(int n, int[][] edges)
{
    // 建立并初始化距离矩阵和路径矩阵
    int[][] dis = new int[n][n];
    int[][] map = new int[n][n];

    // 创建访问矩阵，标记某个位置是否作为最近点使用过
    boolean[][] vis = new boolean[n][n];

    for(int i = 0 ; i < n ; i ++){
        Arrays.fill(dis[i], Integer.MAX_VALUE / 2);
        Arrays.fill(map[i], Integer.MAX_VALUE / 2);
    }

    // 将边权加到路径矩阵中，方便后续直接使用
    for(int [] edge : edges){
        int from = edge[0], to = edge[1], len = edge[2];
        map[from][to] = len;
        map[from][to] = to;
    }

    for(int i = 0 ; i < n ; i ++){
        dis[i][i] = 0; // 每个点到自身距离为0
        for(int j = 0 ; j < n ; j ++){
            int shortPos = -1;

            // 寻找最近的点
            for(int k = 0 ; k < n ; k ++){
                if( !vis[i][k] && (shortPos == -1 || dis[i][k] < dis[i][shortPos])){
                    shortPos = k;
                }
            }
            vis[i][shortPos] = true;

            // 借助最近点去算到其他点的距离，不断更新
            for(int k = 0 ; k < n ; k ++){
                dis[i][k] = Math.min(dis[i][k], dis[i][shortPos] + map[shortPos][k]);    
            }
        }
    }
    return dis;
}

算法小记(1)