第2节 数据结构、前缀和、对数器

数据结构

• 数据结构（所有都是）
  • 连续结构
  • 跳转结构
  • 连续+跳转 结构

• 概念
  • 数据结构是存储、组织数据的方式
  • 精心选择的数据结构可以带来更高的运行或者存储效率
  • 数据结构是很多算法得以进行的载体
• 最基本的数据结构
  • 数组（是连续结构）
    • 便于寻址，不便于增删数据
  • 链表（是跳转结构）
    • 便于增删数据，不便于寻址

前缀和

• 正方形（遍历两边）｛查询量大，查询频繁时。使用｝
• 代码如下

• package class02;
  
  
  public class Code_PreSum {
      // 正方形
      public static class RangeSum1 {
          private int[] arr;
  
          public RangeSum1(int[] array) {
              arr = array;
          }
  
          public int rangeSum(int L, int R) {
              int sum = 0;
              for (int i = L; i <= R; i++) {
                  sum += arr[i];
              }
              return sum;
          }
      }
  
      /**
       * 前缀数组
       * 假设有一个数组arr,用户总是频繁的查询arr中某一段的累加和
       * 你如何组织数据，能让这种查询变得便利和快捷？
       * 解答如下
       */
      public static class RangeSUm2 {
          private int[] preSum; // 前缀和
  
          public RangeSUm2(int[] array) {
              int N = array.length;
              preSum = new int[N];
              preSum[0] = array[0];
              for (int i = 1; i < N; i++) {
                  preSum[i] = preSum[i - 1] + array[i];
              }
          }
  
          public int rangeSum(int L, int R) {
              return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
          }
      }
  }

对数器

介绍随机函数（Java中的Math.random()）

• 基本代码

• package class02;
  
  public class Code_RandToRand {
  
      public static void main(String[] args) {
          System.out.println("测试开始");
          // Math.random() -> double(返回类型) -> [0,1)(范围)
          // 0到1 等概率 返回一个数
  
          int testTimes = 10000000;
          int count = 0; // 定义变量统计次数
          for (int i = 0; i < testTimes; i++) {
              if (Math.random() < 0.7) {
                  count++;
              }
          }
          // 打印的数接近0.7
          System.out.println((double) count / (double) testTimes); // 真实出现次数除总次数的概率
  
          System.out.println("===========");
  
          // [0,1) -> *8 [0,8)
          count = 0;
  //        double ans = Math.random()*8; // 在0~8上等概率返回一个数
          for (int i = 0; i < testTimes; i++) {
              if (Math.random() * 8 < 4) {
                  count++;
              }
          }
          // 打印的数接近0.5
          System.out.println((double) count / (double) testTimes);
  
          System.out.println("===========");
          /*
           * 重点
           * */
          int K = 9;
          // [0,K) -> * K(整型) [0,K-1] (变成0~K-1左闭右闭)
          int[] counts = new int[9]; // counts[0] = 0次数 counts[1] = 1出现的次数
          for (int i = 0; i < testTimes; i++) {
              int ans = (int) (Math.random() * K); // [0,K-1]
              counts[ans]++;
          }
          for (int i = 0; i < K; i++) {
              System.out.println(i + "这个数，出现了" + counts[i] + "次"); // 打印结果都差不多（即等概率）
          }
          System.out.println("===========");
  
          // 测试xToXPower2()
          count = 0;
          double x = 0.7;
          for (int i = 0; i < testTimes; i++) {
              if (xToXPower2() < x) {
                  count++;
              }
          }
          // 以下两个打印出来的概率差不多
          System.out.println((double) count / (double) testTimes);
          System.out.println(Math.pow(x, 2)); // x的平方
  
          // 测试xToXPower_2()
          count = 0;
          double y = 0.7;
          for (int i = 0; i < testTimes; i++) {
              if (xToXPower_2() < y) {
                  count++;
              }
          }
          System.out.println((double) count / (double) testTimes);
          System.out.println((double) 1 - Math.pow((double) 1 - y, 2)); // x的平方
  
      }
  
  
      // 返回[0,1)的一个小数
      // 任意的x， x属于[0,1), [0,x)范围上的数出现概率由原来的x调整为x平方
      public static double xToXPower2() {
          return Math.max(Math.random(), Math.random()); // 直接调两次随机数，再返回最大值
          // 0~x,两次都命中x，最大值返回，才是x的平方
          // 依次类推，3次方就再调用一次随机数的最大值
  
      }
  
      public static double xToXPower_2() {
          return Math.min(Math.random(), Math.random()); // 直接调两次随机数，再返回最小值
          // [0,x)
          // 得不到0~x的概率,只有第一次是得不到0~x的概率即1-x，并且第二次也是1-x，才是得不到的概率（1-x）的平方，所以得到概率是1-（1-x）的平方
      }
  }

