邢台网络公司做网站,有限责任公司怎么注册,5113二次加密和三次加密,wordpress 备份 教程面试题72#xff1a; 问题#xff1a;
输入一个非负整数#xff0c;计算它的平方根。
解决方案#xff1a;
使用二分查找。一个数x的平方根一定小于或等于x#xff0c;同时#xff0c;除了0之外的所有非负整数的平方根都大于等于1#xff0c;故该数的平方根在1到x…面试题72 问题
输入一个非负整数计算它的平方根。
解决方案
使用二分查找。一个数x的平方根一定小于或等于x同时除了0之外的所有非负整数的平方根都大于等于1故该数的平方根在1到x的范围内。定义left为1作为左边界right为x作为右边界。取该范围内的中间数字m并判断m是否小于x/m如果m小于x/m那么继续判断m1是否大于x/m1如果m1大于x/m1那么返回m如果m1不大于x/m1那么目标值位于数组后半部分。如果m大于或等于x/m那么目标值位于数组前半部分。
源代码
class Solution {public int mySqrt(int x) {int left 1;int right x;while(left right){int mid (left right)/2;//if(mid x/mid){if(mid 1 x/(mid 1)){return mid;}left mid 1;}else{right mid - 1;}}return 0;}
}面试题73 问题
门卫走开H小时有n堆香蕉狒狒去吃香蕉狒狒一个小时只能吃一堆香蕉狒狒要在门卫回来前将香蕉吃完问狒狒每个小时至少得吃多少根香蕉。
解决方案
使用二分查找。狒狒吃香蕉的速度的范围在1和数组中的最大值也就是n堆香蕉的最大值记为max根。在1-max中取中间值mid求出按照每个小时吃mid根的速度吃完n堆香蕉需要多少小时记为time1如果time1小于或等于H那么继续判断mid是否为1如果是那么mid就是狒狒每小时吃香蕉速度的最小值。如果mid不为1那么继续判断以mid-1求出的时间time2与H如果time2大于H那么mid就是狒狒每小时吃香蕉速度的最小值。如果time2小于H那么狒狒吃香蕉的速度还可以慢点。如果time1大于H那么狒狒吃香蕉的速度应该快些。
源代码
class Solution {public int minEatingSpeed(int[] piles, int h) {int left 1;int right Integer.MIN_VALUE;for (int pile : piles) {right Math.max(right, pile);}while (left right) {int mid (left right) / 2;int midTime getTime(piles, mid);if (midTime h) {if (mid 1 || getTime(piles, mid - 1) h) {return mid;}right mid - 1;} else {left mid 1;}}return right;}//计算狒狒每个小时吃mid根所花费的时间private int getTime(int[] piles, int mid) {int time 0;for (int pile : piles) {time pile / mid;if (pile % mid ! 0) {time;}}return time;}
}
