[数据结构与算法]8.2-8.6学习总结

8.2-8.6学习总结

1. 数据结构与算法总结：

8.1 1337. 矩阵中战斗力最弱的 K 行

• 题目解释：

  给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

? 请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

? 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

? 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

• 题目难度是简单级别，首先，这是个排序问题，题目的排序标准是 战斗力（军人数量），然而每一行的军人数量都是由多少个1决定的。那我们的第一种想法就是统计每一排1的个数，然后再排序返回题目要求的结果就行了。
• 接着，我们又注意到了 军人总是排在一行中的靠前位置，也就是说1总是出现在0之前*这句话，然后我们意识到这是一个排好顺序的队伍，那么，我们解决第一步骤的 统计每一排的1的个数 就可以用二分法来解决，这样我们在排序阶段就只花了log n的时间复杂度。

int a=0,b=n;
while(a<b){
    int mid=a+(b-a)/2;
    if(mat[i][mid]==1)
        a=mid+1;
    else
        b=mid;
}

通过上面的二分法，我们得到了a=b的结果，此时他们两个代表的是自左向右第一个0的下标，即1的个数

• 然后就是将得到的每行战斗力，我们存起来就行了

int m=mat.length,n=mat[0].length;
int[][] res=new int[m][2];
for(int i=0;i<m;i++){
    res[i][0]=i;
    int a=0,b=n;
    while(a<b){
        int mid=a+(b-a)/2;
        if(mat[i][mid]==1)
            a=mid+1;
        else
            b=mid;
    }
    res[i][1]=a;
}

• 接着就是排序，选择前k个输出就行了

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        int m=mat.length,n=mat[0].length;
        int[][] res=new int[m][2];
        for(int i=0;i<m;i++){
            res[i][0]=i;
            int a=0,b=n;
            while(a<b){
                int mid=a+(b-a)/2;
                if(mat[i][mid]==1)
                    a=mid+1;
                else
                    b=mid;
            }
            res[i][1]=a;
        }
        Arrays.sort(res,(int[] a,int[] b)->{
            if(a[1]!=b[1])
                return a[1]-b[1];
            else
                return a[0]-b[0];
        });
        int[] ans=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=res[i][0];
        }
        return ans;
    }
}

提交结果：

8.2 743. 网络延迟时间

• 题目解释：

  有 n 个网络节点，标记为 1 到 n。

  给你一个列表 times，表示信号经过 有向 边的传递时间。

  times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

  现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

• 首先，这是一个图论的题目，具体方法有

  1. 深度优先遍历

  2. 广度优先遍历

  3. Dijkstr

  4. 弗洛伊德算法

  5. 等等

简便起见，我选择使用弗洛伊德算法，当然也可以选择使用Dijkstr算法。

• 这是一个单源最短路径算法，相当于简化版的弗洛伊德。
  1. 初始化一个一元数组，表示从源点到当前节点的最短路径。
  2. 数组里面除了源节点的值为0外其余的都是不可达，我们设为-1.
  3. 设置标志变量，如果遍历当前所有路径发现：将要到达的节点值为-1，或者存在更短的路径，我们选择更新标志变量为真。
  4. 否则我们不管，当然，我们在每次循环的时候就是在判断标志变量，所以我们在每次循环初始就把标志变量置为假。
  5. 从理论上来讲，弗洛伊德算法的循环次数是不超过路径总个数（边的个数）。

int[] arr = new int[n+1];
Arrays.fill(arr,-1);
arr[k]=0;
boolean flag = true;
while(flag){
    flag = false;
    //更新法，如果能按现有组合走出通路或者更短路，继续计算；否则说明已是最优，跳出
    for(int[] time:times){
        if(arr[time[0]]>=0){
            if(arr[time[1]]==-1 || arr[time[0]]+time[2] < arr[time[1]]){
                flag = true;
                arr[time[1]]=arr[time[0]]+time[2];
            }
        }
    }
}

