2020-06-15

LeetCode二分查找

面试10.03 搜索旋转数组(map存储查找)

题目

分析

1. 利用map存储数组内容和下标，然后通过containsKey(target)输出最小的value值即可

代码

public class SouSuoXuanZhuanArr {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        int target=input.nextInt();
        System.out.println(search(a,target));
    }

    public static int search(int[] arr, int target) {
        int min=Integer.MAX_VALUE;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();  //设置map集合存储
        for(int i=0;i<arr.length;i++){
            map.put(arr[i],i);   //将数组的集合内容和下标存储下去
        }
        if(map.containsKey(target)){  //如果map里面有这个就获取map对应下标 
            int i=map.get(target);
            min=Math.min(min,i);  //多个出现就得到最小的那个索引
            return min;
        }
        return -1;  //默认找不到就是-1
    }

}

结果

面试10.05 稀疏数组搜索(普通遍历)

题目

分析

就是普通的将字符串数组每一位和目标string对比

代码

public class XiShuSouSuo {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String[] words={"at","","","","ball","","","car","","","dad","",""};
        String s=input.next();
        System.out.println(findString(words,s));
    }

    public static int findString(String[] words, String s) {
        int index=-1;
        for(int i=0;i<words.length;i++){
            String c=words[i];
            if(c.equals(s)){
                return i;
            }
        }
        return index;
    }

}

结果

面试11 旋转数组的最小数字(二分法范围确定)

题目

分析

代码

public class XuanZhuanMin {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=input.nextInt();
        }
        System.out.println(minArray(a));
    }

    public static int minArray(int[] numbers) {
        int left=0;
        int right=numbers.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(numbers[right]<numbers[mid]){  // ..3..1(肯定在右边mid-right中)
                left=mid+1;
            } else if (numbers[mid] < numbers[right]) {  //..1..3(肯定在左边left-mid中)
                right=mid;
            }else{
                right--;  //确定不了在哪个区域就right--缩小范围
            }
        }
        return numbers[left];  //最后三个指针肯定在一个位置就是需要的
    }

}