一、数据结构基本分类
连续的（数组）、跳转的（链表）（或者连续的+跳转的）
二、最基本的数据结构
- 数组：便于寻址，不便于增删改查
- 链表：便于增删数据，不便于寻址
三、随机函数
1、Java中的Math.random()函数
平时刷题验证自己方法正确的一个很灵魂的东西
1
2
3
| java中的Math.random()可以返回一个随机的double的数字，范围是[0,1)
而且是等概率返回一个，但是数学上是做不到等概率返回一个数的，而计算机是可以的，这是因为计算机中所有的小数都是有精度的
下面的例子就可以测试下这个问题
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| package com.shifpeng.algorithmnovice.applets;
public class RandToRand {
public static void main(String[] args) {
int times = 10000000;
int count = 0;
double randNum = 0.35;
for (int j = 0; j < times; j++) {
if (Math.random() < randNum) {
count++;
}
}
System.out.println((double) count / (double) times);
}
}
|
那么如果使用Math.random()✖️一个数（a），那么就是从0到这个数a(左闭右开)返回一个
int ans = (int) (Math.random() * k); 等概率的返回一个[0,k-1)中的一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class RandToRand {
public static void main(String[] args) {
int k = 9;
int[] counts = new int[9];
for (int j = 0; j < times; j++) {
int ans = (int) (Math.random() * k);
counts[ans]++;
}
for (int i = 0; i < counts.length; i++) {
System.out.printf(i+"这个数出现了"+counts[i]+"次");
}
}
}
|
执行结果：
1
2
3
4
5
6
7
8
9
| 0这个数出现了1109956次
1这个数出现了1111296次
2这个数出现了1110856次
3这个数出现了1110434次
4这个数出现了1113265次
5这个数出现了1110023次
6这个数出现了1110999次
7这个数出现了1110828次
8这个数出现了1112343次
|
问：如果要求任意的X,X属于[0,1)，[0,X)范围上的数出现的概率由原来的x调整成X平方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| package com.shifpeng.algorithmnovice.applets;
public class RandToRand {
public static void main(String[] args) {
int times = 10000000;
count = 0;
double x = 0.63;
for (int j = 0; j < times; j++) {
if (xToPower2() < x) {
count++;
}
}
System.out.println((double) count / (double) times);
System.out.println((Math.pow(x, 2)));
}
public static double xToPower2() {
return Math.max(Math.random(), Math.random());
}
}
0.3968045
0.39690000000000003
|
两次随机行为，怎么才能让最终的值在[0,X)上，那么只有每次行为都落到[0,X)，才能返回在[0,X)上面。
两个都在这个范围。那么出现的概率就是X^2
比如：X=0.3，第一次随机行为返回[0,0.3)上的数，概率是0.3，第二次随机行为返回[0,0.3)上的数，概率还是0.3，只有两次都返回这个区间的数字，最后Math.max(Math.random(), Math.random())才能返回[0,0.3)的数，所以概率就是0.3*0.3
同理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| package com.shifpeng.algorithmnovice.applets;
public class RandToRand {
public static void main(String[] args) {
int times = 10000000;
int count = 0;
count = 0;
double x = 0.17;
for (int j = 0; j < times; j++) {
if (xToPower3() < x) {
count++;
}
}
System.out.println((double) count / (double) times);
System.out.println((Math.pow(x, 3)));
}
public static double xToPower3() {
return Math.max(Math.random(), Math.max(Math.random(), Math.random()));
}
}
0.0049114
0.004913000000000001
|
**这里有人会问：为什么不用min()? **
如果用min()，那么只要有一次 随机行为返回[0,X)，那么Math.min(Math.random(), Math.random());就可以返回[0,X)范围上的数
那使用min之后，返回值在[0,X)的概率是多少呢？
Math.min(Math.random(), Math.random());
那就是上面的：
第一个随机行为返回[0,X)，第二个随机行为不返回[0,X)
第一个随机行为不返回[0,X)，第二个随机行为返回[0,X)
两个随机行为都返回[0,X)
我们反过来推算：
一个随机行为返回[0,X)的概率是X，那么不返回的概率就是1-X，那么两次都不返回的概率就是(1-x)^2，因此，使用min()返回[0,X)的概率就是1-(1-x)^2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| package com.shifpeng.algorithmnovice.applets;
public class RandToRand {
public static void main(String[] args) {
int times = 10000000;
int count = 0;
count = 0;
x = 0.17;
for (int j = 0; j < times; j++) {
if (xToPower2() < x) {
count++;
}
}
System.out.println((double) count / (double) times);
System.out.println((1 - Math.pow((double) 1 - x, 2)));
}
public static double xToPower2() {
return Math.min(Math.random(), Math.random());
}
}
0.3110039
0.31110000000000004
|
2、常见面试题
有一个函数f(),可以等概率的返回1,2,3,4,5，不能借助其他，只根据这个f()，等概率得到1，2，3，4，5，6，7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| package com.shifpeng.algorithmnovice.applets.RandonFunction;
public class RandInterview {
public static void main(String[] args) {
int times = 10000000;
int count = 0;
for (int j = 0; j < times; j++) {
if (f1() == 0) {
count++;
}
}
System.out.println("得到0的概率：" + (double) count / (double) times);
}
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;
}
}
|
上面我们写了一个f1()函数，用来等概率返回0和1，接着
既然需要1～7范围等概率，那么如果得到0～6等概率，那+1之后就可以得到
那么如何得到0～6的等概率呢？
看看这个范围需要几个二进制位：
一个二进制位，可以得到0～1范围上的等概率，即00000000 00000001，即1
两个二进制位，可以得到0～3范围上的等概率，即00000000 00000011，即3
三个二进制位，可以得到0～3范围上的等概率，即00000000 00000011，即7
因此，需要三个二进制位可以得到0～7上的等概率随机
每个二进制位调用一次f1()，那么得到的都是等概率的
1
2
3
4
5
6
7
8
9
10
11
|
public static int f2() {
return (f1() << 2) + (f1() << 1) + (f1() << 0);
}
|
新增一个方法f2(),做到0～7等概率返回一个
测试一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void main(String[] args) {
int times = 10000000;
for (int j = 0; j < times; j++) {
int num = f2();
counts[num]++;
}
for (int i = 0; i < counts.length; i++) {
System.out.println("得到" + i + "这个数的次数为：" + counts[i] + "次");
}
得到0这个数的次数为：1248902次
得到1这个数的次数为：1251259次
得到2这个数的次数为：1249346次
得到3这个数的次数为：1249131次
得到4这个数的次数为：1248915次
得到5这个数的次数为：1251108次
得到6这个数的次数为：1251808次
得到7这个数的次数为：1249531次
|
所以是等概率的
但是题目要求的是0~6，那根据前面的做法，我们遇到7就重新来呗，不返回
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static int f3() {
int ans = 0;
do {
ans = f2();
} while (ans == 7);
return ans;
}
|
继续测试一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void main(String[] args) {
int times = 10000000;
for (int j = 0; j < times; j++) {
int num = f3();
counts[num]++;
}
for (int i = 0; i < counts.length; i++) {
System.out.println("得到" + i + "这个数的次数为：" + counts[i] + "次");
}
得到0这个数的次数为：1428772次
得到1这个数的次数为：1426569次
得到2这个数的次数为：1428955次
得到3这个数的次数为：1428804次
得到4这个数的次数为：1429490次
得到5这个数的次数为：1428054次
得到6这个数的次数为：1429356次
得到7这个数的次数为：0次
|
因此，最终的g()函数就来了
1
2
3
4
5
6
7
8
9
|
public static int g() {
return f3() + 1;
}
|
举一反三
1、给一个函数，是3～19上是等概率的，写一个函数实现20～56上是等概率的？
1、根据3～19是等概率的，定义出0～1上等概率函数，即：
3～10范围返回0，12～19返回1，11重做
2、要做到17～56上等概率，那么可以先做到0～39的等概率，最后+17
那么就看看需要几个二进制位
0～1、0～3、0～7、0～15、0～31、0～63
需要6个字节来完成
即得到000000～111111等概率 即做到了0～39等概率返回一个（只要返回40～63的数，就重做）
如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！