• 接下来要做的就是，遍历路径数组，如果发现有-1就说明存在未达点，返回-1
• 否则就比较当前最短路径，直至最终返回最短路径结果。

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] arr = new int[n+1];
        Arrays.fill(arr,-1);
        arr[k]=0;
        boolean flag = true;
        while(flag){
            flag = false;
            //更新法，如果能按现有组合走出通路或者更短路，继续计算；否则说明已是最优，跳出
            for(int[] time:times){
                if(arr[time[0]]>=0){
                    if(arr[time[1]]==-1 || arr[time[0]]+time[2] < arr[time[1]]){
                        flag = true;
                        arr[time[1]]=arr[time[0]]+time[2];
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            //存在非通路，返回-1
            if(arr[i]==-1){
                return -1;
            }
            //所有都是通路，求出最长的
            ans = Math.max(arr[i],ans);
        }
        return ans;
    }
}

提交结果：

8.3 581. 最短无序连续子数组

• 题目描述：

  给你一个整数数组 nums ，你需要找出一个 连续子数组 ，

  如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

  请你找出符合题意的 最短 子数组，并输出它的长度。

• 示例：

• 首先，我们要理解题目意思，这是说我们动最少的步骤，使得整个数组变为递增数组。
• 其中，我们只能动子数组，并且只能动一个。
• 然后我们的操作也是只将选择的子数组给排个序，仅此而已。

解题思路：

1. 从整体上看，我们最重的目标是得到一个递增的数组，如果直接排序的话，可以用n log n 的时间复杂度完成。
2. 然后从左边开始与原数组比较找到第一个不同的数字的下标，接着从右边开始比较得到右边第一个与原数组不同的下标。
3. 然后这两个下标之间的子数组就是我们需要找的，消耗时间复杂度为n。
4. 但是，如果就这样的话，我们就理解不了这道题目的精髓。

5. 然后我们接着看，刚才我们是怎么找到最左边的元素哪？

6. 我们发现想要成为完全递增数组，并且只改变一个子数组，那么这个子数组的左右边界一定是要改变的；

7. 换句话说，我们拿到的最小长度子数组的左侧一定是小于子数组的任何一个值，

8. 同理，最小长度子数组的右侧一定是大于子数组的任意值；

9. 并且，我们要将子数组重新排序，那么一定，对于所有出现断崖（乱序）的情况，要全部都包含在最短长度子数组内部。

10. 这样，我们找到了最短长度子数组的两个要素：

    • 包含所有乱序的情况；
    • 子数组内所有元素必须全部大于（等于）左侧其余元素，小于（等于）右侧其余元素。

11. 上述的两个条件，第一条说的是最短子数组的最小值，第二条说的是其最短子数组的上限。

12. 那我们接下来的步骤就是先找到极限最小值，以左侧为例；

13. 自左向右遍历，如果出现乱序，那么我们就找到了最短子数组的最大左极限；

14. 接着向右遍历，如果出现比左极限还要小的数字就把左极限继续向左退。

15. 幸运的是在最短长度子数组的右侧是不会出现小于左极限的数字；

16. 即，当我们遍历完整个数组时，那么我们就一定找到子数组的最小值了。

17. 右侧右极限也同理。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums.length<2)
            return 0;
        int head=0,tail=nums.length-1;
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]>nums[i])
                break;
            else
                head++;
        }
        for(int i=head;i<nums.length;i++){
            while(head>=0 && nums[i]<nums[head]){
                head--;
            }
            if(head<0)
                break;
        }
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i+1]<nums[i])
                break;
            else
                tail--;
        }
        for(int i=tail;i>=0;i--){
            while(tail<nums.length && nums[i]>nums[tail]){
                tail++;
            }
            if(tail>=nums.length)
                break;
        }
        return head>tail ? 0 : tail-head-1;
    }
}

• 提交结果：

8.4 611. 有效三角形的个数

