[数据结构与算法]面试官最最最常问的几种算法(Java实现)

算法的概念

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

• 描述：算法是一种解决特定问题的思路
• 常见算法：
  

递归

概念
递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。

递归三要素

• 递归结束条件：既然是循环就必须要有结束，不结束就会OOM了
• 函数的功能：这个函数要干什么，打印，计算…
• 函数的等价关系式：递归公式，一般是每次执行之间，或者与个数之间的逻辑关系

Demo案例

/**
 * @Description: 打印5次”Hello World“
 * @title: PrintHelloWorld
 * @Author szh
 * @Date: 2022/1/7 22:35
 * @Version 1.0
 */
public class PrintHelloWorld {

    //递归实现
    public static void print(String ss, int n) {
        //递归条件
        if(n>0){
            //函数的功能
            System.out.println(ss);
            //函数的等价关系式
            print(ss,n-1);
        }
    }
    public static void main(String[] args) {
        //调用递归  
        print("Hello World", 5);
    }
}

/**
 * @Description: 斐波那契数列：0、1、1、2、3、5、8、13、21、34、55.....
 * @title: FibonacciSequenceTest
 * @Author szh
 * @Date: 2022/1/7 22:38
 * @Version 1.0
 */
public class FibonacciSequenceTest {

    //递归实现 -> 函数的等价关系式：fun(n)=fun(n-1)+fun(n-2)
    public static int fun2(int n) {
        if (n <= 1) return n;
        return fun2(n - 1) + fun2(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fun2(9));
    }
}

规律：从第3个数开始，每个数等于前面两个数的和递归分析：函数的功能：返回n的前两个数的和递归结束条件：从第三个数开始，n<=2函数的等价关系式：fun(n)=fun(n-1)+fun(n-2)

分治算法

概念
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
关于分治和递归的区别
分治算法是一种处理问题的思想，递归是一种编程技巧
分治算法的递归实现中，每一层递归都会涉及这样三个操作：

• 分解：将原问题分解成一系列子问题
• 解决：递归地求解各个子问题，若子问题足够小，则直接求解
• 合并：将子问题的结果合并成原问题

Demo案例:
将字符串中的小写字母转化为大写字母“abcde”转化为"ABCDE"
利用分治的思想将整个字符串转化成一个一个的字符处理

/**
 * @Description:  字符串小写字母转大写字母---分治算法
 * @title: CharUpCase
 * @Author szh
 * @Date: 2022/1/7 22:53
 * @Version 1.0
 */
public class CharUpCase {

    public static char[] toUpCase(char[] arr,int i){
        //递归结束条件
        if(i>=arr.length){
            return arr;
        }
        arr[i]=toUpCaseUnit(arr[i]);
        return toUpCase(arr,i+1);
    }

    /**
     * 单元方法 小写转大写
     * @param a
     * @return
     */
    private static char toUpCaseUnit(char a){
        //不是字母
        if((int)a<97||(int)a>122){
            return ' ';
        }
        return  (char)Integer.parseInt(String.valueOf((int)a-32));
    }

    public static void main(String[] args) {
        char[] arr=toUpCase("abcdde".toCharArray(),0);
        System.out.println(arr);
    }
}

/**
 * @Description: 求x的n次方问题
 * @title: Pow
 * @Author szh
 * @Date: 2022/1/7 23:03
 * @Version 1.0
 */
public class Pow {

    public static int dividpow(int x,int n){

        //递归结束 任何数的1次方都是它本身
        if(n==1){
            return x;
        }

        //每次分拆成幂的一半
        int half=dividpow(x,n/2);
        //偶数          
        if(n%2==0){
            return half*half;
        } else {
            return half*half*x;
        }
    }

    public static void main(String[] args) {
        System.out.println(dividpow(2,10));
    }
}

贪心算法

回溯算法

动态规划

0-1背包问题