文章目录
-
- 数据结构与算法（一）
-
- 1 位运算、算法是什么、简单排序
-
- 1.1 实现打印一个整数的二进制
- 1.2 给定一个参数N，返回1!+2!+3!+4!+…+N!的结果
- 1.3 简单排序算法
- 2 数据结构大分类、前缀和、对数器
-
- 2.1 实现前缀和数组
- 2.2 如何用1~5的随机函数加工出1~7的随机函数
- 2.3 如何把不等概率随机函数变成等概率随机函数
- 3 二分法、时间复杂度、动态数组、哈希表、有序表
-
- 3.1 有序数组中找到 num
- 3.2 有序数组中找到>=num最左的位置
- 3.3 有序数组中找打
- 3.4 局部最小问题
- 3.5 哈希表、有序表
- 4 链表相关的简单面试题
-
- 4.1 反转单链表
- 4.2 反转双链表
- 4.3 用单链表实现队列
- 4.4 用单链表实现栈
- 4.5 用双链表实现双端队列
- 4.6 K个一组翻转链表
- 4.7 两个链表相加问题
- 4.8 两个有序链表的合并
- 5 位图
-
- 5.1 位图
- 5.2 位运算实现加减乘除
- 6 比较器、优先队列、二叉树
-
- 6.1 合并多个有序链表
- 6.2 判断两棵树是否结构相同
- 6.3 判断一棵树是否是镜面树
- 6.4 返回一棵树的最大深度
- 6.5 用先序数组和中序数组重建一棵树
- 6.6 二叉树先序、中序、后序遍历的代码实现、介绍递归序
- 7 二叉树
-
- 7.1 二叉树按层遍历并收集节点
- 7.2 判断是否是平衡搜索二叉树
- 7.3 在二叉树上能否组成路径和
- 7.4 在二叉树上收集所有达标的路径和
- 7.5 判断二叉树是否是搜索二叉树
- 8 归并排序和快速排序
-
- 8.1 归并排序的递归实现和非递归实现
- 8.2 快速排序的递归实现和非递归实现
数据结构与算法（一）
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*n
long 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
// 方法一：每次遍历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 1
for (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 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
目录 通用命令是什么 SET & GET keys EXISTS DEL EXPIRE TTL redis 的过期策略 定时器策略 基于优先级队列定时器 基于时间轮的定时器 TYPE 通过 redis 客户端和 redis 服务器交互。 所以需要使用 …
