# 算法新手班
# 一.位运算,算法是什么,简单排序
# 1.阶乘题:给定一个参数N，
返回： 1! + 2! + 3! + 4! + … + N! 的结果
暴力解法:每一个阶乘,然后相加到一起.
算法:后一个数其中有些在上一个阶乘中已经算过了,不需要再重新算,只需要前一个结果加上自己即可.
# 2.选择排序:选择就是一遍遍选出来最小的放到前面.O(n²)
一遍一遍比,选一个最小的,排到前面,然后从这个数下一个数一个个选出来.
0~N-1选一个最小的和0位置换
1~N-1选一个最小的和1位置换
2~N-1选一个最小的和2位置换
......
一直到最后一个了,就排完了
选择排序是个不稳定的排序算法,例如arr=[5,5,2],第一个5会和2交换,则第一个5和第二个5相对顺序改变,所以不稳定.
# 3.冒泡排序:第一个数开始,一点点往后冒,两个两个比,最大的排到最后.O(n²)
0~N-1,一个个比,最大的冒到最后.
0~N-2,一个个比,最大的冒到最后.
......
0~1,,最大的冒到最后.就排完了.
冒泡排序是稳定的排序算法,在冒泡排序中，只比较相邻的两个元素，如果它们的顺序错误，再进行交换。这个过程不会导致跨越多个元素的移动，因此在排序过程中，相等的元素不会改变它们在数组中的相对顺序。
# 4.插入排序:从第一个数开始,后面出现一个新数,往前插,插到比他小或者相等的后面.循环操作O(n²)
0位置先来一个数,有序了,
0~1出现一个新数,从后往前,插到比他小或者相等的后面
0~2出现一个新数,从后往前,插到比他小或者相等的后面
.....
0~N-1,出现一个新数,从后往前,插到比他小或者相等的后面,就排完了
**插入排序是一种稳定的排序算法。**这意味着在排序过程中，相等元素的相对位置不会发生变化。
# 二.数据结构的大分类、介绍前缀和与对数器
# 前缀:
有个需求,一个数组,返回其中某一段的和.查询频率极高.
a.前缀和:后面位置的前缀和减去前面位置的前缀和,即L...R位置的和.
b.二维数组:先遍历一遍,然后L...R直接取二维数组取数,极快,如果查询非常频繁,可以用这种.
# Math.random() -> double -> [0,1) 等概率
# 1.任意的x,x属于[0,1),[0,x)范围上的数出现概率由原来的x调整为x².
出现一次x的概率为Math.random()<x,两次都在这个范围,也就是最大值在这个范围.也就是x²,所以是math.max(Math.random(),Math.random());
# 2.从1-5随机到1-7随机
1-5随机是个黑盒.随机返回1-5.
我们让他对半分,12返回0,45返回1,3就重新做.让他只能返回0,1,
二进制数,1-7 ,三位足够表示,000~111等概率,_ _ _,每一位都是随机的,也就是0~7等概率返回一个,
假设f2()是返回0,1等概率的,那么 ((f2() << 2) + (f2() << 1) + f2() 即可.然后,遇到7让他重做,即可0~6等概率.然后再结果+1,即1~7等概率.
假如要17-56等概率呢?一样先得到0~(56-17)等概率,看看需要几个二进制位,然后结果+17即可.
# 3.01不等概率随机到01等概率随机
01固定概率,但是不是等概率.0的概率是P,1的概率是1-P
随机2次,00,11不要,10或01要,P*(1-P),
假设x()是不等概率方法.
第一次等于第二次,就重做,
int ans = 0;
do{
ans = x();
}while(ans == x());
return ans;
# 4.对数据
随机生成最大的长度,最大的数范围内的大小的数组.用于验证算法.
# 5.快排-荷兰国旗问题
5.1让一个数组小于等于某个值放左边,大于某个值放右边.
- 设置一个小于区,右边界为-1.
- 从L~R,为0~N-1,设置一个index,未当前遍历数的指针.
- 挨个遍历,
- 如果他小于等于,
- 当前数和小于区右边下一个数换
- 小于区右扩
- 当前数跳下一个
- 如果他大于
- 直接跳下一个
- 如果他小于等于,
5.2让一个数组小于某个值放左边,大于某个值放右边,等于的放中间
设置一个小于区,右边界为-1.设置一个大于区,左边界为N
从L~R,为0~N-1,设置一个index,未当前遍历数的指针.
挨个遍历,
- 如果他小于
- 当前数和小于区右边下一个数换
- 小于区右扩
- 当前数跳下一个
- 如果他等于
- 当前数直接跳下一个
- 如果他大于
- 当前数和大于区前一个交换
- 大于区左扩
- 当前数停在原地
/** * 给定一个数组,和范围,给小于R位置的数放左边,等于的放中间,大于的放右边.排好后,返回等于区的边界, * @param arr 数组 * @param L 左边界 * @param R 右边界 * @return */ public static int[] netherlandsFlag(int[] arr,int L,int R){ if (L > R){ return new int[]{-1,-1}; } if (L == R){ return new int[]{L,R}; } //小于区右边界 int less = -1; //大于区左边界 int more = R; //当前数 int index = 0; //因为大于区中是大于的,所以遍历到他左边界足够了 while (index < more){ if (arr[index] < arr[R]){ swap(arr,less+1,index); less++; index++; //swap(arr,++less,index++); }else if (arr[index] == arr[R]){ index++; }else{ swap(arr,more-1,index); more--; //swap(arr,--more,index); } //把最后一个数换到等于区 swap(arr,R,more); } return new int[]{less+1,more}; }- 如果他小于