面试 Java 算法高频题五问五答第二期

作者：程序员小白条，个人博客

相信看了本文后，对你的面试是有一定帮助的！

⭐点赞⭐收藏⭐不迷路！⭐

寻找峰值:

主要思想：二分查找，利用get函数，方便判断越界情况，如果没越界返回的是1和nums[index],如果越界返回0,0.Compare函数，用于比较nums,index1,index2两个数的大小情况，如果得到get后，第一个索引不同，return nums[0]>nums[0]1:-1,如果第二个索引相同返回0，return nums[1]>nums[1]1:-1;

主函数：用compare判断是否属于峰值，mid-1,mid<0说明mid>mid-1,mid,mid+1>0,说明mid>mid+1,if(comapre(nums,mid,mid+1)>0) 左边大于右边，抛弃右边 right = mid-1;

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int result = 0;
        while(left<=right){
            int mid = (left+right)>>1;
            if(compare(nums,mid-1,mid)<0&&compare(nums,mid,mid+1)>0){
                result = mid;
                break;
            }
            if(compare(nums,mid,mid+1)>0){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return result;
    }
    public int[] get(int [] nums,int index){
        if(index<0||index>=nums.length){
            return new int []{0,0};
        }
        return new int []{1,nums[index]};
    }
    public int compare(int []nums,int idx1,int idx2){
       int[] nums1 = get(nums,idx1);
       int [] nums2 = get(nums,idx2);
       if(nums1[0]!=nums2[0]){
           return nums1[0]>nums2[0]?1:-1;
       }
       if(nums1[1]==nums2[1]){
           return 0;
       }
       return nums1[1]>nums2[1]?1:-1;
    }
}

搜索旋转排序数组:

主要思想：因为左右各一边是升序，因此先判断nums[mid]是否等于target，如果等于直接返回,如果然后判断mid和left,区别哪边有序，再判断target在有序的一边还是无序的一边，如果mid==left,left++;

class Solution {
   public int search(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(left<=right){
           int mid = (left+right)>>1;
           if(nums[mid]==target){
               return mid;
           }
           if(nums[mid]>nums[left]){
               if(target>=nums[left]&&target<nums[mid]){
                   right = mid-1;
               }else{
                   left = mid+1;
               }
           }else if(nums[mid]<nums[left]){
               if(nums[mid]<target&&target<=nums[right]){
                     left = mid+1;
               }else{
                    right = mid-1;
               }
           }else{
               left++;
           }
       }
       return -1;
    }
}

做菜顺序:

主要思想：贪心算法，先将数组进行降序，然后记录preSum,和sum,如果preSum+nums[i]>0那么 preSum+=nums[i] ,sum+=preSum;

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        for (int i = 0, j = satisfaction.length - 1; i < j; i++, j--) {
            int temp = satisfaction[i];
            satisfaction[i] = satisfaction[j];
            satisfaction[j] = temp;
        }
        int presum = 0, ans = 0;
        for (int si : satisfaction) {
            if (presum + si > 0) {
                presum += si;
                ans += presum;
            } else {
                break;
            }
        }
        return ans;
    }
}

在排序数组中查找元素的第一个和最后一个位置:

主要思想：二分查找，两个辅助函数，分别寻找左右区间，如果没找到返回-2，主函数分成三种情况，没找到返回-1,-1,如果rightRange-leftRange>1,也就是至少有一个，那么说明找到return leftRange+1,RightRange-1,其他情况，return -1,-1;

class Solution {
   public int[] searchRange(int[] nums, int target) {
        int left = searchLeftRange(nums, target);
        int right = searchRightRange(nums, target);
        if (left == -2 || right == -2) {
            return new int[]{-1, -1};
        }
        if (right - left > 1) {
            return new int[]{left + 1, right - 1};
        }
        return new int[]{-1,-1};
    }
    public int searchLeftRange(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       int leftRange = -2;
       while(left<=right){
           int mid = (left+right)>>1;
           if(nums[mid]<target){
                left = mid+1;
           }else{
               right = mid-1;
               leftRange = right;
           }
       }
       return leftRange;
    }

    public int searchRightRange(int[] nums, int target) {
        int left = 0;
       int right = nums.length-1;
       int rightRange = -2;
       while(left<=right){
           int mid = (left+right)>>1;
           if(nums[mid]>target){
               right = mid-1;
           }else{
            left = mid+1;
            rightRange = left;
           }
       }
       return rightRange;
    }

}

寻找旋转排序数组中的最小值:

主要思想：利用二分查找，旋转后，每次去抛弃较大区间，nums[mid]>nums[right]抛弃左边，注意left<right是循环条件，right = mid,

class Solution {
    public int findMin(int[] nums) {
        int left=  0;
        int right = nums.length-1;
        while(left<right){
            int mid = (left+right)>>1;
            if(nums[mid]>nums[right]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
}