算法学习Zero
Class01
1. 简单的位运算介绍
public class Demo01 {
public static void print(int num) {
for (int i = 31; i >= 0; i--) {
System.out.print((num & (1<<i)) == 0?'0':'1' );
}
System.out.println();
}
public static void main(String[] args) {
// int 整形 32 位 ；
//只要是int整形在计算机底层都是32位信息，让这个与1相与
// 如果为1 说明这以为信息为1 ，如果为0说明这一位为0，让它左移就可以了。
int num = 4 ;
print(num);
print(num<<2);
print(-1); // 输出的32位信息，全部取反，最后末尾加1，就是负几
int c = 5;
int d = -c ; // 相反数
int dd = ~c+1 ;
System.out.println(dd); //最高位取反为一，是负数，加一等于相反数
}
}
2. 选择排序
假定一个最小的数，是起始位置的，如果发现后面的数中有比这个数小的数，就交换位置，这时还没有结束，第一层循环还是在第一个位置，直到找到最小的一个数，将其交换位置，放到最开始的位置，依次类推，第二小的就放在后面。
/**
@about: 选择排序
*/
public class Demo02 {
public static void selectSort(int[] arr){
// 考虑边界条件
if(arr == null || arr.length < 2){
return ;
}
int n = arr.length;
for(int i = 0; i < n ; i++){
int minValueIndex = i ;
for(int j = i+1 ; j < n; j++){
minValueIndex = arr[j] < arr[minValueIndex]?j:minValueIndex ;
}
swap(arr,i,minValueIndex);
}
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void swap(int[] arr, int i ,int j ){
int tmp = arr[j] ;
arr[j] = arr[i] ;
arr[i] = tmp ;
}
public static void main(String[] args){
int[] arr = {5,1,2,6,4,8,6,4,7,15} ;
printArray(arr);
selectSort(arr);
printArray(arr);
}
}
3. 冒泡排序
//每一趟只能确定将一个数归位，第一次将末位上的数归位，第二次倒数第二，直到结束，最大的数放到最后面。第一趟最后一个数有了就可以不用在排，所以外层循环用n-1。
public static void bubbleSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
//0~ n-1
//0~ n-2
//0~ n-3
//0~ end
int n = arr.length;
for(int end = n-1 ;end >= 0; end--){
for(int second = 1; second <= end; second++ ){
if(arr[second-1] > arr[second]){
swap(arr,second,second-1) ;
}
}
}
}
//冒泡排序的关键步骤，其他的和上面的排序是一样的。4. 插入排序
举例 ：
数组在0-0范围内，是有序的，
0-1范围内，如果 1位置上的数小于0位置上的数，将他们两个互换
0-2范围内，如果2位置上的数小于1位置上的数，互换，如果1位置上的数比0位置的数还小，继续互换。
0-3范围内，如果3位置上的数小于2位置上的数，这两个数互换位置，如果2位置上新换的数比1位置上的数小，继续换位置，知道不小于前一个数为止
0-4范围内，如果4位置上的数大于或者等于3位置上的数，结束，这一范围不用动，继续下一范围的数0-5
…….
0 - end（arr.length)
//其余部分都是一样的，插入排序的实现代码
//while 循环里面是终止条件，分别是打0位置或者后面的数大于前面的数了
public static void insertSort(int[] arr){
int n = arr.length ;
for(int end = 1; end < n; end++){
int newNumIndex = end ;
while(newNumIndex - 1 >= 0 && arr[newNumIndex-1] > arr[newNumIndex]){
swap(arr,newNumIndex,newNumIndex-1);
newNumIndex-- ;
}
}
}// 也可以这样写 ， 用两个for循环
public static void insertSort2(int[] arr){
int n = arr.length ;
for(int end = 1; end < n ; end++){
for(int pre= end ; pre-1 >=0 && arr[pre-1] > arr[pre] ; pre-- ){
swap(arr,pre-1,pre);
}
}
}Class02
数据结构，前缀和，对数器
基本数据结构 ： 数组 ，便于寻址，不便于增删数据
链表，不便于寻址，便于增删数据
1. 前缀数组
假设有一个数组arr，频繁的查询arr中某一段的累加和，可以利用前缀和，让查询变得更便利和快捷。
// 就是让前n个数的和相加，分别为左边界和有边界。
// 需要分开判断左右边界的值。
public class Demo01 {
public static class RangeSum2 {
private int[] preSum;
public RangeSum2(int[] arr) {
int n = arr.length;
preSum = new int[n];
preSum[0] = arr[0];
for (int i = 1; i < n; i++) {
preSum[i] = preSum[i - 1] + arr[i];
}
}
public int rangesum(int l, int r) {
return l == 0 ? preSum[r] : preSum[r] - preSum[l - 1];
}
}
// 方法的调用
public static void main(String[] args) {
int[] arr = {1, 56, 4, 6, 48, 12, 56};
RangeSum2 rs = new RangeSum2(arr);
int res = rs.rangesum(1, 5);
System.out.println(res);
}
}
2. 创建等概率数
例题：1-5 的随机数怎么得到1-7的等概率的函数
// 生成的 1-5范围的数
public static int f1(){
return (int)(Math.random()*5) + 1 ;
}
// 随机机制只能返回1 ，等概率返回0和1
public static int f2(){
int ans = 0 ;
do{
ans = f1() ;
}while(ans == 3) ;
return ans < 3 ? 0 : 1 ;
}
// 用到了位运算 ， 看需要几个二进制位 ；
// 得到000~111 概率 即做到了0-7的等概率返回
public static int f3(){
return (f2()<<2) + (f2()<<1) + (f2() << 0) ;
}
// 0~6等概率返回
public static int f4(){
int ans = 0;
do{
ans = f3();
}while(ans == 7);
return ans ;
}
// 得到1-7等概率的函数
public static int g(){
return f4()+1 ;
}
// 以上是等概率返回 1-7 的方法
// 下面的是等概率返回0和1那一章节的
//只能知道，x会以固定概率返回0和1 ，但是x的内容，你看不到
public static int x(){
return Math.random() < 0.84 ? 0 : 1 ;
}
// 等概率返回0 和 1 , 第一次ans = x（）， 如果第一次与第二次while里面的一样，重新做，此时0和1返回的结果是等概率的。
public static int y(){
int ans = 0 ;
do {
ans = x() ;
}while(ans == x()) ;
return ans ;
}
}3. 对数器，可以用来验证排序等结果是否正确。
// 返回一个数组arr , arr长度[0 , maxLen-1], arr中的每个值[0 , maxValue-1]
public static int[] lenRandomValueRandom(int maxLen, int maxValue){
int len = (int)(Math.random()*maxLen) ;
int[] ans = new int[len] ;
for (int i = 0; i < len; i++){
ans[i] = (int)(Math.random() * maxValue) ;
}
return ans ;
}
// 复制数组
public static int[] copyArray(int[] arr){
int[] ans = new int[arr.length] ;
for(int i = 0 ; i < arr.length; i++){
ans[i] = arr[i] ;
}
return ans ;
}
//判断是否是排序的数组，前提是arr1 和 arr2 一定等长 。
public static boolean isSorted(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 ;
}
max = Math.max(max, arr[i]) ;
}
return true ;
}
public static void main(String[] args){
int len = 10 ;
int maxValue = 1000 ;
int testTimes = 10000 ;
for(int i = 0 ; i < testTimes; i++){
int[] arr1 = lenRandomValueRandom(len,maxValue) ;
int[] arr2 = copyArray(arr1) ;
selectSort(arr1);
// insertSort2(arr1);
if(!isSorted(arr1)){
for (int j = 0 ; j < arr2.length ;j++){
System.out.print(arr2[j] + " ");
}
System.out.println();
System.out.println("选择排序出错了");
break;
}
}
}