• ?问题
  • 从1~5随机到1~7随机

    • package class02;
      
      public class Code_Practice01 {
          // f()函数，不可以改
          public static int f() { // 实现1~5的随机
              return (int) (Math.random() * 5) + 1;
          }
      
          // 随机机制，只能用f，
          // 等概率返回0和1
          public static int f1() {
              int ans = 0;
              do {
                  ans = f();
              }
              while (ans == 3); // 等于3，就一直重新做，直到f()不等于3时（相当于3不要）
              return ans < 3 ? 0 : 1; // 小于3是0，否则为1
          }
      
          // 得到000~111 做到等概率  即是0~7等概率返回一个 1+2+4=7，即2的0次方，1次方，2次方相加
          // 一个二进制位是0~1等概率随机，两个二进制位是0~3等概率随机，三个二进制位是0~7等概率随机，调用三次就行（他们是独立的）
          public static int f2() {
              return (f1() << 2) + (f1() << 1) + (f1() << 0);// (f1() << 2)确定第一位 (f1() << 1)确定第二位 (f1() << 0)确定第三位 所以这个式子要么是000，要么是111
          }
      
          // 0~6等概率返回
          public static int f3() {
              int ans = 0;
              do {
                  ans = f2();
              } while (ans == 7);
              return ans;
          }
      
          // 1~7等概率返回(目标实现)
          public static int g() {
              return f3() + 1;
          }
      
          public static void main(String[] args) {
              int testTimes = 10000000;
              // f1()
              int count = 0; // 定义变量统计次数
              for (int i = 0; i < testTimes; i++) {
                  if (f1() == 0) {
                      count++;
                  }
              }
              System.out.println("f1的概率" + (double) count / (double) testTimes); // 接近0.5，所以f1()函数无问题
              System.out.println("=========");
      
              // f2()
              count = 0; // 定义变量统计次数
              for (int i = 0; i < testTimes; i++) {
                  if (f2() == 0) {
                      count++;
                  }
              }
              System.out.println((double) count / (double) testTimes); // 接近0.125，所以f2()函数无问题
              System.out.println("=========");
      
              count = 0; // 定义变量统计次数
              for (int i = 0; i < testTimes; i++) {
                  if (f3() == 0) {
                      count++;
                  }
              }
              System.out.println((double) count / (double) testTimes); // 接近0.142，所以f3()函数无问题
              System.out.println("=========");
      
              // 测试f2()
              int[] counts = new int[8];
              for (int i = 0; i < testTimes; i++) {
                  int num = f2();
                  counts[num]++;
              }
              for (int i = 0; i < 8; i++) {
                  System.out.println(i + "这个数，出现了" + counts[i] + '次'); // 打印结果接近，所以是等概率
              }
              System.out.println("=========");
              // 测试f3()
              counts = new int[8];
              for (int i = 0; i < testTimes; i++) {
                  int num = f3();
                  counts[num]++;
              }
              for (int i = 0; i < 8; i++) {
                  System.out.println(i + "这个数，出现了" + counts[i] + '次'); // 打印结果,7这个数，出现了0次
              }
              System.out.println("=========");
      
              // 实现g()
              counts = new int[8];
              for (int i = 0; i < testTimes; i++) {
                  int num = g();
                  counts[num]++;
              }
              for (int i = 0; i < 8; i++) {
                  System.out.println(i + "这个数，出现了" + counts[i] + '次'); // 打印结果,7这个数，出现了0次
              }
              System.out.println(f());
          }
      }

  • 从1~5随机到3~9

    • package class02;
      
      
      public class Code_Practice02 {
          public static int f() {
              return (int) (Math.random() * 5) + 1;
          }
      
          public static int f1() {
      
              int ans = 0;
              do {
                  ans = f();
              } while (ans == 3);
              return ans < 3 ? 0 : 1;
          }
      
          public static int f2() {
              // 1+2+4+8+16=31 19需要5个进制位才满足，4个够不着
              return ((f1() << 4) + (f1() << 3)+(f1() << 2)+(f1() << 1)+(f1() << 0));
          }
          // 0~16等概率返回
          public static int f3() {
              int ans = 0;
              do {
                  ans = f2();
              // 重点！！！
              } while (ans >16); // 19-3=16，大于16的一直重新做，直到不大于16!
              return ans ;
          }
          // 3~19等概率返回
          public static int g() {
              return f3() +3;
          }
      
          public static void main(String[] args) {
              int testTimes = 10000000;
              int count = 0; // 定义变量统计次数
              for (int i = 0; i < testTimes; i++) {
                  if (f1() == 0) {
                      count++;
                  }
              }
              System.out.println("f1的概率" + (double) count / (double) testTimes); // 接近0.5，所以f1()函数无问题
              System.out.println("=========");
      
              int[] counts = new int[20];
              for (int i = 0; i < testTimes; i++) {
                  int num = g();
                  counts[num]++;
              }
              for (int i = 0; i < 20; i++) {
                  System.out.println(i + "这个数，出现了" + counts[i] + "次");
              }
      
          }
      }

  • 01不等概率随机到01等概率随机

    • package class02;
      
      public class Code_Practice03 {
          // 你只能指定，x会以固定概率返回0和1，但是x的内容，你看不到
          public static int x() {
              return Math.random() < 0.84 ? 0 : 1;
          }
      
          // 等概率返回0和1
          public static int y() {
              int ans = 0;
              do {
                  ans = x(); // 第一次拿值，拿了0 或 1
              } while (ans == x()); // 如果第一次拿的值等于第二次的值，它就重做
              // ans = 0 1
              // ans = 1 0
              // 以上两种情况出来
              return ans;
          }
      
          public static void main(String[] args) {
              int testTimes = 10000000;
              int count = 0;
              for (int i = 0;i<testTimes;i++){
                  if (y() ==0){
                      count++;
                  }
              }
              System.out.println((double) count/(double) testTimes); // 接近0.5，函数满足
          }
      }

