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

2023-12-22 19:34:02

面试 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];
    }
}

一起加油!算法需要正向反馈,建议从专项练起,很多算法的数据结构,解题思路都需要接触,思维开拓了,就可以一题多解。

文章来源:https://blog.csdn.net/qq_67358181/article/details/135159622
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。