数据结构与算法（一）

数据结构与算法（一）

1 位运算、算法是什么、简单排序

1.1 实现打印一个整数的二进制

public static void print(int num) {// int 32位，依次打印高位到低位(31 -> 0)的二进制值for (int i = 31; i >= 0; i--) {System.out.print((num & (1 << i)) == 0 ? "0" : "1");}System.out.println();
}42361845			=>		00000010100001100110001111110101
Integer.MAX_VALUE	=>		01111111111111111111111111111111
Integer.MIN_VALUE	=>		10000000000000000000000000000000

1.2 给定一个参数N，返回1!+2!+3!+4!+…+N!的结果

• 方法一：

public static long f1(int n) {long ans = 0;for (int i = 1; i <= n; i++) {ans += factorial(i);}return ans;
}public static long factorial(int n) {long ans = 1;for (int i = 1; i <= n; i++) {ans *= i;}return ans;
}

• 方法二：每次都基于上次计算结果进行计算 -> 更优

public static long f2(int n) {// 第1次：1! -> cur// 第2次: 2! = 1!*2 -> cur*2 -> cur// 第3次: 3! = 2!*3 -> cur*3 -> cur// ...// 第n次: n! = (n-1)!*n -> cur*nlong ans = 0;long cur = 1;for (int i = 1; i <= n; i++) {cur = cur * i;ans += cur;}return ans;
}

1.3 简单排序算法

• 选择排序：

// [1,len) -> find minValue -> 与 0 位置交换
// [2,len) -> find minValue -> 与 1 位置交换
// ...
// [i,len) -> find minValue -> 与 i - 1 位置交换
public static void selectSort(int[] arr) {if (arr == null || arr.length < 2) return;int len = arr.length;for (int i = 0; i < len; i++) {int minValueIndex = i;for (int j = i + 1; j < len; j++) {minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;}swap(arr, i, minValueIndex);}
}

• 冒泡排序：

// [0, len) -> 两两比较并交换 -> maxValue放到 len-1 位置
// [0, len-1) -> 两两比较并交换 -> maxValue放到 len-2 位置
// ...
// [0, len-i) -> 两两比较并交换 -> maxValue放到 len-i-1 位置
public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) return;int len = arr.length;for (int i = len - 1; i >= 0; i--) {for (int j = 1; j <= i; j++) {if (arr[j - 1] > arr[j]) {swap(arr, j - 1, j);}}}
}// 优化：
public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) return;int len = arr.length;for (int i = len - 1; i >= 0; i--) {boolean flag = false;for (int j = 1; j <= i; j++) {if (arr[j - 1] > arr[j]) {swap(arr, j - 1, j);flag = true;}}if (!flag) { // 如果没发生交换，说明已经有序，可以提前结束break;}}
}

• 插入排序：

// [0,0] -> 有序，仅一个数，显然有序
// [0,1] -> 有序 -> 从后往前两两比较并交换
// [0,2] -> 有序 -> 从后往前两两比较并交换
// ...
// [0,len-1] -> 有序 -> 从后往前两两比较并交换
public static void insertSort(int[] arr) {if (arr == null || arr.length < 2) return;int len = arr.length;for (int i = 1; i < len; i++) {int pre = i - 1;while (pre >= 0 && arr[pre] > arr[pre + 1]) {swap(arr, pre, pre + 1);pre--;}//			// 写法二：
//			for (int pre = i - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
//				swap(arr, pre, pre + 1);
//			}}
}

2 数据结构大分类、前缀和、对数器

• 内容：

  • 什么是数据结构，组成各种数据结构的最基本元件？

    • 数组、链表

  • 前缀和数组

  • 随机函数

  • 对数器的使用

2.1 实现前缀和数组

• 求一个数组 array 在给定区间 L 到 R 之间（[L,R]，L<=R）数据的和。

// 方法一：每次遍历L~R区间，进行累加求和
public static class RangeSum1 {private int[] arr;public RangeSum1(int[] array) {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[] array) {int N = array.length;preSum = new int[N];preSum[0] = array[0];for (int i = 1; i < N; i++) {preSum[i] = preSum[i - 1] + array[i];}}public int rangeSum(int L, int R) {return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];}
}

2.2 如何用1~5的随机函数加工出1~7的随机函数

// 此函数只能用，不能修改
// 等概率返回1~5
private static int f() {return (int) (Math.random() * 5) + 1;
}
// 等概率得到0和1
private static int f1() {int ans = 0;do {ans = f();} while (ans == 3);return ans < 3 ? 0 : 1;
}
// 等概率返回0~6
private static int f2() {int ans = 0;do {ans = (f1() << 2) + (f1() << 1) + f1();} while (ans == 7);return ans;
}
// 等概率返回1~7
public static int g() {return f2() + 1;
}public static void main(String[] args) {int testTimes = 10000000;int[] 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这个数，出现了 0 次
1这个数，出现了 1428402 次
2这个数，出现了 1427345 次
3这个数，出现了 1428995 次
4这个数，出现了 1428654 次
5这个数，出现了 1428688 次
6这个数，出现了 1428432 次
7这个数，出现了 1429484 次

2.3 如何把不等概率随机函数变成等概率随机函数

// 你只能知道，f会以固定概率返回0和1，但是x的内容，你看不到！
public static int f() {return Math.random() < 0.84 ? 0 : 1;
}// 等概率返回0和1
public static int g() {int first = 0;do {first = f(); // 0 1} while (first == f());return first;
}public static void main(String[] args) {int[] count = new int[2];// 0 1for (int i = 0; i < 1000000; i++) {int ans = g();count[ans]++;}System.out.println(count[0] + " , " + count[1]);
}

3 二分法、时间复杂度、动态数组、哈希表、有序表

• 内容：
  • 二分法
  • 使用二分法解决不同的题目
  • 时间复杂度
  • 动态数组
  • 按值传递、按引用传递
  • 哈希表
  • 有序表

3.1 有序数组中找到 num

// arr保证有序
public boolean find(int[] arr, int num) {if (arr == null || arr.length == 0) return false;int l = 0, r = arr.length - 1;while <