面试 Java 算法高频题五问五答第二期
面试 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];
}
}
一起加油!算法需要正向反馈,建议从专项练起,很多算法的数据结构,解题思路都需要接触,思维开拓了,就可以一题多解。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!