[数据结构与算法] 前缀和，对数器与随机函数

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 前缀和，对数器与随机函数 -> 正文阅读

[数据结构与算法]前缀和，对数器与随机函数

数据结构分为物理结构与逻辑结构：
逻辑结构：有序表，链表，二叉树等
物理结构：紧密结构（连续结构），跳转结构
ps: 所有的逻辑结构都是基于物理结构所形成的（单一或组合。）
基本数据结构：
数组：便于寻址，不便于增加和删除
链表：便于增加和删除，不便于寻址

稍微特殊一点的是，当数组很大时，可能会出现少量的跳转结构。比如一亿长度的数组，1000万紧密存放在一起，然后尾指针指向下一个块的地址。

前缀和解法 --> 针对范围和问题
给定一个数组，任意给出左右边界的值，，求以O(1)的时间复杂度返回累加和。
（1）二维数组

（2）前缀和 --> 一维数组

public class Code01_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;
		}

	}

	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() --> 返回double类型 [0, 1)区间等概率返回（因为小数有精度，所以小数不是无穷的）

–> [0, 1) --> [0, 8) 注意是double类型
Math.random() * 8

–>double [0, 1) --> (int)(Math.random() * K) --> int [0, K) --> int [0, K-1]
通过随机函数，可以得到任意范围的值 e.g. [16, 54] ([0, 1) * 39 + 16 )。
Math.random * K + t
通过随机函数，实现不等概率返回，对于生成的任意数值,使得出现在[0 ,x]出现的概率的
3.1 使得 [0， x) 的出现的概率为 x^2

3.2 使得[0, x)出现的概率为 1-(1 - x)^2
答： Math.min(Math.random(), Math.random());

随机函数面试题
4.1 从 1 ~ 5 随机 f(x) 到 1 ~ 7 g(x) 随机等概率
（1）1 2 --> 0; 3 重做； 4 5 --> 1 >>>>>>>>> 实现等概率01生成器
（2）1 ~ 7共7个数字，三位二进制可以满足（8种组合），对二进制进行移位 (x<<3 + x<<2 + x<<1) 属于范围 [0, 7]
（3）封装函数， do { } while (x == 0) ----> 0重做，其余输出，从而完成 1 - 7等概率随机

// 1~5随机 [1, 5] --> int [1, 6) --> int [0, 5) + 1
public static int f() {
    return (int) (Math.random() * 5 + 1);
}

// 等概率01生成器
public static int _01Generator() {
    int ans;
    do {
        ans = f();
    } while (ans == 3);
    return ans < 3 ? 0 : 1;
}

public static int g() {
    int ans;
    do {
        // 小心这里，记不清顺序 就乖乖把 括号加上，保证运算顺序
        ans = (_01Generator() << 2) + (_01Generator() << 1) + (_01Generator() << 0);
    } while (ans == 0);
    return ans;
}

OR
（3）在第二步之后，将其变成 [0, 6]的等概率生成器（7重做）, 然后封装函数，使其返回值 +1 ，就变成了 [1, 7]。

// return [0, 6]
public static int g1() {
    int ans = 0;
    do {
        ans = (_01Generator() << 2) + (_01Generator() << 1) + (_01Generator() << 0);
    } while (ans == 7); // return [0,7] ----> [0, 6]
    return ans;
}

public static int g2(){
    return g1() + 1;
}

4.2 从 a ~ b 随机到 c ~ d 随机 - 等概率
推荐使用后一种（3），基本方法相同。但latter更有普适性。（比如 3-19生成器变为 128-150生成器，只需将[128,150] —> [0, 22] + 128，从而不需要生成过多二进制位）
构造01等概率发生器（奇数重新生成，偶数直接对半分），寻找包含范围的二进制位数，调整对应的生成随机数范围
4.3 从01不等概率到01等概率随机
0 0 --> 重做
1 1 --> 重做
1 0 --> 50% --> 返回 1
0 1 --> 50% --> 返回 0

// 01不等概率生成器 0的概率为 P = 0.8， 1的概率为 0.2
public static int x(){
    return Math.random() > 0.8 ? 0: 1;
}

// 转换为01等概率
public static int y(){
    int ans;
    do{
        ans = x();
    }while( ans == x());
    return ans;
}