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

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