package com.tmd.learn.algorithm;
import org.apache.jasper.compiler.JspUtil;
import java.util.Arrays;
import java.util.Scanner;
public class Recursion {
/**
* 位运算符
* &（与）：都为1结果为1
* |（或）：有一个为1结果为1
* ^（异或）：二者不同时结果为1，不进位加法
* 性质：对于任何数x,都有x^x=0,x^0=x
* ~（非）：取反
* >>和<< 将二进制位进行左移或右移操作
* >>>将用0填充高位；>>用符号位填充高位；没有<<<运算符
*/
/**
* 判断奇偶性 X&1 结果是1奇数，结果是0是偶数；因为二进制奇数的最低位必然是1，偶数最低位必然是0
* 获取二进制位是1还是0
*/
/**
* 1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，
* 设计一个算法，将它找出来；不用辅助储存空间？
*/
/**
* 学习视频：https://www.bilibili.com/video/BV1KA411x7oA?p=16
* 递归算法练习
* 求阶乘
* 打印i-j
* 数组求和
* 翻转字符串
* 斐波那契数列
* 最大公约数
* 递归形式进行插入排序
* 汉诺塔--不想看了
* 二分查找的递归解法
* 顺序查找
* 排序的基本算法：冒泡、选择、插入、希尔
*
* 算法的性能分析
* 子问题的规模下降
* 子问题的答案处理消耗时间
* T(n)=T(n-1)+O(1) T指时间，O指算法复杂度
*
* 小白上楼梯：楼梯有n阶楼梯，小白一次可以上1阶，2阶或3阶，实现一个方法，计算小白有多少种走完楼梯的方式？
* 二分法变体：
*
*/
//求阶乘
static int f1(int n) {
if (n == 1)
return 1;
return n * f1(n - 1);
}
//求打印i-j
static void f2(int i, int j) {
if (i > j)
return;
System.out.println(i);
f2(i + 1, j);
}
//数组求和
static int f3(int[] arr, int begin) {
if (begin == arr.length - 1)
return arr[begin];
return arr[begin] + f3(arr, begin + 1);
}
//字符串翻转
static String reverse(String src, int end) {
if (end == 0)
return src.charAt(end) + "";
return src.charAt(end) + reverse(src, end - 1);
}
//斐波那契数列,求斐波那挈数列第几项的值是多少
static int fib(int n) {
if (n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
//最大公约数
static int f4(int a, int b) {
if (b == 0)
return a;
return f4(b, a % b);
}
//递归形式进行插入排序
static void insertSort(int[] arr, int k) {
if (k == 0) {
return;
}
insertSort(arr, k - 1);
int x = arr[k];
int index = k - 1;
while (index > -1 && x < arr[index]) {
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = x;
}
/**
* 冒泡排序的递归解法
* 原理：把大的元素放到最后，第二次不用排了
* 变化：需要排序的元素个数
*
*/
static void bubbleSort(int[] arr , int end){
if(end==0)
return;
int index = 0;
while(index<end){
if(arr[index] > arr[index+1]) {
int temp = arr[index];
arr[index] = arr[index+1];
arr[index+1] = temp;
}
index++;
}
bubbleSort(arr, end-1);
}
/**
* 二分查找的递归解法
* @param arr
* @param low
* @param high
* @param target
* @return
*/
static int binarySearch(int[] arr, int low, int high, int target) {
if (low > high)
return -1;
int mid = low + ((high - low) >> 1); //(high +low)>>>1 防止high+low> Integer.max()
int midVal = arr[mid];
if (target > midVal) {
return binarySearch(arr, mid + 1, high, target);
} else if (target < midVal) {
return binarySearch(arr, low, mid - 1, target);
} else {
return mid;
}
}
/**
* 顺序查找
* @param arr
* @param target
* @return
*/
static int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
/**
* 小白上楼梯：楼梯有n阶楼梯，小白一次可以上1阶，2阶或3阶，实现一个方法，计算小白有多少种走完楼梯的方式？
* @param n
* @return
*/
static int f5(int n){
if (n==0) return 1;
if (n==1) return 1;
if (n == 2) return 2;
return f5(n-1)+f5(n-2)+f5(n-3);
}
/**
* 旋转数组的最小数字：把一个数字最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序数组的旋转，输出旋转数组的最小元素
* 例如数组{3,4,5,1,2}是为{1,2,3,4,5}的一个旋转该数组的最小值为1.
* @param args
*/
/**
* 最长连续递增子序列
* @param
*/
static int[] f6(int[] arr){
int begin=0;
int end= 0;
int length = 1;
int index =0;
for(int i =0; i< arr.length-1;i++){
end =i+1;
begin = index;
if (arr[i]>=arr[i+1]){
//起始下标推进
//新数组长度
//与老数组长度对比
if (length <= i-index+1){
begin = index;
end = i;
length = i-index+1;
}
index = i+1;
}
}
int[] arr1 = new int[end -begin+1];
for(int i=0 ;begin <=end ; begin++,i++){
arr1[i] = arr[begin];
}
return arr1;
}
/**
* 高效的a的n次幂的算法
* @param
*/
static int pow(int a ,int n){
if (n==0) return 1;
int res = a;
int ex =1;
while((ex<<1)<=n){
res = res * res;
ex<<=1;
}
return res * pow(a ,n-ex);
}
static int pow0(int a ,int n){
int res =1;
for (int i=0;i<n;i++){
res *=a;
}
return res;
}
public static void main(String[] args) {
int result = f1(5);
System.out.println(result);
f2(1, 5);
int result2 = f3(new int[]{1, 2, 3, 4, 5, 6}, 0);
System.out.println(result2);
String a = "abcdefghi";
System.out.println(reverse(a, a.length() - 1));
// 1 1 2 3 5 8 13
System.out.println(fib(7));
System.out.println(f4(20, 15));
int[] arr = {1, 3, 5, 2, 6, 7, 9, 5};
// insertSort(arr, arr.length - 1);
System.out.println(Arrays.toString(arr));
int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7, 11, 24, 25, 26, 27, 29, 30, 36, 38, 39, 40, 41, 46, 48, 49, 50, 51, 57, 58, 60, 61, 68, 69, 70, 71, 72};
int target = 10000 * 10000;
int[] arr2 = new int[target];
for (int i = 0; i < arr2.length; i++) {
arr2[i] = i + 1;
}
long init = System.currentTimeMillis();
System.out.println(binarySearch(arr2, 0, arr2.length - 1, target));
System.out.println(System.currentTimeMillis() - init + "ms"); //1ms
init = System.currentTimeMillis();
System.out.println(search(arr2, target));
System.out.println(System.currentTimeMillis() - init + "ms"); //37ms
//冒泡排序的算法复杂度是
bubbleSort(arr,arr.length-1);
System.out.println(Arrays.toString(arr));
// Arrays.sort(arr); 的算法复杂度是N*LgN
/* Scanner sc = new Scanner(System.in);
Boolean flag = false;
while (flag){
int n = sc.nextInt();
System.out.println(f5(n));
}*/
System.out.println("-----");
System.out.println(Arrays.toString(f6(new int[]{1,9,2,5,7,3,4,6,8,0})));
System.out.println(Arrays.toString(f6(new int[]{1,2,3,4,6,8})));
System.out.println(Arrays.toString(f6(new int[]{2,2,2,2,2,2})));
System.out.println(Arrays.toString(f6(new int[]{1,9,2,5,7,3,4,6,8})));
System.out.println(pow(2,2));
System.out.println(pow0(2,15));
}
}
网友评论