北京城建亚泰建设集团有限公司网站,wordpress 小工具调用,wordpress商店会员管理,百度一下你就知道官网网页文章目录 数据结构与算法（一）1 位运算、算法是什么、简单排序1.1 实现打印一个整数的二进制1.2 给定一个参数N，返回1!+2!+3!+4!+...+N!的结果1.3 简单排序算法2 数据结构大分类、前缀和、对数器2.1 实现前缀和数组2.2 如何用1\~5的随机函数加工出1\~7的随机函数2.3 如何把不… 文章目录 数据结构与算法（一）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 有序数组中找到 num3.2 有序数组中找到=num最左的位置3.3 有序数组中找打=num最右的位置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 = 100000000000000000000000000000001.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
