二分模板
62. Search in Rotated Sorted Array
先看是否反序，再分6种情况讨论
class Solution {public:/*** @param A: an integer rotated sorted array* @param target: an integer to be searched* @return: an integer*/int search(vector<int> &A, int target) {// write your code hereif (A.size() == 0){return -1;}int left = 0, right = A.size() - 1;while(left + 1 < right){int mid = left + (right - left) / 2;if (A[left] < A[right]){if (A[mid] < target){left = mid;}else{right = mid;}}else{if ((A[mid] < target && target < A[0]) || (A[mid] >= A[0] && A[mid] < target) || (A[mid] > A[left] && A[left ] > target)){left = mid;}else{right = mid;}}}if (A[left] == target){return left;}else if (A[right] == target){return right;}else{return -1;}}};
460. Find K Closest Elements
int low = lower_bound(A.begin(),A.end(),target) - A.begin();
class Solution {public:/*** @param A: an integer array* @param target: An integer* @param k: An integer* @return: an integer array*/vector<int> kClosestNumbers(vector<int> &A, int target, int k) {// write your code here//int i = 0, end = A.size() - 1;int low = lower_bound(A.begin(),A.end(),target) - A.begin();//cout << low;int pos = 0;vector <int> res;if (low > 0 && A[low] - target > target - A[low - 1]){pos = low - 1;}else{pos = low;}if (pos == 0){vector <int> res(A.begin(), A.begin() + k);return res;}else if(pos == A.size() || pos == A.size() - 1){vector <int> res(A.end() - k, A.end());reverse(res.begin(), res.end());return res;}else{int left = low - 1, right = low, count = 0;while(left >= -1 && right <= A.size() && count < k){if (left == -1){res.push_back(A[right]);right ++;}else if (right == A.size()){res.push_back(A[left]);left --;}else{if (A[right] - target >= target - A[left]){res.push_back(A[left]);left --;}else{res.push_back(A[right]);right ++;}}count ++;}}return res;}};
140. Fast Power
计算机计算在一个较大的容器中进行，最后再进行截取。
class Solution {
public:
/**
* @param a: A 32bit integer
* @param b: A 32bit integer
* @param n: A 32bit integer
* @return: An integer
*/
int fastPower(int a, int b, int n) {
// write your code here
int temp = n;
a = a % b;
long powNow = a;
long res = 1;
if (b == 1){
return 0;
}
if (n == 0){
return 1;
}
while(temp != 0){
if (temp % 2 == 1){
//cout << temp << endl;
temp --;
//cout << powNow << endl;
res = (res * powNow) % b;
//cout << res << endl;
// powNow *= a;
}
powNow = (powNow * powNow) % b;
//powNow = powNow % b;
temp /= 2;
}
return res;
}
};
141. Sqrt(x)
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
// write your code here
long left = 1, right = x;
while(left + 1 < right){
long mid = left + (right - left)/2;
if(x > mid * mid){
left = mid;
}else if (x < mid * mid){
right = mid;
}else{
return mid;
}
}
if (right * right <= x){
return right;
}
return left;
}
};
586. Sqrt(x) II
class Solution {
public:
/**
* @param x: a double
* @return: the square root of x
*/
double sqrt(double x) {
// write your code here
double left = 0, right = max (1.0, x);
double eps = 1e-12;
while (left + eps < right){
double mid = left + (right - left) / 2;
if (mid * mid < x){
left = mid;
}else {
right = mid;
}
}
if (right * right < x){
return right;
}
return left;
}
};
617. Maximum Average Subarray II
#include <float.h>
class Solution {
public:
/**
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
bool isRight(double res, vector <int> nums, int k) {
vector <double> newNums(nums.size());
vector<double> preSum(nums.size(), DBL_MAX);
vector <double> minPreSum(nums.size());
newNums[0] = nums[0] - res;
preSum[0] = nums[0] - res;
minPreSum[0] = nums[0] - res;
for (int i = 1; i < nums.size(); i++) {
newNums[i] = nums[i] - res;
preSum[i] = preSum[i - 1] + newNums[i];
minPreSum[i] = min(preSum[i], minPreSum[i - 1]);
//cout << minPreSum[i] << ' ' << res << endl;
}
if (preSum [k - 1] > 0){
return true;
}
for (int i = k; i < nums.size(); i++) {
if (preSum[i] - minPreSum[i - k] > 0 || preSum[i] > 0) {
return true;
}
}
return false;
}
double maxAverage(vector<int> &nums, int k) {
// write your code here
if (nums.size() == 0) {
return 0.0;
}
double accuracy = 1e-4;
int minimum = nums[0], maximum = nums[0];
for (int i = 0; i < nums.size(); i++) {
minimum = min(minimum, nums[i]);
maximum = max(maximum, nums[i]);
}
double start = minimum, end = maximum;
while (start + accuracy < end) {
double mid = start + (end - start) / 2;
if (isRight(mid, nums, k)) {
start = mid;
}
else {
end = mid;
}
}
return end;
}
};
437. Copy Books
class Solution {
public:
/**
* @param pages: an array of integers
* @param k: An integer
* @return: an integer
*/
bool isExist(vector<int> &pages, int k, int tempRes){
int pointer = 0;
for (int i = 0; i < k; i ++){
if (pointer == pages.size()){
return true;
}
int perRes = 0;
while (perRes + pages[pointer] <= tempRes){
perRes += pages[pointer];
pointer ++;
if (pointer == pages.size()){
return true;
}
}
}
return false;
}
int copyBooks(vector<int> &pages, int k) {
// write your code here
int tempRes = 0;
int sum = 0;
int start = 0;
for (int i = 0; i < pages.size(); i ++){
sum = sum + pages[i];
}
int end = sum;
while (start + 1 < end){
int mid = start + (end - start) / 2;
//cout << mid << endl;
if (isExist(pages, k, mid)){
end = mid;
}else{
start = mid;
}
}
if (isExist(pages, k, start)){
return start;
}
return end;
}
};
633. Find the Duplicate Number
class Solution {
public:
/**
* @param nums: an array containing n + 1 integers which is between 1 and n
* @return: the duplicate one
*/
int findDuplicate(vector<int> &nums) {
// write your code here
vector <int> newVec = nums;
sort(newVec.begin(), newVec.end());
int start = 0, end = nums.size() - 1;
while (start + 1 < end){
int mid = start + (end - start) / 2;
cout << mid << endl;
if (newVec[mid] * 2 >= (newVec[start] + newVec[end])){
start = mid;
}else{
end = mid;
}
}
return newVec[start];
}
};
438. Copy Books II
class Solution {
public:
/**
* @param n: An integer
* @param times: an array of integers
* @return: an integer
*/
bool isExist(int n, vector<int> & times, int temp){
int res = 0;
for (int i = 0; i < times.size(); i ++){
res += temp / times[i];
}
if (res >= n){
return true;
}
return false;
}
int copyBooksII(int n, vector<int> ×) {
// write your code here
int temp = 0, end = INT_MAX;
for (int i = 0; i < times.size(); i ++){
end = min(end, times[i]);
}
end = end * n;
int start = 0;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (isExist(n, times, mid)){
end = mid;
}else{
start = mid;
}
}
if (isExist(n, times, start)){
return start;
}
return end;
}
};
183. Wood Cut
class Solution {
public:
/**
* @param L: Given n pieces of wood with length L[i]
* @param k: An integer
* @return: The maximum length of the small pieces
*/
bool isExist(vector<int> &L, int k, int mid){
int res = 0;
for (int i = 0; i < L.size(); i ++){
res += L[i] / mid;
}
if (res >= k){
return true;
}
return false;
}
int woodCut(vector<int> &L, int k) {
// write your code here
int start = 0, end = 0;
for (int i = 0; i < L.size(); i ++){
end = max(end, L[i]);
}
while(start + 1 < end){
int mid = start + (end - start) / 2;
if (isExist(L, k, mid)){
start = mid;
}else{
end = mid;
}
}
if (isExist(L, k, end)){
return end;
}
return start;
}
};
若有收获，就点个赞吧
0 人点赞
