二分查找 —— 好多题好多题
50 Pow(x ,n)
题面：
思路：
题解：
class Solution { // lyy的天才解法
public:
double myPow(double x, int n) {
double ans = x;
for (int i = 0; i < n - 1; i++) {
ans *= x;
}
return ans;
}
};
class Solution { // 递归
public:
double quickMul(double x, long long N) {
if (N == 0) { // 递归出口
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x; // N为偶数时，直接返回平方；N为奇数时，返回平方乘x
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
class Solution {
public:
double quickMul(double x, long long N) {
double ans = 1.0;
double x_conribute = x; // 初始贡献值为x
while (N > 0) {
if (N % 2 == 1) {
ans *= x_conribute; // 如果N为奇数，则计入贡献
}
x_conribute *= x_conribute; // 贡献值平方
N /= 2;
}
return ans;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
367 有效的完全平方数
题面：
思路：
一个非负数的平方根不大于 num / 2 + 1
题解：
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 0, right = num / 2 + 1;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long)mid * mid;
if (square == num) {
return true;
}
if (square > num) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
};
744 寻找比目标字母大的最小字母
题面：
思路：
二分查找右边界类型 使用 left < right
题解：
class Solution {
public:
int findRightBorder(vector<char>& letters, char target) {
int left = 0, right = letters.size() - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (target < letters[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
char nextGreatestLetter(vector<char>& letters, char target) {
if (target >= letters.back()) { // 判断特殊情况
return letters[0];
}
int right_border = findRightBorder(letters, target);
return letters[right_border];
}
};
154 寻找旋转排序数组中的最小值 II
题面：
思路：
前几天写过 I，本题数组中存在重复元素
如果最右侧元素和 mid 相同，则让右侧元素减一
题解：
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right--; // nums[mid] == nums[right]时，right--
}
}
return nums[left];
}
};
349 两个数组的交集
题面：
思路：
先将数组进行排序，然后进行比较，使用双指针
初始时，指针指向第一个元素 当两个指针指向的元素相等时，记入返回数组（注意要判断元素不重复）
如果两个元素不相等，则指向较小元素的指针向右移动一位
题解：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int length1 = nums1.size();
int length2 = nums2.size();
int index1 = 0, index2 = 0;
vector<int> ret;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
if (!ret.size() || num1 != ret.back()) {
ret.push_back(num1);
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return ret;
}
};
350 两个数的交集 II
题面：
思路：
先将数组进行排序，然后进行比较，使用双指针
初始时，指针指向第一个元素
当两个指针指向的元素相等时，记入返回数组
如果两个元素不相等，则指向较小元素的指针向右移动一位
题解：
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> ret;
int index1 = 0, length1 = nums1.size();
int index2 = 0, length2 = nums2.size();
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
ret.push_back(num1);
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return ret;
}
};
167 两数之和 II - 输入有序数组
题面:
思路：
1、二分查找：
先固定数组中一个数，然后对剩下的数进行二分查找
如果查找到的值 = target - 固定的数，则返回（逆天）
2、双指针：
两个指针分别指向数组的头和尾
两数之和大于 target 时则尾指针减 1 两数之和小于 target 时则尾指针加 1
题解：
class Solution { // 二分法
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int length = numbers.size();
for (int i = 0; i < length; i++) {
int fixed_num = numbers[i];
int left = i + 1, right = length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (target - fixed_num == numbers[mid]) {
return {i + 1, mid + 1};
} else if (target - fixed_num > numbers[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return {-1, -1};
}
};
class Solution { // 双指针
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1};
} else if (sum > target) {
right--;
} else {
left++;
}
}
return {-1, -1};
}
};
287 寻找重复数
题面：
思路：
假如重复的数是 target，那么在[1, target - 1]里所有的数满足 count[i] <= i，[target, n]里所有的数满足 count[i] > i
使用二分法，确定记录 count，确定 target 在 mid 之前还是之后
题解：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int length = nums.size(), ans = -1;
int left = 1, right = length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
int count = 0; // 记录小于等于 mid 的个数，判断 target 和 mid 的关系
for (int i = 0; i < length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count <= mid) { // target 在 mid 右侧
left = mid + 1;
} else {
right = mid - 1; // target 在 mid 左侧
ans = mid;
}
}
return ans;
}
};
4 寻找两个正序数组的中位数
题面：
思路：
leetcode 官方解析：
在两个数组中找到一条分割线，分割线有三条性质：
1、分割线左侧的数应该有 (length1 + length2 + 1) / 2 个
2、中位数在分割线左侧第一个或者分割线左右两个的数的平均数
3、分割线左侧数严格小于右侧的数
题解：
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 保证数组1一定最短
if (nums1.size() > nums2.size()) {
vector<int> temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int length1 = nums1.size();
int length2 = nums2.size();
// 分割线左边的所有元素要满足的个数为 (length1 + length2 + 1) / 2
int totalLeft = (length1 + length2 + 1) / 2;
// 在nums1的区间[0, length1]里找恰当的分割线
// 使得nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums2[i]
int left = 0, right = length1;
while (left < right) {
int i = left + (right - left + 1) / 2;
int j = totalLeft - i;
if (nums1[i - 1] > nums2[j]) { // 第一个数组的分割线位置太靠右
right = i - 1; // 下一轮的寻找区间为[left, i - 1]
} else {
left = i; // 下一轮的寻找区间为[i, right]
}
}
int i = left;
int j = totalLeft - i;
int nums1_left_max = i == 0 ? INT32_MIN : nums1[i - 1];
int nums1_right_min = i == length1 ? INT32_MAX : nums1[i];
int nums2_left_max = j == 0 ? INT32_MIN : nums2[j - 1];
int nums2_right_min = j == length2 ? INT32_MAX : nums2[j];
if ((length1 + length2) % 2 == 1) {
return max(nums1_left_max, nums2_left_max);
} else {
return (double)(max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0;
}
}
};
719 找出第 k 小的距离对
题面：
思路：
先进行排序，使数组成为升序数组
距离的范围在[0, nums[nums.size() - 1]] 使用二分搜索，对于 mid，检查超过其的距离是否大于 k
题解：
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int min = 0, max = nums.back() - nums.front();
while (min < max) {
int mid = min + ((max - min) >> 1);
int count = 0;
for (int r = 0, l = 0; r < nums.size(); r++) {
while (l < r && nums[r] - nums[l] > mid) {
l++;
}
count += r - l;
}
if (count >= k) {
max = mid;
} else {
min = mid + 1;
}
}
return min;
}
410 分割数组的最大值
题面：
思路：
子数组的最大范围在[max(nums), sum(nums)]之中
计算数组和的最大值不大于 mid 对应的子数组个数 count(这个是关键！)
先猜一个 mid 值，然后遍历数组划分，使每个子数组和都最接近 mid（贪心地逼近 mid），这样我得到的子数组数一定最少;
如果即使这样子数组数量仍旧多于 m 个，那么明显说明我 mid 猜小了，因此 lo = mid + 1;
而如果得到的子数组数量小于等于 m 个，那么我可能会想，mid 是不是有可能更小？值得一试。因此 hi = mid;
题解：
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
long max_nums = nums[0], sum_nums = 0;
for (auto i : nums) {
sum_nums += i;
max_nums = max_nums > i ? max_nums : i;
}
while (max_nums < sum_nums) {
long mid = max_nums + ((sum_nums - max_nums) >> 1);
long temp = 0;
int count = 1;
for (auto i : nums) {
temp += i;
if (temp > mid) {
temp = i;
count++;
}
}
if (count > m) {
max_nums = mid + 1;
} else {
sum_nums = mid;
}
}
return sum_nums;
}
};