lt75 Find Peak Element
lt390 Find Peak Element II
lt141 Sqrt(x)
lt586 Sqrt(x) II 注意判断x与1的大小关系
二分答案 步骤：确定答案范围 找一个验证答案的方法。 时间复杂度O(log(n)*(验证一个答案的事件))
lt183 Wood Cut 答案范围 1 - maxlength；验证函数 是否能切大于等于k段
lt437 Copy Books 答案范围 最大页数 - 全部页数和；验证函数 是否能少于等于k个人完成
lt633 Find the Duplicate Number 答案范围 1 - n； 验证函数 小于等于该元素的元素个数是否小于等于该元素本身
lt75 Find Peak Element O(logn)
public class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
// write your code here
int left = 0;
int right = A.length-1;
while(left+1<right){
int mid = left+(right-left)/2;
if(A[mid]>A[mid+1] && A[mid]>A[mid-1])
return mid;
if(A[mid]>A[mid+1] && A[mid]<A[mid-1])
right = mid;
else
left = mid;
}
return A[left]>A[right] ? left : right;
}
}
lt390 Find Peak Element II
下面给出的是O(nlogn)解法
还能更快到O(n) 横竖横竖切割
public class Solution {
/*
* @param A: An integer matrix
* @return: The index of the peak
*/
public List<Integer> findPeakII(int[][] A) {
// write your code here
List<Integer> result = new ArrayList<>();
if(A==null || A.length==0 || A[0]==null || A[0].length==0)
return result;
for(int i=1; i<A.length-1; i++){
int index = findPeak(A[i]);
if(A[i][index]>A[i-1][index] && A[i][index]>A[i+1][index]){
result.add(i);
result.add(index);
return result;
}
}
return result;
}
public int findPeak(int[] A) {
// write your code here
int left = 0;
int right = A.length-1;
while(left+1<right){
int mid = left+(right-left)/2;
if(A[mid]>A[mid+1] && A[mid]>A[mid-1])
return mid;
if(A[mid]>A[mid+1] && A[mid]<A[mid-1])
right = mid;
else
left = mid;
}
return A[left]>A[right] ? left : right;
}
}
lt141 Sqrt(x)
public class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
int left = 0;
int right = x;
while(left+1<right){
int mid = left+(right-left)/2;
if(mid>x/mid){
right = mid;
}else if(mid<x/mid){
left = mid;
}else{
return mid;
}
}
//注意这里是向下取整（题目要求）
if(right*right==x)
return right;
return left;
}
}
lt586 Sqrt(x) II
public class Solution {
/**
* @param x: a double
* @return: the square root of x
*/
public double sqrt(double x) {
// write your code here
double left = 0;
double right = Math.max(1.0, x);
double eps = 1e-12;
while(left+eps<right){
double mid = left+(right-left)/2;
if(mid>x/mid){
right = mid;
}else if(mid<x/mid){
left = mid;
}else{
return mid;
}
}
return left;
}
}
lt183 Wood Cut 答案范围 1 - maxlength
public class Solution {
/**
* @param L: Given n pieces of wood with length L[i]
* @param k: An integer
* @return: The maximum length of the small pieces
*/
public int woodCut(int[] L, int k) {
// write your code here
if(L==null || L.length==0 || k<=0)
return 0;
int max = findMax(L);
int left = 1;
int right = max;
while(left+1<right){
int mid = left+(right-left)/2;
if(valid(mid, L, k)>=k){
left = mid;
}else{
right = mid;
}
}
if(valid(right, L, k) >= k)
return right;
if(valid(left, L, k) >= k)
return left;
return 0;
}
private int findMax(int[] L){
int max = L[0];
for(int i=0; i<L.length; i++){
max = Math.max(max, L[i]);
}
return max;
}
private int valid(int value, int[] L, int k){
int count = 0;
for(int i : L){
count = count + i/value;
}
return count;
}
}
lt437 Copy Books 答案范围 最大页数 - 全部页数和
public class Solution {
/**
* @param pages: an array of integers
* @param k: An integer
* @return: an integer
*/
public int copyBooks(int[] pages, int k) {
// write your code here
int min = findMax(pages);
int max = getSum(pages);
while(min+1<max){
int mid = min + (max-min)/2;
if(peopleNeed(pages, mid) >k){
min = mid;
}else{
max = mid;
}
}
if(peopleNeed(pages, min)<=k)
return min;
return max;
}
private int peopleNeed(int[] pages, int hour){
int count = 0;
int sum = 0;
for(int i=0; i<pages.length; i++){
if(sum+pages[i]>hour){
sum = pages[i];
count++;
}else if(sum+pages[i]==hour){
sum = 0;
count++;
}else{
sum = sum+pages[i];
}
}
if(sum>0)
count++;
return count;
}
private int findMax(int[] pages){
int max = 0;
for(int i: pages){
max = Math.max(max, i);
}
return max;
}
private int getSum(int[] pages){
int sum = 0;
for(int i: pages){
sum = sum + i;
}
return sum;
}
}
lt633 Find the Duplicate Number
public class Solution {
/**
* @param nums: an array containing n + 1 integers which is between 1 and n
* @return: the duplicate one
*/
public int findDuplicate(int[] nums) {
// write your code here
if(nums==null || nums.length==0)
return -1;
int n = nums.length-1;
int left = 1;
int right = n;
while(left+1<right){
int mid = left+(right-left)/2;
if(lessOrEqual(mid, nums)<=mid){
left = mid;
}else{
right = mid;
}
}
if(lessOrEqual(left, nums)>left)
return left;
return right;
}
private int lessOrEqual(int num, int[] nums){
int count = 0;
for(int i: nums){
if(i<=num)
count++;
}
return count;
}
}
网友评论