数据结构 前缀和 对数器

数据结构

任何数据结构都是由两个基本数据原件组成 :

00.前缀和 对数器 - 图1

数组（连续结构）：擅长寻址 不擅长添加、删除数据

链表（跳转结构）：不擅长寻址 擅长添加删除数据

前缀和

预处理结构： 单次查询 : 快速求出下标 m 到 n 的和

[ 1 , 2 , 3 , 5 , 6 , 7 , 8 , 9 ]

0 1 2 3 4 5 6 7

二维数组 :

下标 0 1 2 3 4 5 6 7
0 1 3 6 11 15 22 30 39
1 × 2 5 10 14 21 29 38
2 × × 3 8 12 19 27 36
3 × × × 5 9 16 24 33
4 × × × × 6 13 21 30
5 × × × × × 7 16 25
6 × × × × × × 8 17
7 × × × × × × × 9

每一位都是前几位的和,这样可以快速求出 第m位到第n位的和 (生成表的代价为 n/2 的规模)

  1. 如果用一维数组表示:

    1.  arr [ 3 , 2 , -1 , 6 , 7 , 2 , -2 ]
  1.           0   1   2   3   4   5   6
  1. H [ 3 , 5 , 4 , 10 , 17 , 19 , 17 ]
    1.   0   1   2   3    4     5    6
  1. 由此 H[ i ] = arr[ 0 ~ i ]累加和
  1.     3 ~ 7 = H[7] - H[2]

  1. 结论: m~n的累加和 :

    1. 如果m==0 sum=H[n];
    2. 如果m !=0 sum= H[n] - H[ m - 1 ]

测试：

  1. public static void main(String[] args) {
  2.     int[] arr = {3, 2, -1, 6, 7, 2, -2};
  3.     System.out.println(preSum01(arr,2,4));
  4.     System.out.println(preSum02(arr,2,4));
  5. }

传统累加代码：

  1. public static int preSum02(int[] arr,int L,int R){
  2.     int sum = 0;
  3.     for (int i = L; i <= R; i++) {
  4.         sum += arr[i];
  5.     }
  6.     return sum;
  8. }

前缀和代码：

  1. public static int preSum(int[] arr,int m,int n) {
  2.         int[] newarr = new int[arr.length];
  3.         newarr[0] = arr[0];
  4.         for (int i = 1; i < arr.length; i++) {
  5.             newarr[i] = newarr[i - 1] + arr[i];
  6.         }
  7.         return m == 0 ? newarr[n] : newarr[n] - newarr[m - 1];
  8. }

随机数

Math.random()

