Skip to content

Commit aec9feb

Browse files
algorithmzuoalgorithmzuo
committed
add class 02
1 parent c9ca690 commit aec9feb

7 files changed

Lines changed: 448 additions & 1 deletion

src/class02/Code05_PreSum.java renamed to src/class02/Code01_PreSum.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package class02;
22

3-
public class Code05_PreSum {
3+
public class Code01_PreSum {
44

55
public static class RangeSum1 {
66

‎src/class02/Code02_RandToRand.java‎

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
package class02;
2+
3+
public class Code02_RandToRand {
4+
5+
// 此函数只能用，不能修改
6+
// 等概率返回1~5
7+
public static int f() {
8+
return (int) (Math.random() * 5) + 1;
9+
}
10+
11+
// 等概率得到0和1
12+
public static int a() {
13+
int ans = 0;
14+
do {
15+
ans = f();
16+
} while (ans == 3);
17+
return ans < 3 ? 0 : 1;
18+
}
19+
20+
// 等概率返回0~6
21+
public static int b() {
22+
int ans = 0;
23+
do {
24+
ans = (a() << 2) + (a() << 1) + a();
25+
} while (ans == 7);
26+
return ans;
27+
}
28+
29+
// 等概率返回1~7
30+
public static int c() {
31+
return b() + 1;
32+
}
33+
34+
// 这个结构是唯一的随机机制
35+
// 你只能初始化并使用，不可修改
36+
public static class RandomBox {
37+
private final int min;
38+
private final int max;
39+
40+
// 初始化时请一定不要让mi==ma
41+
public RandomBox(int mi, int ma) {
42+
min = mi;
43+
max = ma;
44+
}
45+
46+
// 13 ~ 17
47+
// 13 + [0,4]
48+
public int random() {
49+
return min + (int) (Math.random() * (max - min + 1));
50+
}
51+
52+
public int min() {
53+
return min;
54+
}
55+
56+
public int max() {
57+
return max;
58+
}
59+
}
60+
61+
// 利用条件RandomBox，如何等概率返回0和1
62+
public static int rand01(RandomBox randomBox) {
63+
int min = randomBox.min();
64+
int max = randomBox.max();
65+
// min ~ max
66+
int size = max - min + 1;
67+
// size是不是奇数，odd 奇数
68+
boolean odd = (size & 1) != 0;
69+
int mid = size / 2;
70+
int ans = 0;
71+
do {
72+
ans = randomBox.random() - min;
73+
} while (odd && ans == mid);
74+
return ans < mid ? 0 : 1;
75+
}
76+
77+
// 给你一个RandomBox，这是唯一能借助的随机机制
78+
// 等概率返回from~to范围上任何一个数
79+
// 要求from<=to
80+
public static int random(RandomBox randomBox, int from, int to) {
81+
if (from == to) {
82+
return from;
83+
}
84+
// 3 ~ 9
85+
// 0 ~ 6
86+
// 0 ~ range
87+
int range = to - from;
88+
int num = 1;
89+
// 求0～range需要几个2进制位
90+
while ((1 << num) - 1 < range) {
91+
num++;
92+
}
93+
94+
// 我们一共需要num位
95+
// 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
96+
int ans = 0;
97+
do {
98+
ans = 0;
99+
for (int i = 0; i < num; i++) {
100+
ans |= (rand01(randomBox) << i);
101+
}
102+
} while (ans > range);
103+
return ans + from;
104+
}
105+
106+
public static void main(String[] args) {
107+
108+
int[] count = new int[8]; // 0 1 2 .. 7
109+
int testTime = 10000000;
110+
for (int i = 0; i < testTime; i++) {
111+
int ans = c();
112+
count[ans]++;
113+
}
114+
115+
for (int i = 0; i < 8; i++) {
116+
System.out.println(i + " : " + count[i]);
117+
}
118+
119+
// RandomBox randomBox = new RandomBox(3, 9);
120+
// int from = 17;
121+
// int to = 29;
122+
// int[] ans = new int[to + 1];
123+
// int testTime1 = 1000000;
124+
// for (int i = 0; i < testTime1; i++) {
125+
// ans[random(randomBox, from, to)]++;
126+
// }
127+
// for (int i = 0; i < ans.length; i++) {
128+
// System.out.println(ans[i]);
129+
// }
130+
// System.out.println("==========");
131+
132+
}
133+
134+
}

‎src/class02/Code03_EqualProbabilityRandom.java‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package class02;
2+
3+
public class Code03_EqualProbabilityRandom {
4+
5+
// 内部内容不可见
6+
public static int f() {
7+
return Math.random() < 0.8 ? 0 : 1;
8+
}
9+
10+
// 等概率返回0和1
11+
public static int g() {
12+
int first = 0;
13+
do {
14+
first = f(); // 0 1
15+
} while (first == f());
16+
return first;
17+
}
18+
19+
// 这个结构是唯一的随机机制
20+
// 你只能初始化并使用，不可修改
21+
public static class RandomBox {
22+
private final double p;
23+
24+
// 初始化时请一定满足：0 < zeroP < 1
25+
public RandomBox(double zeroP) {
26+
p = zeroP;
27+
}
28+
29+
public int random() {
30+
return Math.random() < p ? 0 : 1;
31+
}
32+
33+
}
34+
35+
// 底层依赖一个以p概率返回0，以1-p概率返回1的随机函数rand01p
36+
// 如何加工出等概率返回0和1的函数
37+
public static int rand01(RandomBox randomBox) {
38+
int num;
39+
do {
40+
num = randomBox.random();
41+
} while (num == randomBox.random());
42+
return num;
43+
}
44+
45+
public static void main(String[] args) {
46+
int[] count = new int[2];// 0 1
47+
for (int i = 0; i < 1000000; i++) {
48+
int ans = g();
49+
count[ans]++;
50+
}
51+
System.out.println(count[0] + " , " + count[1]);
52+
53+
// double zeroP = 0.88;
54+
// RandomBox randomBox = new RandomBox(zeroP);
55+
//
56+
// int testTime = 10000000;
57+
// int count = 0;
58+
// for (int i = 0; i < testTime; i++) {
59+
// if (rand01(randomBox) == 0) {
60+
// count++;
61+
// }
62+
// }
63+
// System.out.println((double) count / (double) testTime);
64+
65+
}
66+
67+
}

‎src/class02/Code04_BSExist.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package class02;
2+
3+
import java.util.Arrays;
4+
5+
public class Code04_BSExist {
6+
7+
public static boolean exist(int[] sortedArr, int num) {
8+
if (sortedArr == null || sortedArr.length == 0) {
9+
return false;
10+
}
11+
int L = 0;
12+
int R = sortedArr.length - 1;
13+
int mid = 0;
14+
// L..R
15+
while (L < R) { // L..R 至少两个数的时候
16+
mid = L + ((R - L) >> 1);
17+
if (sortedArr[mid] == num) {
18+
return true;
19+
} else if (sortedArr[mid] > num) {
20+
R = mid - 1;
21+
} else {
22+
L = mid + 1;
23+
}
24+
}
25+
return sortedArr[L] == num;
26+
}
27+
28+
// for test
29+
public static boolean test(int[] sortedArr, int num) {
30+
for(int cur : sortedArr) {
31+
if(cur == num) {
32+
return true;
33+
}
34+
}
35+
return false;
36+
}
37+
38+
39+
// for test
40+
public static int[] generateRandomArray(int maxSize, int maxValue) {
41+
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
42+
for (int i = 0; i < arr.length; i++) {
43+
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
44+
}
45+
return arr;
46+
}
47+
48+
public static void main(String[] args) {
49+
int testTime = 500000;
50+
int maxSize = 10;
51+
int maxValue = 100;
52+
boolean succeed = true;
53+
for (int i = 0; i < testTime; i++) {
54+
int[] arr = generateRandomArray(maxSize, maxValue);
55+
Arrays.sort(arr);
56+
int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
57+
if (test(arr, value) != exist(arr, value)) {
58+
succeed = false;
59+
break;
60+
}
61+
}
62+
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
63+
}
64+
65+
}

‎src/class02/Code05_BSNearLeft.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package class02;
2+
3+
import java.util.Arrays;
4+
5+
public class Code05_BSNearLeft {
6+
7+
// 在arr上，找满足>=value的最左位置
8+
public static int nearestIndex(int[] arr, int value) {
9+
int L = 0;
10+
int R = arr.length - 1;
11+
int index = -1; // 记录最左的对号
12+
while (L <= R) { // 至少一个数的时候
13+
int mid = L + ((R - L) >> 1);
14+
if (arr[mid] >= value) {
15+
index = mid;
16+
R = mid - 1;
17+
} else {
18+
L = mid + 1;
19+
}
20+
}
21+
return index;
22+
}
23+
24+
// for test
25+
public static int test(int[] arr, int value) {
26+
for (int i = 0; i < arr.length; i++) {
27+
if (arr[i] >= value) {
28+
return i;
29+
}
30+
}
31+
return -1;
32+
}
33+
34+
// for test
35+
public static int[] generateRandomArray(int maxSize, int maxValue) {
36+
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
37+
for (int i = 0; i < arr.length; i++) {
38+
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
39+
}
40+
return arr;
41+
}
42+
43+
// for test
44+
public static void printArray(int[] arr) {
45+
if (arr == null) {
46+
return;
47+
}
48+
for (int i = 0; i < arr.length; i++) {
49+
System.out.print(arr[i] + " ");
50+
}
51+
System.out.println();
52+
}
53+
54+
public static void main(String[] args) {
55+
int testTime = 500000;
56+
int maxSize = 10;
57+
int maxValue = 100;
58+
boolean succeed = true;
59+
for (int i = 0; i < testTime; i++) {
60+
int[] arr = generateRandomArray(maxSize, maxValue);
61+
Arrays.sort(arr);
62+
int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
63+
if (test(arr, value) != nearestIndex(arr, value)) {
64+
printArray(arr);
65+
System.out.println(value);
66+
System.out.println(test(arr, value));
67+
System.out.println(nearestIndex(arr, value));
68+
succeed = false;
69+
break;
70+
}
71+
}
72+
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
73+
}
74+
75+
}

0 commit comments

Comments
 (0)