• 高级进阶班1——补充（利用平凡解优化流程、通过记录结构找到可能性划分的边界情况、动态规划填表的斜率优化技巧、上中位数结构）

    目录

    【案例1】

    【题目描述】

    【思路解析】

    【代码实现】

    【案例2】

    【题目描述】 

    【题目描述】

    【代码实现】

     【案例3】

    【题目描述】

    【思路解析】

    【代码实现】

    【案例4】

    【题目描述】

    【思路解析1】

    【思路解析2】

    【思路解析3】

    【代码实现 仅实现最优解法的代码   对数器使用的是方法1】

    【案例1】

    【题目描述】

    【思路解析】

    先通过遍历数组得到整个数组的最小值和最大值，将【最小值，最大值】这个闭区间划分为n+1个小区间，然后整个数组的n个数字一定会分布在这n+1个小区间中，可能某一个区间会含有多个数，但是这些数中的相邻差值一定小于一个区间的长度，然后因为是n+1个小区间，就一定会有个别区间中没有数字，这些空区间左右的两边相邻数字差一定会大于一个区间的长度。（即这n+1个小区间，因为有空区间，所以给出了一个平凡解（区间长度），所以我们不需要再考虑一定小于平凡解的解，所以我们不必求解相同区间的相邻数字的解）。我们只用记录每个区间的最小值和最大值，然后在不同区间中求解。

    【代码实现】

    1. /**
    2.  * @ProjectName: study3
    3.  * @FileName: Ex1
    4.  * @author:HWJ
    5.  * @Data: 2023/9/16 15:57
    6.  * 利用平凡解优化的技巧
    7.  */
    8. public class Ex1 {
    9.     public static void main(String[] args) {
    10.  
    11.     }
    12.  
    13.     public static int getMaxDeviation(int[] arr){
    14.         if (arr.length < 2) {
    15.             return -1; // 只有一个数字的数组，无法得到两个相邻数的差
    16.         }
    17.         int max = Integer.MIN_VALUE;
    18.         int min = Integer.MAX_VALUE;
    19.         int len = arr.length;
    20.         for (int i = 0; i < len; i++) {
    21.             max = Math.max(max, arr[i]);
    22.             min = Math.min(min, arr[i]);
    23.         }
    24.         if (max == min){ // 满足此条件表示整个数组为常数数组。
    25.             return 0;
    26.         }
    27.         boolean[] hasNum = new boolean[len + 1];
    28.         int[] maxs = new int[len + 1];
    29.         int[] mins = new int[len + 1];
    30.         int index = 0;
    31.         for (int i = 0; i < len; i++) {
    32.             index = getIndex(len + 1, arr[i], min, max);
    33.             maxs[index] = hasNum[index] ? Math.max(maxs[index], arr[i]) : arr[i];
    34.             mins[index] = hasNum[index] ? Math.min(mins[index], arr[i]) : arr[i];
    35.             hasNum[index] = true;
    36.         }
    37.         int lastMax = maxs[0];
    38.         int res = Integer.MIN_VALUE;
    39.         for (int i = 1; i < len + 1; i++) {
    40.             if(hasNum[i]){
    41.                 res = Math.max(mins[i] - lastMax, res);
    42.                 lastMax = maxs[i];
    43.             }
    44.         }
    45.         return res;
    46.     }
    47.  
    48.     public static int getIndex(int len, int num, int min, int max){
    49.         return (int) (num - min) * len / (max - min);
    50.     }
    51. }

    【案例2】

    【题目描述】 

     给出n个数字a1，……an，问如何将这个数组划分为多个部分，使得这个划分中异或和等于0的部分尽可能多。问最多是多少。

    【题目描述】

    对于任何一个i位置上的数字，只有两种可能性，（1）它在最优化分情况下能使从k位置到i位置的异或和等于0 ，（2）它在最优划分情况下不能使某一个部分的异或和等于0。所以我们需要解决如果i位置能使最优划分情况下从k位置到i位置的异或和等于0，我们怎么找到这个最近的k位置。我们可以在遍历时记录从0-i位置的异或和，异或和为m，则上一次达到m的位置是k-1。利用这个记录结构我们可以找到那些部分能够使异或和为0，然后再满足不重复的条件下，得到最优划分情况。

    【代码实现】

    1. import java.util.HashMap;
    2.  
    3. /**
    4.  * @ProjectName: study3
    5.  * @FileName: Ex2
    6.  * @author:HWJ
    7.  * @Data: 2023/9/16 16:31
    8.  */
    9. public class Ex2 {
    10.     public static void main(String[] args) {
    11.         int[] arr= {3,2,1,4,0,4,0,3,2,1};
    12.         System.out.println(getBestDivision(arr));
    13.     }
    14.  
    15.     public static int getBestDivision(int[] arr){
    16.         int[] division = new int[arr.length];
    17.         HashMap<Integer, Integer> map = new HashMap<>();
    18.         map.put(0, -1); // 初始化记录表
    19.         int xor = 0;
    20.         for (int i = 0; i < arr.length; i++) {
    21.             xor ^= arr[i];
    22.             if (map.containsKey(xor)){
    23.                 int pre = map.get(xor);
    24.                 division[i] = pre == -1 ? 1 : Math.max(division[pre] + 1, division[i - 1]);
    25.             }
    26.             map.put(xor, i);
    27.         }
    28.         return division[arr.length - 1];
    29.     }
    30. }

     【案例3】

    【题目描述】

    【思路解析】

    这道题可以看作使用普通币完成a面值有x种方法，纪念币完成m-a面值有y种方法。然后对于这样使用普通币和纪念币完成m面值的方法为 x*y。所以我们使用两个动态规划分别得到普通币完成0……m面值的方法数，纪念币完成0……m面值的方法数。

    对于普通币的动态规划可以进行斜率优化。

    10010
    1
    1

    对于上面的表格可以做是普通币动态规划需要填充的表格，对于上面表格dp[i, j]表示使用0……i种，完成 j 面值的方法数。假设有三种货币分别为3，2，1，需要完成的面值为4。第一列根据定义表示为，使用 i种货币完成0面值的方法数，即不使用币，均为1。第一行表示为使用3这个货币，完成 j面值的方法数，然后第二行表示为使用 2和3这两个货币，完成 j面值的方法数，对于这一行任一j位置，它依赖与dp[i-1][j]  dp[i-1][j - 3]   dp[i-1][j - 6].......对于j - 3依赖dp[i-1][j - 3]   dp[i-1][j - 6].......所以我们对于任一j位置可以优化为dp[i][j] =  dp[i-1][j ] + dp[i][j - 3] .

    【代码实现】

    1. /**
    2.  * @ProjectName: study3
    3.  * @FileName: Ex3
    4.  * @author:HWJ
    5.  * @Data: 2023/9/16 17:09
    6.  */
    7. public class Ex3 {
    8.     public static void main(String[] args) {
    9.         int[] arr1 = {2,3,4};
    10.         int[] arr2 = {2,3,1};
    11.         System.out.println(dpWays(arr1, arr2, 8));
    12.     }
    13.  
    14.     public static int dpWays(int[] arr1, int[] arr2, int m){
    15.         int[][] dp1 = new int[arr1.length][m + 1];
    16.         int[][] dp2 = new int[arr2.length][m + 1];
    17.         for (int i = 0; i < arr1.length; i++) {
    18.             dp1[i][0] = 1;
    19.         }
    20.         for (int i = arr1[0]; i < m + 1; i += arr1[0]) {
    21.             dp1[0][i] = 1;
    22.         }
    23.         for (int i = 1; i < arr1.length; i++) {
    24.             for (int j = 1; j < m + 1; j++) {
    25.                 dp1[i][j] = dp1[i - 1][j] + ((j - arr1[i]) >= 0 ? dp1[i][j - arr1[i]] : 0);
    26.             }
    27.         }
    28.  
    29.         for (int i = 0; i < arr2.length; i++) {
    30.             dp2[i][0] = 1;
    31.         }
    32.         dp2[0][arr2[0]] = 1;
    33.         for (int i = 1; i < arr2.length; i++) {
    34.             for (int j = 1; j < m + 1; j++) {
    35.                 dp2[i][j] = dp2[i - 1][j] + ((j - arr2[i]) >= 0 ? dp2[i - 1][j - arr2[i]] : 0);
    36.             }
    37.         }
    38.         int ans = 0;
    39.         for (int i = 0; i < m + 1; i++) {
    40.             ans += dp1[arr1.length - 1][i] * dp2[arr2.length - 1][m - i];
    41.         }
    42.         return ans;
    43.     }
    44. }

    【案例4】

    【题目描述】

    【思路解析1】

    利用两个指针进行外排序，时间复杂度为O(K)。最没有营养的解法。

    【思路解析2】

    因为是两个排好序的数组，那一定可以通过二分查找。

    有两种情况第k位的数在A中，第k位的数在B中。

    每次在A数组进行二分找到一个数，然后通过这个数在B数组进行二分查找他应该在那个位置。这样我就知道这个数在A排第a + 1位，在B排第b + 1位，那么他在总数中排a+b+1位，通过a+b+1和k的大小关系，我们可以决定下一次二分查找的策略。如果最后在A中找到了，就返回这个数，否则，在B中进行一次这样的查找过程。时间复杂度为O(logM*logN)。

    【思路解析3】

    上中位数的定义，因为是两个等长度的数组的上中位数，则总长度一定为偶数，则假设总长度为4，a b c d。处于中间的有两个数b 和 c，我们认为b是上中位数，c是下中位数。

    我们定义一个函数，他能返回两个数组中的上中位数，要求两个数组等长度。

    现在开始解析这个函数的实现方法。这里给出奇数的分析方法，偶数更简单，可自行实现。

    abcde
    12345

    每次分别找到这两个数组的中间的那个数字（a.lenth - 1)/2，如果c==3，则返回他们的数值，他们一定是两个数组的中位数，否则不妨设c>3，那我们现在来考虑有那些数可能成为上中位数，标蓝的就是可能成为上中位数的可能性。但是这样划分的话，我们就没有办法进行递归了，因为我们要求的是两个数组一定要等长，所以我们单独验证3是否为上中位数，排除后用a b 4 5进行递归。递归的上中位数就是总体的中位数。

    好了现在我们有了这个函数后，我们进行总体可能性的划分。

    长数组的长度为 n，短数组的长度为m

    （1）k <=m。

    我们直接选取长数组的前k个元素和短数组的前k个元素进行求解上中位数，返回值就是第k位的数。

    （2） m < k <= n

    当m < k <= n时我们一定能筛选出某些数字一定不能作为第k位，然后删除它们，剩下的两个数组可能不是等长的（长数组会多一个），但是我们可以单独验证个别数来使两个数组变为等长的，然后用这两个剩下的数组进行求解上中位数。

    （3）k > n

    当k>n时我们一定能筛选出某些数字一定不能作为第k位，然后删除它们，剩下的两个数组应该是等长的，然后用这两个剩下的数组进行求解下中位数。但是我们的函数是求上中位数的，所以我们对这两个等长的数组的第一个元素进行检验，然后再对剩下的两个数组求上中位数。

    因为每次取出的数来递归的长度不会超过m，则时间复杂度为O(logM).

    【代码实现 仅实现最优解法的代码   对数器使用的是方法1】

    1. package AdvancedPromotion2;
    2.  
    3. import java.util.Arrays;
    4. import java.util.Random;
    5.  
    6. /**
    7.  * @ProjectName: study3
    8.  * @FileName: Ex4
    9.  * @author:HWJ
    10.  * @Data: 2023/9/17 15:23
    11.  */
    12. public class Ex4 {
    13.     public static void main(String[] args) {
    14.         Comparator();
    15.     }
    16.  
    17.     public static int getKDigitNum(int[] arr1, int[] arr2, int k){ // 这里保证k合法, 即在调用函数之前，验证k的合法性。
    18.         int n = Math.max(arr1.length, arr2.length);
    19.         int m = Math.min(arr1.length, arr2.length);
    20.         int[] longs = n == arr1.length ? arr1 : arr2;
    21.         int[] shorts = n == arr1.length ? arr2 : arr1;
    22.         if (k <= m){
    23.             return upperMedian(shorts, longs, 0, k - 1, 0, k - 1);
    24.         } else if (k <= n) {
    25.             int l = k - m;
    26.             if (longs[l - 1] > shorts[m - 1]){
    27.                 return longs[l - 1];
    28.             }else {
    29.                 return upperMedian(shorts, longs, 0, m - 1, l, k - 1);
    30.             }
    31.         } else {
    32.            int s = k - n;
    33.            int l = k - m;
    34.            if (longs[l - 1] >= shorts[m - 1]){
    35.                return longs[l - 1];
    36.            } else if (shorts[s - 1] >= longs[n - 1]) {
    37.                return shorts[s - 1];
    38.            }else {
    39.                return upperMedian(shorts, longs, s, m - 1, l , n - 1);
    40.            }
    41.         }
    42.     }
    43.  
    44.     // 求上中位数的函数
    45.     public static int upperMedian(int[] arr1, int[] arr2, int s1, int e1, int s2, int e2) {
    46.         if (s1 == e1) { // 当两个数组只有一个数时，进入baseCase
    47.             return Math.min(arr1[s1], arr2[s2]);
    48.         }
    49.         int mid1 = (e1 - s1) / 2 + s1;
    50.         int mid2 = (e2 - s2) / 2 + s2;
    51.         if (arr1[mid1] == arr2[mid2]) {
    52.             return arr1[mid1];
    53.         } else if (arr1[mid1] > arr2[mid2]) {
    54.             if ((e1 - s1) % 2 != 0) { // 数组长度为偶数情况下
    55.                 return upperMedian(arr1, arr2, s1, mid1, mid2 + 1, e2);
    56.             } else { // 数组长度为奇数情况下
    57.                 if (arr2[mid2] >= arr1[mid1 - 1]) {
    58.                     return arr2[mid2];
    59.                 } else {
    60.                     return upperMedian(arr1, arr2, s1, mid1 - 1, mid2 + 1, e2);
    61.                 }
    62.             }
    63.  
    64.         } else {
    65.             if ((e1 - s1) % 2 != 0) { // 数组长度为偶数情况下
    66.                 return upperMedian(arr1, arr2, mid1 + 1, e1, s2, mid2);
    67.             } else { // 数组长度为奇数情况下
    68.                 if (arr1[mid1] >= arr2[mid2 - 1]) {
    69.                     return arr1[mid1];
    70.                 } else {
    71.                     return upperMedian(arr1, arr2, mid1 + 1, e1, s2, mid2 - 1);
    72.                 }
    73.             }
    74.         }
    75.     }
    76.  
    77.     public static int compare(int[] arr1, int[] arr2, int k){
    78.         int p1 = 0;
    79.         int p2 = 0;
    80.         int ans = 0;
    81.         while (p1 + p2 < k){
    82.             if (p1 != arr1.length && p2 != arr2.length){
    83.                 if (arr1[p1] < arr2[p2]){
    84.                     ans = arr1[p1++];
    85.  
    86.                 }else {
    87.                     ans = arr2[p2++];
    88.                 }
    89.             }else {
    90.                 if (p1 == arr1.length){
    91.                     ans = arr2[p2++];
    92.                 }else {
    93.                     ans = arr1[p1++];
    94.                 }
    95.             }
    96.  
    97.         }
    98.         return ans;
    99.     }
    100.  
    101.     public static void Comparator(){
    102.         Random random = new Random();
    103.         int times = 50000;
    104.         int size = 1000;
    105.         int max = 10000;
    106.         for (int i = 0; i < times; i++) {
    107.             int[] arr1 = new int[random.nextInt(size) + 100];
    108.             int[] arr2 = new int[random.nextInt(size) + 100];
    109.             for (int j = 0; j < arr1.length; j++) {
    110.                 arr1[j] = random.nextInt(max);
    111.             }
    112.             for (int j = 0; j < arr2.length; j++) {
    113.                 arr2[j] = random.nextInt(max);
    114.             }
    115.             int k = random.nextInt(arr1.length + arr2.length) + 1;
    116.             Arrays.sort(arr1);
    117.             Arrays.sort(arr2);
    118.             int ans1 = getKDigitNum(arr1, arr2, k);
    119.             int ans2 = compare(arr1, arr2, k);
    120.             if (ans1 != ans2){
    121.                 System.out.println("失败！！！");
    122.                 System.out.println(ans1 + " " + ans2 + "  " + k);
    123.                 System.out.println(Arrays.toString(arr1));
    124.                 System.out.println(" ------------------ ");
    125.                 System.out.println(Arrays.toString(arr2));
    126.                 break;
    127.             }
    128.         }
    129.         System.out.println("成功！！！");
    130.     }
    131. }

  • 相关阅读:
    java毕业生设计养老院信息管理计算机源码+系统+mysql+调试部署+lw
    java-websocket自定义springboot 作为ws客户端
    K-均值聚类算法
    Linux系统编程——网络编程
    羊了个羊爆火，背后有什么样的营销套路？
    C语言程序设计—通讯录实现
    PMP每日一练 | 考试不迷路-9.21（包含敏捷+多选）
    【git命令】删除分支
    【数学建模】2018年数学建模国赛C题 基于RFMT 模型的百货商场会员画像描绘
    通过python采集lazada商品详情数据接口，支持多站点。
  • 原文地址：https://blog.csdn.net/weixin_73936404/article/details/132897175