剑指Offer-面试算法题

1.二分查找（递归与非递归实现）

基本算法，掌握好循环条件

package com.company;

/**
 * Description :二分查找（递归与非递归实现）
 * Created by Wanbo
 * Date :2021/7/18
 */
public class offer1 {
//   非递归
    public static int binarySearch(int []arr, int num){
        int low =0, high = arr.length-1, mid = 0;
        while (low <= high){
            mid = (low + high)/2;
            if(arr[mid] == num){
                return mid;
            }
            else if(arr[mid] > num){
                high = mid-1;
            }
            else if(arr[mid] < num){
                low = mid+1;
            }
        }
        return -1;
    }

//    递归
    public static int recursiveBinarySearch(int arr[], int low, int high, int num){
        int mid = 0;
        if(low <= high) {
            mid = (low + high)/2;
            if(arr[mid] == num){
                return mid;
            }
            else if(arr[mid] > num){
                return recursiveBinarySearch(arr, low, high-1, num);
            }
            else if(arr[mid] < num){
                return recursiveBinarySearch(arr, mid+1, high, num);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int arr[] = {1,3,5,7,9,10,12,15,20};
        System.out.println(binarySearch(arr,7));
        System.out.println(recursiveBinarySearch(arr,0,arr.length-1,7));
    }
}

2.二维数组中查找

两个for循环复杂度比较高，从右上或左下进行遍历查找，每遍历一次就能减少一行/列，降低复杂度

package com.company;

/**
 * Description :二维数组中查找
 * Created by Wanbo
 * Date :2021/7/18
 */
public class offer2 {
//    右上或左下开始遍历，减少遍历范围，我采用右上
    public static boolean findNumIn2DArray(int array[][], int num) {
        if(array.length == 0 || array[0].length == 0){
            return false;
        }
        int rows = array.length;
        int columns = array[0].length;
        int i = 0;
        int j = columns - 1;
        while(i < rows && j >=0) {
            if(array[i][j] == num) {
                return true;
            }
            else if(array[i][j] > num) {
                j--;
            }
            else {
                i++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int arr[][] = {
                {1,2,3},
                {4,5,6},
                {7,8,9}
        };
        System.out.println(findNumIn2DArray(arr, 2));
    }
}

3.旋转数组中最小的数

旋转数组可以分为两个子数组，都是有序，且后面的子数组最大的要小于等于左边的子数组最小的元素，常规遍历复杂度为n，采用二分查找。

package com.company;

/**
 * Description :旋转数组中最小的数
 * Created by Wanbo
 * Date :2021/7/18
 */
public class offer3 {
    public static int minNumberInRotateArray(int [] array) {
        if(array.length==0){
            return 0;
        }
        int low = 0, high = array.length-1, mid = 0;
        while(low < high){
            if(array[low]<array[high]){
                return array[low];
            }
            mid = (high+low)/2;
            if(array[mid] > array[high]){
                low = mid+1;
            }else if(array[mid] < array[high])
            {
                high = mid;
            }else{
                //存在low high mid大小相同的情况，左移high，比较右边小的子数组
                high --;
            }
        }
        return array[low] ;
    }

    public static void main(String[] args) {
//        int arr[] = {3,4,5,1,2};
        int arr[] = {2,2,2,1,2};
        System.out.println(minNumberInRotateArray(arr));
    }
}

4.调整数组使得奇数在前偶数在后

    类似快排，双指针i，j，指向两端，往中间遍历
    i指向的为奇数跳过，j指向的为偶数跳过
    i指向偶数，j指向奇数交换值
    i=j时退出

package com.company;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Description :调整数组使得奇数在前偶数在后
 * Created by Wanbo
 * Date :2021/7/18
 */
public class offer4 {
    /*
    * 类似快排，双指针i，j，指向两端，往中间遍历
    * i指向的为奇数跳过，j指向的为偶数跳过
    * i指向偶数，j指向奇数交换值
    * i=j时退出
    * */
    public static int[] adjustOddAndEven(int arr[]){
        int i = 0, j = arr.length-1, temp = 0;
        while(i < j){
            while(i<j && arr[i]%2 ==1){
                i++;
            }
            while(i<j && arr[j]%2 == 0){
                j--;
            }
            if(i < j) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,7};
        System.out.println(Arrays.toString(adjustOddAndEven(arr)));
    }
}

5.顺时针打印矩阵

找到打印规律，注意起始与终止的循环下标，添加到list中进行打印。

package com.company;
import java.util.ArrayList;

/**
 * Description :顺时针打印矩阵
 * Created by Wanbo
 * Date :2021/7/18
 */
public class offer5 {
    public static ArrayList<Integer> getList(int arr[][]) {
        ArrayList<Integer> list=new ArrayList<>();
        int row=arr.length, col=arr[0].length;
        if(arr.length == 0 || row<0 || col<0){
            return null;
        }
        int count=0;
        while(col>count*2 && row>count*2){
            getNum(list,arr,col,row,count);
            count++;
        }
        return list;
    }

    public static void getNum(ArrayList<Integer> list, int [][] arr,int col,int row,int start){
        int endrow=row-start-1;
        int endcol=col-start-1;
        //从左到右打印一行，行号为count，列号为count到endrow递增，添加row个数
        for(int i=start;i<=endcol;i++){
            list.add(arr[start][i]);
        }
        //从上往下打印，终止行号需大于起始行号，行号为count+1到endrow递增，添加col-1个数
        if(endrow>start){
            for(int i=start+1;i<=endrow;i++){
                list.add(arr[i][endcol]);
            }
        }
        //从右往左打印，终止列号要大于起始列号，添加row-1个数
        // 列号为endcol-1到count递减
        if(endrow>start && endcol>start){
            for(int i=endcol-1;i>=start;i--){
                list.add(arr[endrow][i]);
            }
        }
        //从下往上打印，终止行号至少比开始行号大1，行号为endrow-1到count+1递减，添加col-2个数
        if((endrow-start>1)&&endcol>start){
            for(int i=endrow-1;i>=start+1;i--){
                list.add(arr[i][start]);
            }
        }
    }

    public static void main(String[] args) {
        int arr[][] = {
                {1,2,3,4},
                {4,5,6,5},
                {7,8,9,6}
        };
        ArrayList<Integer> list = getList(arr);
        System.out.println(list.toString());
    }
}

6.数组中超过一半的数

排序找中位数，即使出现次数最多的数，根据数据规模，特征选择合适的排序算法，详见常见八大排序算法

package com.company;
/**
 * Description :数组中超过一半的数
 * Created by Wanbo
 * Date :2021/7/20
 */
public class offer6 {

//    排序找中位数，即使出现次数最多的数，用快排
    public static int getNum(int arr[]){
        rotate(arr,0,arr.length-1);
        return arr[arr.length/2];
    }

    public static int quickSort(int[] arr, int low, int high) {
        int i = low, j = high, temp = arr[low];
        while (i < j) {
            while (i < j && arr[j] >= temp) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
            }
            while (i < j && arr[i] <= temp) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
            }
        }
        arr[i] = temp;
        return i;
    }

    public static void rotate(int[] arr,int low, int high){
        if(arr == null || arr.length == 0){
            return;
        }
        if(low < high) {
            int pos = quickSort(arr, low, high);
            quickSort(arr, low, pos - 1);
            quickSort(arr, pos + 1, high);
        }
    }

    public static void main(String[] args) {
        int arr[] = {3,4,6,1,4,5,2,2,2,2,2,2};
        System.out.println(getNum(arr));
    }
}

7.统计一个数字在排序数组中出现的次数

for一次循环每次遇见key次数+1，复杂度为n，可以采用二分查找，找出数组中第一次与最后一次出现数字的位置，它们的差+1就是出现的次数，复杂度为logn

package com.company;

/**
 * Description :统计一个数字在排序数组中出现的次数
 * Created by Wanbo
 * Date :2021/7/20
 */
public class offer7 {
    public static int getNumOfCount(int arr[], int key){
        if(arr.length == 0 || arr == null){
            return 0;
        }
        int firstKey = 0, lastK = 0, count = 0;
        firstKey = getFirstK(arr, key);
        lastK = getLastK(arr, key);
        if(firstKey != -1 && lastK != -1){
            return (lastK-firstKey+1);
        }
        return 0;
    }
    public static int getFirstK(int arr[], int key){
        int low = 0, high = arr.length-1, mid = 0;
        while(low <= high){
            mid = (low+high)>>1;
            if(arr[mid] == key){
                if(arr[mid-1] < key){
                    return mid;
                }else {
                    high = mid-1;
                }
            }else if(arr[mid] < key){
                low = mid+1;
            }else {
                high = mid-1;
            }
        }
        return -1;
    }
    public static  int getLastK(int arr[], int key){
        int low = 0, high = arr.length-1, mid = 0;
        while(low <= high){
            mid = (low+high)>>1;
            if(arr[mid] == key){
                if(arr[mid+1] > key){
                    return mid;
                }else {
                    low = mid+1;
                }
            }else if(arr[mid] < key){
                low = mid+1;
            }else {
                high = mid-1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int arr[] = {1,2,3,3,4,4,4,4,4,5,6};
        System.out.println(getNumOfCount(arr,4));
        System.out.println();
    }
}

8.求数组中最小的K个数

排序，输出前k个，用一下堆排

package com.company;
/**
 * Description :
 * Created by Wanbo
 * Date :2021/7/20
 */
public class offer8 {
    public static void adjust(int[] arr, int start, int end){
        //start表示要调整树的根节点
        int tmp = arr[start];
        //找左右 孩子的最大值
        for(int i=2*start+1; i<=end; i=2*i+1){
            //判断是否有右孩子
            if(i+1 <= end && arr[i] < arr[i+1]){
                i++;//i指向左右孩子的最大值
            }
            if(arr[i] > tmp){
                //需要将arr[i]换到start位置
                arr[start] = arr[i];
                start = i; //更新start，保存当前最大孩子的下标
            }else{
                break;
            }
        }
        arr[start] = tmp;
    }

    public static void headSort(int[] arr){
        if(arr == null || arr.length == 0){
            return;
        }
        //i初始化为最后一个叶子节点所在子树的根节点
        //经过for循环之后发现当前序列所对应的堆是大根堆
        for(int i=(arr.length-1-1)/2; i>=0 ;i--){
            adjust(arr, i, arr.length-1);
        }
        for(int i=0; i<arr.length; i++){
            //相当于将根节点(待排序列的最大值)换到待排序列的最后
            int tmp = arr[0];
            arr[0] = arr[arr.length-1-i];
            arr[arr.length-1-i] = tmp;

            adjust(arr, 0, arr.length-1-i-1);
        }
    }
    public static void main(String[] args) {
        int[] arr = {2, 9, 10, 11, 29, 3, 6, 100, 50, 67, 30, 8};
        int k = 5;
        headSort(arr);
        for (int i=0; i<k; i++) {
            System.out.println(arr[i]);
        }
    }
}