Algorithm-Day01

前言

如果想成为别人口中的大佬，那就无时无刻的卷，追随着大佬的步伐......

基础知识

• 位运算概念: << , >>(带符号右移,用符号位填补), >>>(无符号右移,用零填补)等各种运算符
• 二进制的原码、反码、补码

• 负数是去掉符号位，其余反码+1。(方便底层二进制实现加减乘除用于同一套逻辑)：例如取一个数值的相反数，正负数取反都可以用

• int类型的正负数表示:二进制首位是符号位不带入计算
• 相反数: (~c + 1 ) 等同于 -c

• 负数的最小值相反数是本身
• 零相反数是零
• 如果取到负数最小值,那么数据类型应该设置为Long类型，而不是Int类型

练习

打印一个int类型数值的二进制

public class IntToBinary{
public static void print(int num){
for(int i = 31; i >= 0; i--){
// 底层int 类型的数组是32位二进制构成
//循环32此，判断 每一位数据是否位1
//与 1 进行 & 运算即可
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
}
public static void main(String[] args) {
int num = 13216516;
System.out.println(num);
print(num);
}
}
//扩展：其余类型打印二进制，同理

阶乘的计算：累加一个数值从1到N的阶乘总和

public class SumOfFactorial{
public static long f1(int N){
int curNum = 1; //用于保存阶乘数值
int ans = 0;//用于保存累加总和
for(var i = 1; i <= N; i++){
curNum *= i;
ans += curNum
}
return ans
}
}

经典排序

选择排序

// 实现原理：一个变量保存起始索引，与剩余元素进行比较，
// 选出最小（或最大）的一个元素，变量保存索引，进行交换
public class Code03_Sort {
public static void SelectSort(int[] arr) {
//如果数组没有 或者 数组长度为空 直接返回
if(arr ==null || arr.length == 0) return;

for(var index = 0; index < arr.length; index++){
//MinIndex用来保存最终比较出来的索引
int MinIndex = index;//默认最小值位置是起始位置
for (int j = index + 1; j < arr.length; j++) {
MinIndex = arr[j] < arr[MinIndex] ? j : MinIndex;
}
//进行索引交换
Swap(arr,index,MinIndex);
}
}
public static void Swap(int[] arr, int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
public static void printArray(int[] arr) {
for(var index = 0; index < arr.length; index++){
System.out.print(arr[index]+ ", ");
}
}
public static void main(String[] args) {
int[] arr = { 7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6 };
printArray(arr);
SelectSort(arr);
System.out.println();
printArray(arr);
}
}

// 一次循环 只交换一次索引

冒泡排序

//实现原理：直接两个元素相比较，选出最大或者最小，直接进行交换
public static void BubbleSort(int[] arr){
//如果数组没有 或者 数组长度为空 直接返回
if(arr ==null || arr.length == 0) return;

for(var index = arr.length; index > 1; index--){
for(var j = 0; j < index -1; j++){
if(arr[j] > arr[j+1]){
Swap(arr, j, j+1);
}
}
}
}
//一次循环， 交换索引次数 >= 1

插入排序

//实现原理：排序0~0，0~1，0~2直到0~N上面有序
public static void InsertSort(int[] arr){
//如果数组没有 或者 数组长度为空 直接返回
if(arr ==null || arr.length == 0) return;

for(var index = 1; index < arr.length; index++){
int newNumIndex = index;
while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
Swap(arr, newNumIndex - 1, newNumIndex);
newNumIndex--;
}
}
}

public static void InsertSortTwo(int[] arr){
//如果数组没有 或者 数组长度为空 直接返回
if(arr ==null || arr.length == 0) return;

for(var index = 1; index < arr.length; index++){
for(int j = index -1; j >= 0 && arr[j] > arr[j + 1]; j--){
Swap(arr, j, j + 1);
}
}
}