• 题目描述：

  给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

• 示例：

  

• 注意：

  

• 题目解释：

  1. 首先，我们可以暴力解决，三次循环，找到合适的就 ans++ ；然后返回结果。
  2. 但是，上述暴力破解的话，时间复杂度为 n^3。
  3. 这是不符合我们的期望的。
  4. 那么接下来我们就尝试现把数组排序，花费时间复杂度为 n log n;
  5. 然后外面两层循环，自左至右表示两条较短边，然后我们只需要找到合适的第三条边就行了；
  6. 易知，三角形中较长边满足小于其余两条边之和。
  7. 这样，对于第三条边就有边界了：最右边不得大于两边和；
  8. 而对于寻址第三条边，我们可以采用二分法来找到合适的边。

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int left = j + 1, right = n - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;
    }
}

• 提交结果：

8.5 802. 找到最终的安全状态

• 题目描述：

  在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

  对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。返回一个由图中所有安全的起始节点组成的数组作为答案。

  答案数组中的元素应当按 升序 排列。 该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

• 示例：

  

• 题目分析：

  1. 这道题目的关键核心在于***无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点***这句话的理解，他的意思是说我们所选择的路径每一条都要走一遍，如果发现有闭环的，走不出去的就是不安全的。
  2. 那我们可以反过来想，那些是安全的？首先，对于那些没有出度的节点来说，他们一定是安全的；
  3. 其次，如果把这些安全的节点都去掉，包括那些连接到这些节点上的有向边；
  4. 然后剩下的没有出度的节点就也是安全的；
  5. 如此反复，我们不就得到了全部的安全节点吗？
  6. 总结一下：
  7. 我们可以采用反向拓扑排序的方法找到***安全节点***

• 代码如下：

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> rg = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            rg.add(new ArrayList<Integer>());
        }
        int[] inDeg = new int[n];
        for (int x = 0; x < n; ++x) {
            for (int y : graph[x]) {
                rg.get(y).add(x);
            }
            inDeg[x] = graph[x].length;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int y = queue.poll();
            for (int x : rg.get(y)) {
                if (--inDeg[x] == 0) {
                    queue.offer(x);
                }
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }
}

• 提交结果：

8.6 847. 访问所有节点的最短路径

• 题目描述：

  *存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。给你一个数组 graph 表示这个图。

  其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

  返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

• 示例：

  

• 题目解释：

  1. 这道题目是要求我们全部走完所有的节点（可以重复）；
  2. 这个问题是要寻找最短路径，但是所有的边权重都是相同的；
  3. 所以我们就可以采用广度优先遍历，如果某一条路径可以走完所有的节点；
  4. 那么，就说明我们找到了最短路径；
  5. 但是难点就在于如何记录当前节点走过的路径呢；
  6. 我们认真考虑发现，这里的路径仅仅指的是状态，
  7. 就是说，结局只关心我们走了那些节点，而不用关心它们之间的先后顺序；
  8. 为了简便起见，我们可以采用二进制数的0和1来表示节点是否走过；
  9. 对于广度优先遍历来讲，我们就采用先进先出的队列的数据结构来表示路径状态；

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n=graph.length;
        boolean[][] seen = new boolean[n][1<<n];
        Queue<int[]> queue=new LinkedList<int[]>();
        for(int i=0;i<n;i++){
            seen[i][1<<i]=true;
            queue.offer(new int[]{i,1<<i,0});
        }
        int ans=0;
        while(!queue.isEmpty()){
            int[] idea=queue.poll();
            if(idea[1]==(1<<n)-1){
                ans=idea[2];
                break;
            }
            for(int v:graph[idea[0]]){
                if(!seen[v][idea[1] | 1<<v]){
                    queue.offer(new int[]{v,idea[1] | 1<<v,idea[2]+1});
                    seen[v][idea[1] | 1<<v]=true;
                }
            }
        }
        return ans;
    }
}

• 提交结果：