3月10日 2070.每一个查询的最大美丽值

题目描述：

分析：

在做这道题的时候，直接采用暴力解法，遍历请求数组时，再去便利所有的物品，判断出每次请求下的不同物品美丽值取最值更新。时间复杂度为O(nm)，n为请求数组的个数，m为物品数组个数。

代码如下：

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        
        List<Integer> resultList = new ArrayList<>();
        for(Integer querie : queries){
            int result = 0;
            for(int i = 0; i < items.length; i++){
                if(querie >= items[i][0]){
                    result = Math.max(result, items[i][1]);
                }
            }
            resultList.add(result);
        }

        return resultList.stream().mapToInt(Integer::intValue).toArray();

    }
}

写到这里，那么恭喜你获得超时大礼包一份。

再次分析：

我们在暴力解法中，问题出在单次查询是对整个物品数组遍历，我们需要对单次查询进行优化。

可以将单次查询的过程分为两步：

步骤一：找出小于等于当前查询价格的所有物品

步骤二：找出这些物品中美丽值的最大值

在步骤一中，我们把物品 items 数组按照物品的价格升序排列，这样一来只要通过查找就可以找到所有小于等于当前查询价格的物品的下标。时间复杂度为O(nlogn)

我们找到了这些符合条件的物品，那么怎么能够通过一次二分查找就能确定该物品就是美丽值最大的呢？

接下来就是关键的步骤二

在步骤一对物品进行排序后，步骤二是将每个物品的美丽值修改为小于等于它所在下标中的所有物品的美丽值的最大值。时间复杂度为O(n)

而且取最值实际上只需要当前物品与其前一个物品的美丽值取最值就可以了。因为取最值的过程是从左到右依次进行，只要比前一个物品的美丽值大，那么就会比前面所有物品的美丽值大。

这样一来，当我们只通过一次二分查找找到步骤一对应的下标时，如果下标合法，该下标对应的(有可能会被修改过)美丽值就一定是价格小于等于查询价格中物品的最大美丽值；如果下标不合法，那么就返回0。二分查找的时间复杂度为O(logn)

时间复杂度为O(nlogn) + O(n) + O(logn) = O(nlogn)

代码如下：

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        
        //将物品价格按照升序排列，时间复杂度为O(nlogn)
        Arrays.sort(items, (a, b) -> Integer.compare(a[0], b[0]));
        
        //将第i个下标的物品的美丽值改成小于等于i的美丽值中的最大值,时间复杂度为O(n)
        for(int i = 1; i < items.length; i++){
            items[i][1] = Math.max(items[i][1], items[i-1][1]);
        }

        //二分查找 找对应请求的美丽值 O(logn)
        int[] resulArray = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            //二分查找
            int left = 0; 
            int right = items.length - 1;
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(queries[i] < items[mid][0]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            if(left == 0){
                resulArray[i] = 0;
            }else{
                resulArray[i] = items[left - 1][1];
            }
        }     
        return resulArray;   
    }
}

3月11日 卡玛网25.最爱的城市

从题目描述来看这是多源点最短路径，直接 Floyd 算法秒了。

这里再回顾一下多源最短路问题求解思路。

多源最短路径是指在所给图中，求出多个起点到多个终点的多条最短路径。换句话说，我们可以求出任何起点和终点之间最短路径距离。

Floyd 算法对边的权值正负没有要求，它的思想是基于动态规划的。

动态规划最重要的就是我们要推导出当前状态是怎样由其它状态推导出来的。比方说，我们要求的节点 1 到节点 7 之间的最短距离是 m ，在二维数组中体现为 grid[1][7] = m。

现在思考，节点 1 到节点 7 之间的最短距离其中一种可能的来源为节点 1 到节点 4 的最短距离 + 节点 4 到节点 7 的最短距离，又或者是节点 1 到节点 5 的最短距离 + 节点 5 到节点 7 的最短距离组成。

以此类推，每段节点间距离都可以在拆解。在拿到这些路径可能后，怎么选出最终结果呢？要选择最小的路径才是我们需要的答案。

这样一来，动态规划的雏形就有了。

动态规划五部曲：

• 确定 dp 数组以及下标的含义
• 确定递推公式
• dp 数组如何初始化
• 确定遍历顺序
• 打印 dp 数组来排错

（1）确定 dp 数组以及下标的含义

对于有权重的图来说，可以用一个二维数组来保存，一维二维分别代表起始节点和终止节点，值代表节点间最短距离。grid[i][j] = m。在动态规划的思想中将 dp 数组在二维数组 grid 的基础上增加一维：

grid[i][j][k] = m，表示节点 i 到节点 j ，中间经历过[1 … k]集合中的任何一个节点后的最短距离为 m 。

