“This is the 13th day of my participation in the Gengwen Challenge. For more details, see” Gengwen Challenge “.
The last is the first data structure and algorithm novice entry, this is data structure and algorithm novice entry second, come to experience the charm of the algorithm!
The data structure
Algorithms are basically variations on arrays and lists, which are the cornerstones of all algorithms.
Arrays: Memory allocation is sequential, access is fast, and insertions and deletions are slow because arrays are moved.
Linked lists: Memory allocation is discontinuous, insertions and deletions are fast, and access is slow because traversal is required.
The prefix and
For an array, sum the positions from L to R
That’s what you do in general, you go from L to R, you add up. For large numbers, this common solution is a little inefficient, you can use the prefix sum.
public class Code01_PreSum {
public static void main(String[] args) {
int[] arr = {1.2.4.5.7};
RangeSum1 rangeSum1 = new RangeSum1(arr);
System.out.println(rangeSum1.rangeSum(2.4));
RangeSum2 rangeSum2 = new RangeSum2(arr);
System.out.println(rangeSum2.rangeSum(2.4));
RangeSum3 rangeSum3 = new RangeSum3(arr);
System.out.println(rangeSum3.rangeSum(2.4));
}
public static class RangeSum1 {
private int[] arr;
public RangeSum1(int[] array) {
this.arr = array;
}
// Normal solution
public int rangeSum(int L, int R) {
int sum = 0;
for (int i = L; i <= R; i++) {
sum += arr[i];
}
returnsum; }}// One dimensional array solution
public static class RangeSum2 {
private int[] preSum;
public RangeSum2(int[] arr) {
preSum = new int[arr.length];
preSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
preSum[i] = preSum[i - 1] + arr[i]; }}public int rangeSum(int L, int R) {
return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1]; }}// Solve for a two-dimensional array
public static class RangeSum3 {
private int[][] arr;
public RangeSum3(int[] array) {
arr = new int[array.length][array.length];
arr[0] [0] = array[0];
for (int i = 1; i < array.length; i++) {
for (int j = 1; j < arr.length; j++) {
if (i > j) {
continue;
}
arr[i][j] = (i == j) ? array[i] : arr[i][j - 1] + array[j]; }}}public int rangeSum(int L, int R) {
returnarr[L][R]; }}}Copy the codeLogarithmic detector
Verify that the algorithm you write is correct, you can verify through the logizer, validation rules can be customized.
Random equal probability
public class Code02_RandToRand {
public static void main(String[] args) {
int testTimes = 10000000;
int count = 0;
double x = 0.1;
for (int i = 0; i < testTimes; i++) {
if (Math.random() < x) {
count++;
}
}
System.out.println("x=" + x + The probability of "is:" + (double) count / (double) testTimes);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() * 8 < 5) {
count++;
}
}
System.out.println("The probability less than 5 is:" + (double) count / (double) testTimes);
System.out.println((double) 5 / (double) 8);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
int K = 9;
/ / [0, k) - > [0, 8]
int[] counts = new int[9];
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 + "This number, it appears." + counts[i] + "Time");
}
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
count = 0;
x = 0.8;
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));
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
count = 0;
x = 0.8;
for (int i = 0; i < testTimes; i++) {
if (xToXPower22() < x) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println((double) 1 - Math.pow((double) 1 - x, 2));
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
count = 0;
for (int i = 0; i < testTimes; i++) {
if (f2() == 1) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
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 + "This number, it appears." + counts[i] + "Time"); }}// return a decimal of [0,1]
// For any number in the range [0,1), [0, x), the probability of occurrence is adjusted from the original x to x squared
public static double xToXPower2(a) {
return Math.max(Math.random(), Math.random());
}
public static double xToXPower22(a) {
return Math.min(Math.random(), Math.random());
}
// in lib, cannot change
public static int f1(a) {
return (int) (Math.random() * 5) + 1;
}
// Random mechanics, f1 only,
// Return 0 and 1 with equal probability
public static int f2(a) {
int ans = 0;
do {
ans = f1();
} while (ans == 3);
return ans < 3 ? 0 : 1;
}
// Get 000 ~ 111 do equal probability 0 ~ 7 equal probability return one
public static int f3(a) {
return (f2() << 2) + (f2() << 1) + f2();
}
// Return one with equal probability from 0 to 6
public static int f4(a) {
int ans = 0;
do {
ans = f3();
} while (ans == 7);
return ans;
}
public static int g(a) {
return f4() + 1;
}
// You can only know that x returns 0 and 1 with a fixed probability, but you can't see the contents of x!
public static int x(a) {
return Math.random() < 0.84 ? 0 : 1;
}
// Return 0 and 1 with equal probability
public static int y(a) {
int ans = 0;
do {
ans = x();
} while (ans == x());
returnans; }}Copy the codeCheck whether the algorithm is correct
public class Code03_Comp {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr, i, minIndex); }}public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) { // Order 0 ~ I
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1); }}}// Return an array arr with length [0,maxLen-1] and each value in arr [0,maxValue-1]
public static int[] lenRandomValueRandom(int maxLen, int maxValue) {
int len = (int) (Math.random() * maxLen);
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
int ans = (int) (Math.random() * maxValue);
arr[i] = ans;
}
return arr;
}
public static int[] copyArray(int[] arr) {
int[] ans = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
ans[i] = arr[i];
}
return ans;
}
// Arr1 and ARR2 must be the same length
public static boolean isSorted(int[] arr) {
if (arr.length < 2) {
return true;
}
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max > arr[i]) {
return false;
}
max = Math.max(max, arr[i]);
}
return true;
}
public static void main(String[] args) {
int maxLen = 5;
int maxValue = 1000;
int testTimes = 10000;
for (int i = 0; i < testTimes; i++) {
int[] arr1 = lenRandomValueRandom(maxLen, maxValue);
int[] tmp = copyArray(arr1);
selectionSort(arr1);
if(! isSorted(arr1)) {for (int j = 0; j < tmp.length; j++) {
System.out.print(tmp[j] + "");
}
System.out.println();
System.out.println("The selection is wrong!");
break; }}}}Copy the codeWelcome to follow the public account (MarkZoe) to learn from each other and communicate with each other.