Algorithm-Day02

前言

如果想成为别人口中的大佬，那就无时无刻的卷，追随着大佬的步伐......

练习

从一个数组，获取两个索引之间的总和

// 方法一：直接从索引一直累加
public static void LRSum_One(int[] arr, int L, int R){
// 参数：L：左边索引 R：右边索引 arr：所用数组
if(arr.length <= 1){
System.out.println("数组长度为1");
return;
}

int Sum = 0; // 用于保存总和
for(int i = L; i <= R; i++){
Sum += arr[i];
}
System.out.println("索引之间总和为" + Sum);
}

// 方法二: 生成0~N的累加，然后数组之间相减计算出结果
public static void printArray(int[] arr){
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i]+ " ");
}
System.out.println();
}

public static int LRSum_Two(int[] arr, int L, int R){
// 数组长度小于等于1或者输入的索引大于数组的长度，直接返回 报错
if(arr.length <=1 || R >= arr.length || L >= arr.length) return;
var preSum = new int[arr.length];
preSum[0] = arr[0];
for(var i = 1; i < arr.length; i++){
preSum[i] = preSum[i-1] + arr[i];
}
printArray(preSum);
return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
}

随机函数的玩法

//证明等概率：Math.Random() 返回[0,1)
//直接利用java.Raddom打印输出次数
public static void main(String[] args) {
int testTimes = 10000000;
int count = 0;
// 测试：累计随机X次，出现概率一致
for (int i = 0; i < testTimes; i++) {
if (Math.random() < 0.85) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
//接近于0.85
}

• 使概率调整为

//方式一：使用Math.Max，获取两次等概率取最大
public static double xToXPower() {
// 获取两个数值最大，所以必须Math.random产生的数值 两个必须要都要在范围内，不然就不会满足
return Math.max(Math.random(), Math.random());
}
for (int i = 0; i < testTimes; i++) {
if (xToXPower() < 0.17) {
count++;
}
}
System.out.println((double) count / (double) testTimes);


public static double xToThree() {
//同理可得 等概率的三次方
return Math.max(Math.random(),Math.max(Math.random(), Math.random()));
}//方式二：使用Max.min来实现
public static double xToXPower2() {
// 如果一个Math.random产生的数值在范围内，就会直接正确，所以必须要先算出两个都不在范围内的概率
return Math.min(Math.random(), Math.random());
}
for (int i = 0; i < testTimes; i++) {
if (xToXPower2() < 0.17) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
//必须 Math.random 产生的数值两个都不在范围内，1 - 得不到的范围内的概率
System.out.println((double) 1 - Math.pow((double) 1 - 0.17, 2));

• 给定一个范围内的概率，算出另外范围内的随机概率

//有一个函数fun()等概率返回 1-5 范围的数，如何借助当前fun()函数实现0 - 7范围的等概率返回？
public static int fun(){
return (int)(Math.random() * 5) + 1;
}
//先转换为等概率的0和1 的函数
//[1-5]之间等概率，都是20%
//以3为中心，小于三返回0；大于三返回1
public static int ZeroOne(){
int ans = fun();
//如果为随机出来三，就进行重新等概率生成
//循环10000次生成出来的从0~5的次数相似，所以等概率。
//又讲生成3的次数作为 循环次数，再次生成等概率的0~5，直到没有3
//或者讲将3生成概率的20%平分给别的数值
while(ans == 3){
ans = fun();
}
return ans < 3 ? 0 : 1;
}

//将 7 以二进制的形式表示，用最接近的位数进行等概率生成 1 1 1 = 7
public static void f7(){
return (ZeroOne() << 2) + (ZeroOne() << 1) + (ZeroOne() << 0);
}

• 思路：

随机给定一个数值范围的等概率，先生成0，1等概率生成的函数。

直接将将范围中心为界，进行0，1划为。

例如[0,8]等概率：生成0_3为0，58为1，生成4直接重新生成，知道没有出现4

求得范围内的等概率，将范围内的左边界，转换为0

[19，56] 转换为 [0,37]

再将右边界数值用二进制表示，位数作为0，1等概率生成的次数

37：100101 二进制表示6位

(ZeroOne() << ) + (ZeroOne() << ) + (ZeroOne() << ) + ..

最后加上数值 变为初始 左边界的数值

• 生成不等概率的0，1生成器，变为等概率的0，1生成器

//不等概率的0，1生成器
public static fun(){
return Math.random() < 0.85 ? 0 : 1
}

//0：生成率p 1：生成率1 - p
//调用两次fun方法，只有生成 0，1和1，0的概率一样。0，0和1，1概率不一致
//所以循环x次 因为只有分别生成0，1是等概率，用这两来生成等概率0，1
public static int OneTwo() {
int ans = 0;//初始化ans
do{
ans = x();
}while(ans == x());

return ans;
}

对数器

//因为Math.random能产生随机数值，可以用来生成随机的测试数组，都随机
//Math.random 产生[0,1) * length = (int)[0,length) 取整随机数值
public static int[] RandomLengthValue(int Length,int Value) {
int arrLength = (int) (Math.random() * Length); //产生随机长度的数组
int[] arr = new int[arrLength];

for(var i = 0; i < arr.length; i++){
arr[i] = (int) (Math.random() * Value); //数组赋值随机的数值
}
return arr; // 长度，整数数值都是随机的数组
}