?Java的值传递

• 定义

  • 值传递（pass by value）是指在调用函数时将实际参数复制一份传递到函数中，这样在函数中如果对参数进行修改，将不会影响到实际参数。
  • 引用传递（pass by reference）是指在调用函数时将实际参数的地址直接传递到函数中，那么在函数中对参数所进行的修改，将影响到实际参数。

• 区别

• Java中只有值传递

  • 纠正一下大家以前的那些错误看法
    • 错误理解一：值传递和引用传递，区分的条件是传递的内容，如果是个值，就是值传递。如果是个引用，就是引用传递
    • 错误理解二：Java是引用传递。
    • 错误理解三：传递的参数如果是普通类型，那就是值传递，如果是对象，那就是引用传递。
  • 求值策略
    • 我们说当进行方法调用的时候，需要把实际参数传递给形式参数，那么传递的过程中到底传递的是什么东西呢？这其实是程序设计中求值策略（Evaluation strategies）的概念。
    • 在计算机科学中，求值策略是确定编程语言中表达式的求值的一组（通常确定性的）规则。求值策略定义何时和以何种顺序求值给函数的实际参数、什么时候把它们代换入函数、和代换以何种形式发生。
    • 求值策略分为两大基本类，基于如何处理给函数的实际参数，分为严格的和非严格的。

• 总结

  • 我们知道，编程语言中需要进行方法间的参数传递，这个传递的策略叫做求值策略。
  • 在程序设计中，求值策略有很多种，比较常见的就是值传递和引用传递。还有一种值传递的特例——共享对象传递。
  • 值传递和引用传递最大的区别是传递的过程中有没有复制出一个副本来，如果是传递副本，那就是值传递，否则就是引用传递。
  • 在Java中，其实是通过值传递实现的参数传递，只不过对于Java对象的传递，传递的内容是对象的引用
  • 我们可以总结说，Java中的求值策略是共享对象传递，这是完全正确的。
  • 但是，为了让大家都能理解你说的，我们说Java中只有值传递，只不过传递的内容是对象的引用。这也是没毛病的。但是，绝对不能认为Java中有引用传递。