新手入门篇-数据结构、前缀和、对数器-灵析社区

数据结构

算法基本上是数组和链表的变种，数组和链表是所有算法的基石。

数组：内存分配是连续的、访问速度快，插入和删除速度慢，因为数组要移动位置。

链表：内存分配是不连续的，插入和删除速度快，访问速度慢，因为需要遍历。

前缀和

对于一个数组，求从L到R位置的和

一般大家都会这么做，从L遍历到R，累加求和。对于数量规模比较大的时候，这种普通求解方法就显得效率有些低下了，可以通过前缀和。

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;
        }
        
        // 普通求解
        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[] 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];
        }

    }

    // 二维数组求解
    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) {
            return arr[L][R];
        }
    }

}

对数器

验证自己写的算法对不对，可以通过对数器进行验证，验证规则可以自定义。

随机等概率

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 + "的概率为：" + (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("小于5的概率为：" + (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 + "这个数，出现了 " + counts[i] + " 次");
        }

        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 + "这个数，出现了 " + counts[i] + " 次");
        }

    }

    // 返回一个[0,1)的小数
    // 任意的x，x属于[0,1)，【0,x)范围上的数出现概率由原来的x调整成x平方
    public static double xToXPower2() {
        return Math.max(Math.random(), Math.random());
    }

    public static double xToXPower22() {
        return Math.min(Math.random(), Math.random());
    }

    // lib里的，不能改
    public static int f1() {
        return (int) (Math.random() * 5) + 1;
    }

    // 随机机制，只能用f1，
    // 等概率返回0和1
    public static int f2() {
        int ans = 0;
        do {
            ans = f1();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

    // 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个
    public static int f3() {
        return (f2() << 2) + (f2() << 1) + f2();
    }

    // 0 ~ 6等概率返回一个
    public static int f4() {
        int ans = 0;
        do {
            ans = f3();
        } while (ans == 7);
        return ans;
    }

    public static int g() {
        return f4() + 1;
    }

    // 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
    public static int x() {
        return Math.random() < 0.84 ? 0 : 1;
    }

    // 等概率返回0和1
    public static int y() {
        int ans = 0;
        do {
            ans = x();
        } while (ans == x());
        return ans;
    }
}

校验算法是否正确

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++) { // 0 ~ i 做到有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    // 返回一个数组arr，arr长度[0,maxLen-1],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和arr2一定等长
    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("选择排序错了！");
                break;
            }
        }
    }

}