• 左神高级提升班1 很重要的题目

    【案例1】

    【题目描述 难度非常高】

     【思路解析】

    因为要求额外空间复杂度为O(1)，所以我们只能使用有限几个变量，来得到整个数组所在的城市距离首都的距离。因为数组paths[i]表示，i城市指向paths[i]城市，我们可以利用这个指向关系（next为下次要去的城市，last为当前城市。并且在往前遍历时，要记录回去的信息，即paths[next的值]=last的值，这样我们就可以再通过last和next往回走），一直往前遍历，直到next==paths[next]，或者paths[next] < 0,我们便开始往回走，并且回走时，如果城市i距离首都为x，则给paths[i]赋值为-x。

    然后得到了这个距离数组后，再通过判断距离数组的正负来统计距离（通过指向关系来进行循环计数）的个数。

    【代码实现】

    1. import java.util.Arrays;
    2.  
    3. /**
    4.  * @ProjectName: study3
    5.  * @FileName: Ex1
    6.  * @author:HWJ
    7.  * @Data: 2023/9/14 22:30
    8.  */
    9. public class Ex1 {
    10.     public static void main(String[] args) {
    11.         int[] paths = {9, 1, 4, 9, 0, 4, 8, 9, 0, 1};
    12.         pathToDistance(paths);
    13.         distanceToCount(paths);
    14.         System.out.println(Arrays.toString(paths));
    15.     }
    16.  
    17.     public static void pathToDistance(int[] paths) {
    18.         int n = paths.length;
    19.         int capital = -1;
    20.         for (int start = 0; start < n; start++) {
    21.             if (paths[start] == start) {
    22.                 capital = start;
    23.             } else if (paths[start] > -1) {
    24.                 int last = start;
    25.                 int next = paths[last];
    26.                 while (paths[next] != next && paths[next] > -1) {
    27.                         int num = paths[next];
    28.                         paths[next] = last;
    29.                         last = next;
    30.                         next = num;
    31.                 }
    32.                 int i = paths[next] == next ? 0 : paths[next];
    33.                 while (last != start) {
    34.                     int num = paths[last];
    35.                     paths[last] = --i;
    36.                     last = num;
    37.                 }
    38.                 paths[last] = --i;
    39.             }
    40.         }
    41.         paths[capital] = 0;
    42.     }
    43.  
    44.     public static void distanceToCount(int[] paths){
    45.         for (int i = 0; i < paths.length; i++) {
    46.             int cur = paths[i];
    47.             paths[i] = Math.max(paths[i], 0);
    48.             while (cur <= 0){
    49.                 int next = paths[-cur];
    50.                 if (next < 0){
    51.                     paths[-cur] = 1;
    52.                     cur = next;
    53.                 }else {
    54.                     paths[-cur]++;
    55.                     break;
    56.                 }
    57.             }
    58.  
    59.         }
    60.     }
    61. }

    【案例2】

    【题目描述 分糖果问题】

    一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

    1. 每个孩子不管得分多少，起码分到一个糖果。

    2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。

    3. 【进价】要求相邻的两个孩子如果得分相同，得到的糖果应该相同。

    4. 要求时间复杂度为O(N)

    【思路解析】

    我们可以通过得分数组得到一个得分的折线图（即升降情况），然后通过从左向右遍历这个升降情况得到每个人应该分到的糖果数。然后通过从右向左遍历这个升降情况得到每个人应该分到的糖果数。然后对应求最大即为每个孩子的糖果数。遍历时要求升序糖果数++，如果降序或者保持不变，使糖果数变回1.

    【进价思路分析】

    我们可以通过得分数组得到一个得分的折线图（即升降情况），然后通过从左向右遍历这个升降情况得到每个人应该分到的糖果数。然后通过从右向左遍历这个升降情况得到每个人应该分到的糖果数。然后对应求最大即为每个孩子的糖果数。遍历时要求升序糖果数++，如果降序使糖果数变回1，如果保持不变，则使糖果数保持不变。

    【代码实现】

    1. /**
    2.  * @ProjectName: study3
    3.  * @FileName: Ex2
    4.  * @author:HWJ
    5.  * @Data: 2023/9/15 0:07
    6.  */
    7. public class Ex2 {
    8.     public static void main(String[] args) {
    9.         int[] scores = {1, 2, 2};
    10.         System.out.println(candy1(scores));
    11.         System.out.println(candy2(scores));
    12.     }
    13.  
    14.     public static int candy1(int[] scores){
    15.         int[] left = new int[scores.length];
    16.         int[] right = new int[scores.length];
    17.         left[0] = 1;
    18.         for (int i = 1; i < scores.length; i++) {
    19.             if(scores[i] > scores[i - 1]){
    20.                 left[i] = left[i - 1] + 1;
    21.             }else {
    22.                 left[i] = 1;
    23.             }
    24.         }
    25.         right[scores.length - 1] = 1;
    26.         for (int i = scores.length - 2; i >= 1; i--) {
    27.             if(scores[i] > scores[i + 1]){
    28.                 right[i] = right[i + 1] + 1;
    29.             }else {
    30.                 right[i] = 1;
    31.             }
    32.         }
    33.         int res = 0;
    34.         for (int i = 0; i < scores.length; i++) {
    35.             res += Math.max(left[i], right[i]);
    36.         }
    37.         return res;
    38.     }
    39.  
    40.     public static int candy2(int[] scores){
    41.         int[] left = new int[scores.length];
    42.         int[] right = new int[scores.length];
    43.         left[0] = 1;
    44.         for (int i = 1; i < scores.length; i++) {
    45.             if(scores[i] > scores[i - 1]){
    46.                 left[i] = left[i - 1] + 1;
    47.             }else if (scores[i] < scores[i - 1]){
    48.                 left[i] = 1;
    49.             }else {
    50.                 left[i] = left[i - 1];
    51.             }
    52.         }
    53.         right[scores.length - 1] = 1;
    54.         for (int i = scores.length - 2; i >= 1; i--) {
    55.             if(scores[i] > scores[i + 1]){
    56.                 right[i] = right[i + 1] + 1;
    57.             }else if (scores[i] < scores[i + 1]){
    58.                 right[i] = 1;
    59.             }else {
    60.                 right[i] = right[i + 1];
    61.             }
    62.         }
    63.         int res = 0;
    64.         for (int i = 0; i < scores.length; i++) {
    65.             res += Math.max(left[i], right[i]);
    66.         }
    67.         return res;
    68.     }
    69. }

    【超级进阶   非常难】

    要求时间复杂度为O(N), 额外空间复杂度为O(1)。   实现特别困难。

    【案例3】

    【题目描述】

    【思路解析】二叉树递归套路类题目

    第一种思路，列出所有可能性，然后在递归时得到所有可能性，然后不断汇总求最优解。

    能获得最优解的可能性如下：

    （1）x结点以下都被照亮（包含x结点），且x上不放灯。

    （2）x结点以下都被照亮（包含x结点），且x上放灯。

    （3）x结点以下都被照亮（不包含x结点），但x上放灯。（因为这种情况可能引出下一个最优解，在x的父上放灯，影响的结点更多）。

    第二种思路，我们在传递的时候已知最优解需要的是什么信息，利用贪心加速常数时间。

    比如当左孩子和右孩子，未被覆盖时，x上必须放灯，如果左孩子和右孩子，被覆盖且放灯，则x上一定不放灯。如果左孩子和右子，被覆盖但没放灯，则x未被覆盖。

    【代码实现】 

    1. /**
    2.  * @ProjectName: study3
    3.  * @FileName: Ex3
    4.  * @author:HWJ
    5.  * @Data: 2023/9/15 0:16
    6.  */
    7. public class Ex3 {
    8.     public static void main(String[] args) {
    9.  
    10.     }
    11.  
    12.     public static class Node{
    13.         Node left;
    14.         Node right;
    15.     }
    16.  
    17.     public static class ReturnData{
    18.         public int unCovered;
    19.         public int coveredNoCamera;
    20.         public int coveredHasCamera;
    21.  
    22.         public ReturnData(int unCovered, int coveredNoCamera, int coveredHasCamera) {
    23.             this.unCovered = unCovered;
    24.             this.coveredNoCamera = coveredNoCamera;
    25.             this.coveredHasCamera = coveredHasCamera;
    26.         }
    27.     }
    28.  
    29.     public static int getMin(Node head){
    30.         ReturnData data = process(head);
    31.         return Math.min(data.unCovered, Math.min(data.coveredHasCamera, data.coveredNoCamera));
    32.     }
    33.  
    34.     public static ReturnData process(Node node){
    35.         if (node == null){
    36.             return new ReturnData(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
    37.         }
    38.         ReturnData left = process(node.left);
    39.         ReturnData right = process(node.right);
    40.         int unCovered = left.coveredNoCamera + right.coveredNoCamera;
    41.         int coveredNoCamera = Math.min(left.coveredHasCamera + right.coveredHasCamera,
    42.                 Math.min(left.coveredHasCamera + right.coveredNoCamera,
    43.                         left.coveredNoCamera + right.coveredHasCamera));
    44.         int coveredHasCamera = Math.min(left.unCovered,
    45.                 Math.min(left.coveredHasCamera, left.coveredNoCamera)) +
    46.                 Math.min(right.unCovered,
    47.                         Math.min(right.coveredHasCamera, right.coveredNoCamera)) + 1;
    48.         return new ReturnData(unCovered, coveredNoCamera, coveredHasCamera);
    49.     }
    50.  
    51.     public enum Status{
    52.         UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA;
    53.     }
    54.  
    55.     public static class ReturnData2{
    56.         public Status status;
    57.         public int cameras;
    58.  
    59.         public ReturnData2(Status status, int cameras) {
    60.             this.status = status;
    61.             this.cameras = cameras;
    62.         }
    63.     }
    64.  
    65.     public static int getMin2(Node head){
    66.         ReturnData2 data = process2(head);
    67.         return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
    68.     }
    69.  
    70.     public static ReturnData2 process2(Node node){
    71.         if (node == null){
    72.             return new ReturnData2(Status.COVERED_NO_CAMERA, 0);
    73.         }
    74.         ReturnData2 left = process2(node.left);
    75.         ReturnData2 right = process2(node.right);
    76.         int cameras = left.cameras + right.cameras;
    77.         if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED){
    78.             return new ReturnData2(Status.COVERED_HAS_CAMERA, cameras + 1);
    79.         }
    80.         if (left.status == Status.COVERED_HAS_CAMERA && right.status == Status.COVERED_HAS_CAMERA){
    81.             return new ReturnData2(Status.COVERED_NO_CAMERA, cameras);
    82.         }
    83.         return new ReturnData2(Status.UNCOVERED, cameras);
    84.     }
    85. }

  • 相关阅读:
    os模块介绍
    开源：分享4个非常经典的CMS开源项目
    数据结构刷题：第十一天
    认真聊聊中断(软中断)
    赫夫曼树的创建(思路分析)
    C++之分水岭——类和对象【上】
    jmeter做性能测试
    线性回归模型
    YOLO-World技术小结
    [ArcGIS].txt或.xlxs(Excel)格式如何转为.shp格式？
  • 原文地址：https://blog.csdn.net/weixin_73936404/article/details/132862975