LeetCode每日十题---二分查找（二）

1.题目描述

1.1笔者分析

动态规划的方法大家都能想到，关键是用二分法来提高效率。看了下评论区大佬们的方法，确实挺新颖的，把二分法用的如此巧妙。针对这题，dp[i]：所有长度为i+1的递增子序列中，最小的那个序列尾数。由定义知dp数组必然是一个递增数组，可以用maxL来表示最长递增子序列的长度。对数组进行迭代，一次判断每个数num将其插入dp数组相应的位置： 1.num>dp[maxL]，表示num比所有一直递增序列的尾数都大，将num添加入dp数组尾部，并将最长递增序列长度maxL加1. 2.dp[i-1]<num<=dp[i] ，只更新相应的dp[i]。

int maxL=0; int[] dp=new int[nums.length]; for(int num:nums){ int lo=0,hi=maxL; while(lo<hi){ int mid=lo+(hi-lo)/2; if(dp[mid]<num) lo=mid+1; else hi=mid; } dp[lo]=num; if(lo==maxL) maxL++; } }

2.题目描述2

2.1笔者分析

这么有意思的一道题，被二分法如此暴力的解出来了，效率还不算太低，罪过罪过。

class Solution { public int maxDistance(int[] position, int m) { Arrays.sort(position); int zuo=1; int you=1000000000; int mid=0; while(zuo<you-1){ mid=(zuo+you)/2; if(isOk(position,m,mid)){ zuo=mid; }else{ you=mid-1; } } return isOk(position,m,you)?you:zuo; } public boolean isOk(int position[],int m,int dis){ int n=m-1; int zuihou=position[0]; for(int i=1;i<position.length;i++){ if(position[i]-zuihou>=dis){ n--; zuihou=position[i]; } } return n<1; } }

3.题目描述

3.1笔者分析

只能说被标签误导了，用的是滑动窗口，而且特别简洁。

class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0; int sum=0; int len=0; for(int j=0;j<nums.length;j++){ sum+=nums[j]; while(sum>=s){ len=len==0?j-i+1:Math.min(len,j-i+1); sum-=nums[i++]; } } return len; } }

总结

二分真的太暴力了，而且还拿它没办法。每日十题打卡三十一天，以下图为证。