[ 0 , 1 ) 的数字等概率返回

  1. 如何返回等概率返回 1~n

    1.  `( int ) ( Math.random() * n ) + 1`

  2. 设定一个f() f() = (int) (Math.random() * 5) + 1;

    1. // 此函数只能用，不能修改
    2. // 等概率返回1~5
    3. public static int f() {
    4.  return (int) (Math.random() * 5) + 1;
    5.  }
  1. 如何用 f() 等概率返回 0 和 1
    1. // 等概率得到0和1
    2.  public static int a() {
    3.      int ans = 0;
    4.      do {
    5.          ans = f();
    6.      } while (ans == 3);
    7.      return ans < 3 ? 0 : 1;
    8.  }
  1. 如何用 f() 等概率返回 0~6
    1. // 等概率返回0~6
    2.  public static int b() {
    3.      int ans = 0;
    4.      do {
    5.          ans = (a() << 2) + (a() << 1) + a();
    6.      } while (ans == 7);
    7.      return ans;
    8.  }
  1. 如何用 f() 等概率返回 1~7
    1. // 等概率返回1~7
    2.  public static int c() {
    3.      return b() + 1;
    4.  }

  1. 唯一的随机机制 只能初始化 不可修改

    1. // 这个结构是唯一的随机机制
    2.  // 你只能初始化并使用，不可修改
    3.  public static class RandomBox {
    4.      private final int min;
    5.      private final int max;
    7.      // 初始化时请一定不要让mi==ma
    8.      public RandomBox(int mi, int ma) {
    9.          min = mi;
    10.          max = ma;
    11.      }
    13.      // 13 ~ 17
    14.      // 13 + [0,4]
    15.      public int random() {
    16.          return min + (int) (Math.random() * (max - min + 1));
    17.      }
    19.      public int min() {
    20.          return min;
    21.      }
    23.      public int max() {
    24.          return max;
    25.      }
    26.  }
  1. 利用条件RandomBox，如何等概率返回0和1
    1. // 利用条件RandomBox，如何等概率返回0和1
    2.  public static int rand01(RandomBox randomBox) {
    3.      int min = randomBox.min();
    4.      int max = randomBox.max();
    5.      // min ~ max
    6.      int size = max - min + 1;
    7.      // size是不是奇数，odd 奇数
    8.      boolean odd = (size & 1) != 0;
    9.      int mid = size / 2;
    10.      int ans = 0;
    11.      do {
    12.          ans = randomBox.random() - min;
    13.      } while (odd && ans == mid);
    14.      return ans < mid ? 0 : 1;
    15.  }

  1. 给你一个RandomBox，这是唯一能借助的随机机制
    等概率返回from~to范围上任何一个数 要求from<=to

    1. public static int random(RandomBox randomBox, int from, int to) {
    2.      if (from == to) {
    3.          return from;
    4.      }
    5.      // 3 ~ 9
    6.      // 0 ~ 6
    7.      // 0 ~ range
    8.      int range = to - from;
    9.      int num = 1;
    10.      // 求0～range需要几个2进制位
    11.      while ((1 << num) - 1 < range) {
    12.          num++;
    13.      }
    15.      // 我们一共需要num位
    16.      // 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
    17.      int ans = 0;
    18.      do {
    19.          ans = 0;
    20.          for (int i = 0; i < num; i++) {
    21.              ans |= (rand01(randomBox) << i);
    22.          }
    23.      } while (ans > range);
    24.      return ans + from;
    25.  }

  1. 测试类

    1. public static void main(String[] args) {
    2.      System.out.println("测试开始");
    3.      // Math.random() -> double -> [0,1)
    4.      //
    6.      int testTimes = 10000000;
    7.      int count = 0;
    8.      for (int i = 0; i < testTimes; i++) {
    9.          if (Math.random() < 0.75) {
    10.              count++;
    11.          }
    12.      }
    13.      System.out.println((double) count / (double) testTimes);
    15.      System.out.println("=========");
    17.      // [0,1) -> [0,8)
    18.      count = 0;
    19.      for (int i = 0; i < testTimes; i++) {
    20.          if (Math.random() * 8 < 5) {
    21.              count++;
    22.          }
    23.      }
    24.      System.out.println((double) count / (double) testTimes);
    25.      System.out.println((double) 5 / (double) 8);
    27.      int K = 9;
    28.      // [0,K) -> [0,8]
    30.      int[] counts = new int[9];
    31.      for (int i = 0; i < testTimes; i++) {
    32.          int ans = (int) (Math.random() * K); // [0,K-1]
    33.          counts[ans]++;
    34.      }
    35.      for (int i = 0; i < K; i++) {
    36.          System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
    37.      }
    39.      System.out.println("=========");
    41.      count = 0;
    42.      double x = 0.17;
    43.      for (int i = 0; i < testTimes; i++) {
    44.          if (xToXPower2() < x) {
    45.              count++;
    46.          }
    47.      }
    48.      System.out.println((double) count / (double) testTimes);
    49.      System.out.println((double) 1 - Math.pow((double) 1 - x, 2));
    51.      System.out.println("==========");
    52.      count = 0;
    53.      for (int i = 0; i < testTimes; i++) {
    54.          if (f2() == 0) {
    55.              count++;
    56.          }
    57.      }
    58.      System.out.println((double) count / (double) testTimes);
    60.      System.out.println("==========");
    62.      counts = new int[8];
    63.      for (int i = 0; i < testTimes; i++) {
    64.          int num = g();
    65.          counts[num]++;
    66.      }
    67.      for (int i = 0; i < 8; i++) {
    68.          System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
    69.      }
    71.  }
  1. 返回[0,1)的一个小数
    任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方
    1. public static double xToXPower2() {
    2.  return Math.max(Math.random(), Math.random());
    3. }
  1. 使用 f1() 等概率返回 0 和 1
    1. public static int f2() {
    2.  int ans = 0;
    3.  do {
    4.      ans = f1();
    5.  } while (ans == 3);
    6.  return ans < 3 ? 0 : 1;
    7. }
  1. 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个
    1. public static int f3() {
    2.  return (f2() << 2) + (f2() << 1) + f2();
    3. }

  1. 0 ~ 6等概率返回一个

    1. public static int f4() {
    2.  int ans = 0;
    3.  do {
    4.      ans = f3();
    5.  } while (ans == 7);
    6.  return ans;
    7. }
    9. public static int g() {
    10.  return f4() + 1;
    11. }
  1. 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
    1. public static int x() {
    2.  return Math.random() < 0.84 ? 0 : 1;
    3. }


