Java面试准备（3）之数据结构与算法——两个最基础的算法

最容易说的是坚持，最难做的也是坚持！


1.递归




1.1基础概念

递归，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。
本质：是一种循环，而且在循环中执行的就是调用自己，递归调用将每次返回的结果存在栈帧中
递归三要素

递归结束条件：必须要有结束，不结束就会OOM了函数的功能：函数实现功能，比如计算，打印函数的等价关系式：递归公式，一般是每次执行之间，或者与个数之间的逻辑关系

1.2 经典案例之斐波拉契数列

0、1、1、2、3、5、8、13、21、34、55..... ，从第3个数开始，每个数等于前面两个数的和
公式：fun(n)=fun(n-1)+fun(n-2)
代码实现：
public class Fibonacci {    public static int sum(int n){        if (n<=1) return n;//结束条件        return sum(n-1)+sum(n-2);//功能和关系式    }    public static void main(String[] args) {        System.out.println(sum(10)); //55    }}1.3时间复杂度和应用




斐波那契数列 普通递归解法为 O(2^n).
优缺点
优点：代码简单
缺点：占用空间巨大，递归太深会导致OOM,大量重复计算
应用
递归作为基础算法，应用非常广泛，比如在二分查找、快速排序、归并排序、树的遍历上都有使用递归，回溯算法、分治算法、动态规划中也大量使用递归算法实现。
2.二分查找

2.1 基础概念

二分查找（Binary Search）算法，也叫折半查找算法，二分查找是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找。



本质
二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
2.2 小案例之查找有序数组某个数的下标

注意前提是有序数组
循环实现：
package com.david;public class HalfSearch {    public static int binarySearch(int[] nums,int n){        int low=0;//低位索引        int high=nums.length-1;//高位索引        int mid=0;//中间位置        while (low<=high){            mid=(low+high);            if (n==nums[mid]){                return mid;            }else if (n<nums[mid]){                //在左侧，高位往左移动                high=mid-1;            }else if (n>nums[mid]){                //在右侧，低位往右移动                low=mid+1;            }        }        return -1;    }    public static void main(String[] args) {        int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};        System.out.println(binarySearch(nums,66));//7    }}递归实现：
package com.david;public class HalfSearch {    public static int bSearch(int[] nums,int n){        return bSearchUnit(nums,0,nums.length-1,n);    }    private static int bSearchUnit(int[] nums, int low, int high, int n) {        int mid=(low+high)/2;        if (n==nums[mid]) {            return mid;        }else if (n>nums[mid]){            //右侧，low右移            return bSearchUnit(nums,mid+1,high,n);        }else if(n<nums[mid]){            //左侧，high左移            return bSearchUnit(nums,low,mid-1,n);        }        return -1;    }    public static void main(String[] args) {        int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};        System.out.println(bSearch(nums,66));//7    }}2.3 面试题(阿里)

一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
思路：二分法查找
偶数位索引跟后面的比相同，奇数位索引跟前面的比相同 则说明前面的都是出现2次的偶数位索引跟前面的比相同，奇数位索引跟后面的比相同 则说明后面的都是出现2次的
package com.david;public class HalfDemo {    public static int bSearch(int[] nums){        int low=0;        int high=nums.length-1;        int mid;        while (low<=high){            mid=(low+high)/2;            if (mid%2==0){                //偶数                if (nums[mid]==nums[mid+1]){                    //偶数如果和后一位相等，说明前面都是成对出现的                    low=mid+1;                }else if (nums[mid]==nums[mid-1]){                    //偶数如果和前一位相等，说明后面都是成对出现的                    high=mid-1;                }else{                    return nums[mid];                }            }            else{                //奇数                if (nums[mid]==nums[mid+1]){                    //奇数如果和后一位相等，说明后面都是成对出现的                    high=mid-1;                }else if (nums[mid]==nums[mid-1]){                    //奇数如果和前一位相等，说明前面都是成对出现的                    low=mid+1;                }else{                    return nums[mid];                }            }        }      return -1;    }    public static void main(String[] args) {        int[] nums={1,1,2,2,3,3,4,5,5,6,6};        int n = bSearch(nums);        System.out.println("n = " + n);//4    }}2.4 时间复杂度和应用

时间复杂度 O(logn).
优缺点优点：速度快，不占空间，不开辟新空间缺点：必须是有序的数组，数据量太小没有意义，但数据量也不能太大，因为数组要占用连续的空间
应用
有序的查找基本都可以使用二分法。