funcmySqrt(x int)int { lx := int64(x) var left int64 = 0 var right int64 = lx/2 + 1 for left < right { mid := left + (right-left)/2 if mid*mid < lx { left = mid + 1 //向下取整的，所以需要额外判断或者取右中位数 if left*left > lx { returnint(mid) } } else { right = mid } } returnint(left) }
还有一种比较好的解法，更加贴合模板
//这个其实更能体现模板的好处 funcmySqrt(x int)int { lx := int64(x) var left int64 = 0 var right int64 = lx/2 + 1 for left < right { mid := left + (right-left)/2 + 1 //大于 lx 的一定不是 res 可以排除，但是小于的不一定不是，题目是向下取整的 if mid*mid > lx { right = mid - 1 } else { left = mid } } returnint(left) }
最小值的特点就是肯定是小于等于 nums 的最后一个元素，这里没有重复的元素，所以最小值肯定是小于最后一个元素的，除非最后一个就是最小的元素，这种情况我们设置为 res 的初始值，这样我重写后我感觉更好理解了，进阶版的只需要在这个的基础上稍加改动就行了
funcfindMin(nums []int)int { var n = len(nums) var left, right = 0, n - 1 var res = right//对 nums[n-1] 就是最小值做兜底 for left <= right { mid := left + (right-left)/2 if nums[mid] < nums[n-1] { res = mid right = mid - 1 } else { left = mid + 1 } } return nums[res] }
同理也可以和左边界比较，最小值一定是小于等于 nums[0] 的
funcfindMin(nums []int)int { var n = len(nums) var left, right = 0, n - 1 var res = left //对 nums[0] 就是最小值做兜底 for left <= right { mid := left + (right-left)/2 if nums[mid] < nums[0] { res = mid right = mid - 1 } else { left = mid + 1 } } return nums[res] }
# update: 2020/4/8 classSolution: deffindMin(self, nums: List[int]) -> int: left, right = 0, len(nums)-1 res = 0 while right >= 0and nums[right] == nums[0]: right -= 1 nr = right while left <= right: mid = left + (right - left)//2 # 和 nr 比，不能和 0 比，可能会有 0 1 2 这样的 if nums[mid] > nums[nr]: left = mid + 1 else: res = mid right = mid - 1 return nums[res]
publicstaticintpeakIndexInMountainArray(int[] A) { int left=0,right=A.length-1; while(left<right){ int mid=left+(right-left)/2; //System.out.println(mid); if (mid>0 && mid<A.length && A[mid] > A[mid-1] && A[mid]<A[mid+1]) { left=mid+1; }elseif (mid>0 && mid<A.length && A[mid]< A[mid-1] && A[mid]>A[mid+1]){ right=mid-1; }else{ return mid; } } return left; }
代码优化 2020.4.9 不知道为啥之前写成哪个鬼样子。
publicstaticintpeakIndexInMountainArray(int[] A) { int left=0,right=A.length-1; while(left<right){ int mid=left+(right-left)/2; if (A[mid]<A[mid+1]) { left=mid+1; }else{ right=mid; } } return left; }
这题，咋说呢，数据太弱了，配不上 hard 题，顶多算个 mid 偏简单，数据大的时候可以考虑加上缓存，这样就比较有意思了，这里我就懒得加了😁
funcfindInMountainArray(target int, mountainArr *MountainArray)int { n := mountainArr.length() //寻找山顶 left := 0 right := n - 1 for left < right { mid := left + (right-left)/2 //mid+1 肯定不会越界 if mountainArr.get(mid) < mountainArr.get(mid+1) { left = mid + 1 } else { right = mid } } res := -1 res = binarySearchUp(mountainArr, target, 0, left) if res == -1 { res = binarySearchDown(mountainArr, target, left, n-1) } return res }
funcbinarySearchUp(mountainArr *MountainArray, target, left, right int)int { for left < right { mid := left + (right-left)/2 if mountainArr.get(mid) < target { left = mid + 1 } else { right = mid } } if mountainArr.get(left) == target { return left } return-1 }
funcbinarySearchDown(mountainArr *MountainArray, target, left, right int)int { for left < right { mid := left + (right-left)/2 if mountainArr.get(mid) > target { left = mid + 1 } else { right = mid } } if mountainArr.get(left) == target { return left } return-1 }
这两个二分是可以合并的，懒得合了（太懒了吧你也😅）
UPDATE: 2020.7.14
自定义函数传递，简化代码
funcfindInMountainArray(target int, mA *MountainArray)int { var n = mA.length() var left = 0 var right = n-1 var maxIdx = right for left <= right{ mid := left + (right-left)/2 //左中，所以 mid+1 不会越界 if mA.get(mid) > mA.get(mid+1){ maxIdx = mid right = mid - 1 }else{ left = mid + 1 } } lr := search(mA, target, 0, maxIdx, func(i int, j int)bool{ return i <= j }) if lr != -1{ return lr } return search(mA, target, maxIdx+1, n-1, func(i int, j int)bool{ return i >= j }) }
funcsearch(mA *MountainArray, target int, left int, right int, less func(int, int)bool) int { var res = left for left <= right{ mid := left + (right-left)/2 if less(mA.get(mid), target){ res = mid left = mid + 1 }else{ right = mid - 1 } } if mA.get(res) != target{ return-1 } return res }
funccountNegatives(grid [][]int)int { iflen(grid) <= 0 { return0 } var m, n = len(grid), len(grid[0]) var count = 0 var i, j = m-1, 0 for i >= 0 && j < n { if grid[i][j] < 0 { count += n - j i-- }else{ j++ } } return count; }
解法二
O(mlogn) 解法
//O(mlogn) 只利用了行逆序的条件 funccountNegatives(grid [][]int)int { iflen(grid) <= 0 { return0 } var count = 0 var m = len(grid) var n = len(grid[0]) for i := 0; i < m; i++ { count += (n - search(grid[i])) } return count }
funcsearch(nums []int)int { var left = 0 var right = len(nums)-1 var res = right+1 for left <= right { mid := left + (right-left)/2 if nums[mid] < 0 { res = mid right = mid - 1 }else{ left = mid + 1 } } return res }
funcisPerfectSquare(num int)bool { var left = 0 var right = num var res = num + 1 for left <= right { mid := left + (right-left)/2 if mid*mid >= num { res = mid right = mid - 1 } else { left = mid + 1 } } return res*res == num }
解法二
完全平方数的性质
//完全平方数性质 n^2 = 1 + 3 + 5 +...+2n+1 （前 n 个奇数的和） //所以只需要判断 num 能不能被奇数减成 0 就行了 funcisPerfectSquare(num int)bool { var i = 1 for num > 0 { num -= i i += 2 } return num == 0 }
这个题目感觉不是 easy 啊，一开始想劈叉了，以为是二分答案，写了半天后来 WA 在一个很大的 case，一直以为是溢出了，改了半天的 bug 没改出来。后来自己按照 case 的规律构建了一个小的 case，发现也 WA 了，然后才意识到是方法错了，(case: [4,9] [4,8])，这个 case 按照二分答案的思路就是错的，二分答案是思路就是验证该半径下能否覆盖整个区间，其实也是题目理解有点问题，题目的要求是覆盖每个房子，而不是覆盖整个区间，所以只需要找到每个房子最近的供暖器就行了，然后统计这些最小值得最大值就是我们需要的半径
funcfindRadius(houses []int, heaters []int)int { //边界处理 heaters = append(heaters, math.MaxInt32) heaters = append(heaters, math.MinInt32) sort.Ints(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 for _, h := range houses{ left := search(heaters, h) res = Max(res, Min(h-heaters[left], heaters[left+1]-h)) } return res } //target 左边最近的一个 funcsearch(heaters []int, target int)int { var left, right = 0, len(heaters)-1 var res = left //左边没有供暖器 for left <= right { mid := left + (right-left)/2 if heaters[mid] <= target{ res = mid left = mid + 1 }else{ right = mid - 1 } } return res }
另一种写法，不额外处理边界，也是一开始的写法
funcfindRadius(houses []int, heaters []int)int { sort.Ints(heaters) var n = len(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 for _, h := range houses{ left := search(heaters, h) if left == -1{ //全部大于 hourse, 取最小的那个 res = Max(res, heaters[0]-h) }elseif left+1 < n{ res = Max(res, Min(h-heaters[left], heaters[left+1]-h)) }else{ res = Max(res, h-heaters[left]) } } return res }
//target 左边最近的一个 funcsearch(heaters []int, target int)int { var left, right = 0, len(heaters)-1 var res = -1//左边没有供暖器 for left <= right { mid := left + (right-left)/2 if heaters[mid] <= target{ res = mid left = mid + 1 }else{ right = mid - 1 } } return res }
funcfindRadius(houses []int, heaters []int)int { heaters = append(heaters, math.MaxInt32) heaters = append(heaters, math.MinInt32) sort.Ints(heaters) sort.Ints(houses) var n = len(heaters) var Min = func(a, b int)int { if a < b {return a}; return b} var Max = func(a, b int)int { if a < b {return b}; return a} var res = 0 var left = 0 for _, h := range houses { for left < n && heaters[left] < h { left++ } res = Max(res, Min(heaters[left]-h, h-heaters[left-1])) } return res }
publicintsmallestDivisor(int[] nums, int threshold) { int left=1,right=1000000; while(left<right){ int mid=left+(right-left)/2; int sum=0; for (int i=0;i<nums.length;i++) { sum+=(nums[i]+mid-1)/mid; //向上取整 } if (sum>threshold) { left=mid+1; }else{ right=mid; } } return left; }
其实只要明确一点这题就很容易想到二分，解空间为：[1，max(nums[i])] 我们只需要在这个区间之内做二分搜索就 ok 了，再然后就是向上取整的一个小技巧
publicintminTime(int[] time, int m) { int left=0,right=0;//上界最多 sum(time) for(int i=0;i<time.length;i++){ right+=time[i]; } int res=right+1; while(left<=right){ int mid=left+(right-left)/2; if(check(time,mid,m)){ res=mid; right=mid-1; }else{ left=mid+1; } } //其实返回 left 就行了，主要是避免搞混 return res; }
第一个参数整数 n 代表序列数字个数， 第二个参数整数 k 代表分出的段数， 第三个参数 vector a 包含 n 个元素代表 n 个数字
解法一
我是真的菜啊，上面一题会写这题就不会写了，果然我这种菜鸡刷题就是背题，变一下就不会了。其实和上面的正好是反过来的，上面是要最大值最小，这里是要最小值最大，所以 check 的思路也是相反的，上面是验证：分为 k 组能否保证每组都小于等于 mid。所以这题很显然就应该是：分为 k 组能否保证每组都大于等于 mid（这里验证也是逐渐逼近答案）
//最小值最大 publicintsolve(int n, int k, int[] a) { intleft=0; intright=0; for (inti=0; i < a.length; i++) { left = Math.min(left, a[i]); right += a[i]; } intres=0; while (left <= right) { intmid= left + (right-left)/2; if (check(mid, a, k)) { res = mid; left = mid + 1; }else { right = mid - 1; } } return res; }
//分为 k 组能否保证每组都大于等于 mid（如果可以说明还可以更大） publicbooleancheck(int mid, int[] a, int k) { intsum=0; intcount=0; for (inti=0; i < a.length; i++) { sum += a[i]; if (sum >= mid) { sum = 0; count++; } } return count >= k; }
publicintminDays(int[] bloomDay, int m, int k) { int n=bloomDay.length; if(m*k>n) return -1; //花园的花不够 //直接写就完事了，这里数据范围只到 1e9，log(1e9) 很小的，只有 30 左右 int left=1,right=(int)1e9; int res=right+1; while(left<=right){ int mid=left+(right-left)/2; if(check(bloomDay,m,k,mid)){ res=mid; right=mid-1; }else{ left=mid+1; } } return res; }
publicintminDays(int[] bloomDay, int m, int k) { int n=bloomDay.length; if(m*k>n) return -1; //花园的花不够 //直接写就完事了，这里数据范围只到 1e9，log(1e9) 很小的，只有 30 左右 int left=1,right=(int)1e9; int res=right+1; while(left<=right){ int mid=left+(right-left)/2; if(check(bloomDay,m,k,mid)){ res=mid; right=mid-1; }else{ left=mid+1; } } return res; }
publicbooleancheck(int[] bloomDay,int m,int k,int day){ int i=0; int count=0; int temp=0; //相邻的开花数量 for(int d:bloomDay){ if(d<=day){ //花开了 (md，这个 if 写反两次） temp++; }else{ temp=0; } if(temp==k){ temp=0; count++; } } return count>=m; }
二分答案的性质很明显，但是这里和之前的不一样，这里是浮点数二分，和整数的不太一样，浮点数/2 的时候都是实际的一分为 2，不会有整除的问题，同时题目给出了 eps=1e-6，只要 left 和 right 误差在这个范围内就是合法的，并不是要求 left 和 right 相等，这里还有一个问题，就是这里如果 eps 太小的话由于精度问题还是可能会 tle，这个时候就可以采取固定循环次数的方式逼近，一般取 100，200 就够了
publicdoubleminmaxGasDist(int[] stations, int k) { // Write your code here doubleleft=0; doubleright=1e8+1; doubleres= right; //for (int i = 0; i <= 100; i++){ while (right-left >= 1e-6){ doublemid= left+(right-left)/2; if (check(stations, k, mid)) { res = mid; right = mid; }else{ left = mid; } } return res; }
publicbooleancheck(int[] stations, int k, double D) { intcount=0; for (inti=1; i < stations.length; i++) { count += (stations[i]-stations[i-1]) / D; } return count <= k; }
publicintmaxDistance(int[] position, int m) { Arrays.sort(position); intleft=1; intright= (int)1e9+1; intres=1; while (left <= right) { intmid= left + (right-left)/2; if (check(position, m, mid)) { res = mid; left = mid + 1; }else{ right = mid - 1; } } return res; } //1 1000 2000 3000 m=3 //验证在距离至少为 force 的情况下能否放下所有的球，然后增大 force 逼近答案 //所以 check 验证成功的不一定是合法的答案，但是最终一定会到达 real ans //类似【378. 有序矩阵中第 K 小的元素】这道题 publicbooleancheck(int[] position, int m, int force) { intlast= position[0]; m--; for (inti=1; i < position.length; i++) { if (position[i]-last < force) { continue; } last = position[i]; m--; if (m==0) returntrue; } returnfalse; }
check 类似 [378. 有序矩阵中第 K 小的元素](#378-有序矩阵中第 k 小的元素)这道题，都是逼近答案，而不是验证答案，其实一开始我的 check 不是这样写的，写的很丑，这里看了别人的写法发现 continue 有时候还是挺好用的