（2）确定递推公式

从 dp 数组定义以及前面举的例子，递推状态可以由两种情况得到：

情况1：节点 i 到节点 j 的最短路径经过节点 k

情况2：节点 i 到节点 j 的最短路径不经过节点 k

接下来对这两种情况掰开了揉碎了分析：

首先是情况1，节点 i 到节点 j 的最短路径经过节点 k 可以拆解为节点 i 到节点 k ，节点 k 到节点 j 两部分。在一部分中，节点i 到节点 k 是不经过节点 k 的，中间所能经历的节点集合就变为了 [1 … k-1]；在第二部分同理，节点 k 到节点 j 也是不经过节点 k 的。

由此得出，grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1]；

那么情况2就很简单了，节点 i 到节点 j 的最短路径不经过节点 k，即中间所能经历的节点集合就变为[1 .. k-1]。

由此得出，grid[i][j][k] = grid[i][j][k-1]；

以上两种情况我们要求出最小值：

grid[i][j][k] = Math.min(grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1], grid[i][j][k] = grid[i][j][k-1])；

（3）dp 数组如何初始化

初始化需要分成两部分：

• 创建 dp 数组后对于整个 dp 的第一次初始化问题
• 影响递推公式的 k 所在维的第二次初始化问题

第一次初始化是将所有i ,j ,k 初始化，当 i = j 时要初始化为 0 这是必须的，因为节点自己到自己的最短距离一定是0；其次剩下的所有值都初始化为最大值（因为我们要求最小值，所以要比较），最大值最好设置题目中所给的权重的最大值，之前做题设置为 Integer.MAX_VALUE 会爆莫名其妙的错误。

//初始化
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                for(int k = 0; k <= n; k++){
                    if(i == j){
                        grid[i][j][k] = 0;
                    }else{
                        grid[i][j][k] = 1000;
                    }
                }
            }
        }

第二次初始化是考虑递推公式状态，grid[i][j][k] = m；从递推公式可以看出，是 k-1 的状态来推出 k 的状态，因此可以将 k = 0 的所有值都赋为 0 ，这样可以根据 grid[i][j][0] 来推出 grid[i][j][1] 的状态。而且我们在设置 grid 数组大小的时候，每一维都设置为 n＋1 ，节点 0 是无意义的，从节点 1 开始 到节点 n 结束。

//递推公式所需要的初始化
        for(int i = 0; i < m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int l = scanner.nextInt();
            grid[a][b][0] = l;
            grid[b][a][0] = l;
        }

（4）遍历顺序

还是来看一看递推公式：

grid[i][j][k] = Math.min(grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1], grid[i][j][k] = grid[i][j][k-1])；

三层 for 循环，分别遍历 i, j, k。如何确定顺序呢？

k 依赖 k-1 的状态， i 和 j 并不依赖 i – 1 或者 j – 1。

所以先遍历 k ，内层在遍历 i 和 j ，至于 i 和 j 谁先谁后就无所谓了。

至此，理论分析结束，上代码：

import java.util.*;


public class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int m = scanner.nextInt();

            //创建dp数组
            int[][][] grid = new int[n + 1][n + 1][n + 1];
            
            //初始化
            for(int i = 0; i <= n; i++){
                for(int j = 0; j <= n; j++){
                    for(int k = 0; k <= n; k++){
                        if(i == j){
                            grid[i][j][k] = 0;
                        }else{
                            grid[i][j][k] = 1000;
                        }
                    }
                }
            }

            //递推公式所需要的初始化
            for(int i = 0; i < m; i++){
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                int l = scanner.nextInt();
                grid[a][b][0] = l;
                grid[b][a][0] = l;
            }

            //开始遍历
            for(int k = 1; k <= n; k++){
                for(int i = 1; i <= n; i++){
                    for(int j = 1; j<= n; j++){
                        grid[i][j][k] = Math.min(grid[i][k][k-1] + grid[k][j][k-1], grid[i][j][k-1]);
                    }
                }
            }

            int x = scanner.nextInt();
            int y = scanner.nextInt();

            if(grid[x][y][n] == 1000){
                System.out.println("No path");
            }else{
                System.out.println(grid[x][y][n]);
            }
        }
    }
}

需要注意的一个点就是这道题的描述：“输入包含多组测试数据”，而给出的示例只是一组，很容易忽略代码是需要一直等待用户输入一整组数据的，因此在进行 Floyd 算法求解逻辑之前，要使用 while 循环一直等待用户的下一组数据。

while(scanner.hasNext()){

//开始你的逻辑~~~~~

}

Scanner输入类中的hasNext() 方法可以阻塞等待用户输入，用户输入内容后按回车后，hasNext() 方法会返回 true 。