Leecode刷题C语言之新增道路查询后的最短距离①

执行结果:通过

执行用时和内存消耗如下：

题目：新增道路查询后的最短距离①

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

解题思路 ：

代码的目的是解决一个关于计算最短距离的问题，其中涉及到一个长度为 n 的数组（或一维空间），以及一系列查询。每个查询包含两个整数，表示数组（或空间）中的两个位置。每次查询后，将这两个位置之间的距离设置为1（可以视为这两个位置之间直接相连），然后计算从数组的第一个位置到最后一个位置的最短距离。最终，函数返回一个数组，其中包含了每次查询后的最短距离。

1. 内存分配：
   • 使用 malloc 为返回数组 returnarray 分配内存，大小为 queriesSize，因为返回的数组长度应与查询的数量相同。
2. 初始化距离矩阵：
   • 创建一个二维数组 distance[n][n] 来存储任意两点之间的初始距离。
   • 初始化时，对于每个点 i 到点 k 的距离（其中 k >= i），直接设置为 k-i，因为初始状态下，两点之间的距离就是它们在数组中的索引差。
3. 处理查询：
   • 遍历每个查询，对于每个查询 (queries[i][0], queries[i][1])：
     • 将这两个点之间的距离设置为1，表示它们直接相连。
     • 更新 distance 矩阵中，从 queries[i][0] 向上（包括它自己）到第一个位置，以及从 queries[i][1] 向右（包括它自己）到最后一个位置的所有点之间的最短距离。
     • 每次查询后，将 distance[0][n-1]（即从数组第一个位置到最后一个位置的最短距离）存储到 returnarray[i] 中。
4. 返回结果：
   • 设置 *returnSize 为 queriesSize。
   • 返回 returnarray，包含了每次查询后的最短距离。

注意：代码中的动态规划更新部分存在逻辑错误，特别是在计算 temp 和更新 distance[k][m] 时。正确的实现应该更加严谨地利用已知的 distance 矩阵，并通过动态规划的思想逐步更新所有相关的最短路径。此外，代码中的内存分配没有对应的错误处理，实际应用中应检查 malloc 是否成功。

int* shortestDistanceAfterQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int *returnarray=malloc(sizeof(int)*queriesSize);
    int distance[n][n],temp;
    for(int i=0;i<n;i++){
        for(int k=i;k<n;k++){
            distance[i][k]=k-i;
        } 
        
    }
    
    int j=0;
    for(int i=0;i<queriesSize;i++){
        distance[queries[i][0]][queries[i][1]]=1;
        for(int k=queries[i][0];k>=0;k--){
            for(int m=queries[i][1];m<n;m++){
                temp=distance[k][queries[i][0]]+1+distance[queries[i][1]][m];
                if(temp<distance[k][m])
                distance[k][m]=temp;
            }
            

        }
        returnarray[i]=distance[0][n-1];
    }
    *returnSize=queriesSize;
    return returnarray;
}