一、线性查找

线性查找是最简单的查找算法。

代码实现

public class SquareDemo {

    public static void main(String[] args) {
        if (args.length > 0) {
            int square = Integer.parseInt(args[0]);
            for (int i = 0; i < square; i++) {
                if (i * i == square) {
                    System.out.println(i);
                    return;
                }
            }
        }
    }
}

二、二分查找

实现思想：

1. 数组有序。
2. 数组按中间分两段，查找数大于中间往右段找，小于中间往左段找。
3. 再将所在段再从中间分两段，重复步骤2。
4. 如未找到一直重复2、3步骤。

图解：

定义数组如下，left为左边下标，right为右边下标，目标数为16

通过(left + right)/2得到中值midIndex。

比较midIndex值13余16的大小，由于16大，所以再13右边寻找。

再通过(left + right)/2得到中值midIndex。

此时midIndex值我16，与查找的值相等，midIndex下标为4.

代码实现

package com.yang.jdk;

import java.util.Arrays;

/**
 * @author yang
 * @since 2022/3/28
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {14, 5, 3,13,16,28};
        Arrays.sort(arr);
        int index = binarySearch(arr, 0, arr.length - 1, 16);
        System.out.println(index);
    }

    /**
     * 二分查找
     * @param arr 数组
     * @param left 左下标
     * @param right 右下标
     * @param value 查找的值
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int value){
        int midIndex = (left+right)/2;
        int minValue = arr[midIndex];
        if (left <= right) {
            if (minValue > value) {
                binarySearch(arr, 0, midIndex - 1, value);
            } else if (minValue < value) {
                binarySearch(arr, midIndex + 1, right, value);
            } else {
                return midIndex;
            }
        }
        return -1;
    }
}

三、递归

简单点就是自己调用自己的方法，有条件判断什么时候停止！

如何计算阶乘：

图解：

例如求4的阶乘，我们可以看成4! = 43! = 432! = 4321

求出2的阶乘

求出3的阶乘

求出4的阶乘

代码实现

package com.yang.jdk;

/**
 * @author yang
 * @since 2022/3/28
 */
public class Recursion {

    public static void main(String[] args) {
        long factorial = factorial(4);
        System.out.println(factorial);
    }

    /**
     * 阶乘
     *
     * @param n
     * @return
     */
    public static long factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

以上就是递归的实现案例，业务中用到的递归还是比较多，合理利用递归，减轻业务代码。

四、斐波那切数列

什么是斐波那契数列：有一个数列它的0号位置的值是0，1号位置的值是1，当要求的位置(n)大于1时，其值为(n-1)+(n-2)。

递归方式：

代码实现

package com.yang.jdk;

/**
 * @author yang
 * @since 2022/3/28
 */
public class Fibonacci {

    public static void main(String[] args) {
        int fibonacci = fibonacci(5);
        System.out.println(fibonacci);
    }

    public static int fibonacci(int n) {
        if(n <= 1) {
            return n;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

空间换时间

将所计算出的值放入缓存中，不需要重复计算。

public static int fibo(Map<Integer, Integer> fibo, int n) {
        Integer fib = fibo.get(n);
        if(Objects.isNull(fib)) {
            if (n <= 1) {
                return n;
            }
            fib = fibo(fibo, n - 1) + fibo(fibo, n - 2);
            fibo.put(n, fib);
        }
        return fib;
    }

不使用递归

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    int first = 1;
    int second = 2;
    for (int i = 3; i <= n; i++) {
        //每次计算都是以上次计算结果为基础
        int third = first + second; 
        first = second;
        second = third;
    }
    return second;
}

五、堆栈

栈是先进后出，后进先出的一种数据结构。将栈想象成弹夹就可以，而子弹就是每一个数据。

如何实现数组的逆序：

代码实现

package com.yang.jdk;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author yang
 * @since 2022/3/28
 */
public class StackDemo {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 1, 5, 7, 4};
        int[] reverse = reverse(arr);
        System.out.println(Arrays.toString(reverse));
    }

    /**
     * 数组逆序
     *
     * @param arr 需要逆序的数组
     * @return
     */
    public static int[] reverse(int[] arr) {
        if (arr.length == 0) {
            return arr;
        }
        Stack stack = new Stack();
        for (int i = 0; i < arr.length; i++) {
            stack.push(arr[i]);
        }
        int[] array = new int[arr.length];
        for (int j = 0; !stack.isEmpty(); j++) {
            array[j] = (int) stack.pop();
        }
        return array;
    }
}

六、队列

什么是队列

队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

求某个数的完全平方数和的最少个数

• 11入队，取出队首，找到与其相差完全平方数的数入队（10、7、2入队） ，层数加一。
• 再次取出队列中的所有元素（取一层），并且将相差完全平方数的数入队。如果取出的数为零，此时的层数就是所求结果；否则如果该层没有出现0，层数加一，再次操作步骤2
• 取到0，就是最短的路径。而红色区域表示，被重复添加的数字。

代码实现

package com.yang.jdk;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yang
 * @since 2022/3/28
 */
public class QueueDemo {

    public static void main(String[] args) {
        int i = numSquares(11);
        System.out.println(i);
    }

    public static int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        int [] visited = new int[n+1];
        int count = 0; // 记录层数  层数就是最短路径
        while(!queue.isEmpty()) {
            // 每次循环将队列中的元素取完（取完一层）
            int len = queue.size();
            for(int i = 0; i<len;i++) {
                int temp = queue.poll();// 取出队首
                // System.out.println(temp);
                if(temp == 0) { // 找到0   就找到了最短路径
                    return count;
                }
                // 将相差平方数的数添加到队列
                for(int k = 1; temp - k*k >= 0;k++){
                    if(visited[temp - k*k] == 0) {
                        queue.offer(temp - k*k);
                        visited[temp - k*k] = 1;
                    }

                }
            }
            count++;
        }
        return count;
    }
}