y()函数 自己写 : 等概率返回0和1

  1.  public static int y() {
  2.         int ans = 0;
  3.         do {
  4.             ans = x();
  5.         } while (ans == x());
  6.         return ans;
  7.          // ans = 0 1
  8.          // ans = 1 0
  9.          // 0 和 1 必然等概率
  10.     }
  1. 出现 1 的概率为 p , 出现 0 的概率为1 - p
    求出现 1 和 0 概率相同 ```java 1 1 -> p p 不要

1 0 -> p 1-p 要

0 1 -> 1-p p 要

0 0 -> 1-p 1-p 不要

则 1 0 和 0 1 的概率 一样

  4. <a name="c35a5d61"></a>
  5. ## 对数器
  7. ```java
  8. public class Code03_Comp {
  10.     public static void selectionSort(int[] arr) {
  11.         if (arr == null || arr.length < 2) {
  12.             return;
  13.         }
  14.         for (int i = 0; i < arr.length - 1; i++) {
  15.             int minIndex = i;
  16.             for (int j = i + 1; j < arr.length; j++) {
  17.                 if (arr[j] < arr[minIndex]) {
  18.                     minIndex = j;
  19.                 }
  20.             }
  21.             swap(arr, i, minIndex);
  22.         }
  23.     }
  25.     public static void swap(int[] arr, int i, int j) {
  26.         int tmp = arr[i];
  27.         arr[i] = arr[j];
  28.         arr[j] = tmp;
  29.     }
  31.     public static void insertionSort(int[] arr) {
  32.         if (arr == null || arr.length < 2) {
  33.             return;
  34.         }
  35.         for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
  36.             for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
  37.                 swap(arr, j, j + 1);
  38.             }
  39.         }
  40.     }
  42.     // 返回一个数组arr，arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]
  43.     public static int[] lenRandomValueRandom(int maxLen, int maxValue) {
  44.         int len = (int) (Math.random() * maxLen);
  45.         int[] ans = new int[len];
  46.         for (int i = 0; i < len; i++) {
  47.             ans[i] = (int) (Math.random() * maxValue);
  48.         }
  49.         return ans;
  50.     }
  52.     public static int[] copyArray(int[] arr) {
  53.         int[] ans = new int[arr.length];
  54.         for (int i = 0; i < arr.length; i++) {
  55.             ans[i] = arr[i];
  56.         }
  57.         return ans;
  58.     }
  60.     // arr1和arr2一定等长
  61.     public static boolean isSorted(int[] arr) {
  62.         if (arr.length < 2) {
  63.             return true;
  64.         }
  65.         int max = arr[0];
  66.         for (int i = 1; i < arr.length; i++) {
  67.             if (max > arr[i]) {
  68.                 return false;
  69.             }
  70.             max = Math.max(max, arr[i]);
  71.         }
  72.         return true;
  73.     }
  75.     public static void main(String[] args) {
  76.         int maxLen = 5;
  77.         int maxValue = 1000;
  78.         int testTime = 10000;
  79.         for (int i = 0; i < testTime; i++) {
  80.             int[] arr1 = lenRandomValueRandom(maxLen, maxValue);
  81.             int[] tmp = copyArray(arr1);
  82.             selectionSort(arr1);
  83.             if (!isSorted(arr1)) {
  84.                 for (int j = 0; j < tmp.length; j++) {
  85.                     System.out.print(tmp[j] + " ");
  86.                 }
  87.                 System.out.println();
  88.                 System.out.println("选择排序错了！");
  89.                 break;
  90.             }
  91.         }
  93.     }
  95. }