note/algorithm/3、数据结构.md

## 数据结构

* 数据结构是存储、组织数据的方式
* 精心选择的数据结构可以带来更高的运行或者存储效率
* 数据结构是很多算法得以进行的载体

### 最基本的数据结构

* 数组 按照下标寻址的时间复杂度为O(1)，不便于增删数据
* 链表 便于增删数据，不便于寻址

### 前缀和数组

可以考虑使用二维数组保存前缀和，避免每次做减法。

```Java
private static int preSum(int[] arr, int left,int right) {
    int length = arr.length;
    int[] preSum = new int[length];
    for (int i = 0; i < length; i++) {
        if (i == 0) {
            preSum[i] = arr[i];
        } else {
            preSum[i] = preSum[i - 1] + arr[i];
        }
    }
    return left == 0 ? preSum[right] : preSum[right] - preSum[left];
}
```

从1-5随机到1-7随机
从a-b随机到c-d随机
01不等概率随机到01等概率随机

```Java
    private static int f1(){
        return (int) (Math.random() * 5) + 1;
    }

    private static int f2(){
        int ans = 0;
        do {
            ans = f1();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

    // 000 - 111 等概率
    private static int f3(){
        return f2() << 2 + f2() << 1 + f2();
    }
```

固定概率方法等概率返回0或者1

```Java
// 固定概率返回0或者1
private static int x(){
    return Math.random() < 0.84 ? 0 : 1;
}

// 等概率返回0或者1
private static int y() {
    int ans = 0;
    do {
        ans = x();
    } while (ans == x());
    return ans;
}
```

生成随机数组，判断排序结果

```Java
public static void main(String[] args) {
    int maxLen = 50;
    int maxValue = 3000;
    int times = 10000;
    for (int i = 0; i < times; i++) {
        int[] arr = randomArr(maxLen, maxValue);
        int[] tmp = copyArr(arr);
        //        selectionSort(arr);
        //        bubbleSort(arr);
        insertSort(arr);
        boolean result = validateArr(arr);
        if (!result) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(tmp[j] + " ");
            }
            System.out.println();
            System.out.println("排序结果错误");
            break;
        }
    }

}

private static int[] copyArr(int[] arr){
    int[] ans = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        ans[i] = arr[i];
    }
    return ans;
}

private static boolean validateArr(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;
        }
    }
    return true;
}
```

小和问题、逆序对、大于两倍问题
区间和leetcode327 可以用有序表、归并解决
荷兰国旗问题