代码拉取完成，页面将自动刷新
ps:二分法一定要牢记3个经常用的模板，注意边界检测。
3个模板代码区别很小，主要在于找到target之后指针的处理，建议比较target时的大于小于等于三种情况都写出来进行讨论，不易搞混淆，还要牢记左右指针的越界时的处理。while循环里时<=符号，while循环结束后right指针在前，left指针在后。
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
//直接返回
right = mid - 1;
} else if(nums[mid] == target) {
return mid;
}
}
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) { //此处注意区别
// 别返回，收缩左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) { //此处注意区别
// 别返回，收缩右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
leetcode给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。
nums[mid] == target时对指针的操作不同:找左边界就要不断往左压缩即右指针不断往左走right = mid - 1;，函数最后返回左指针，找右边界不断往右压缩即左指针不断往右走left = mid + 1，函数返回右指针 vector<int> searchRange(vector<int>& nums, int target) {
int left = findLeft(nums, target);
int right = findRight(nums, target);
return {left, right};
}
int findLeft(vector<int>& nums, int target){
int left = 0;
int right = nums.size()-1;
while (left <=right) {
int mid = left + (right - left)/2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
right = mid - 1;
}
}
if (left >= nums.size() || nums[left] != target) return -1;
return left;
}
int findRight(vector<int>& nums, int target){
int left = 0;
int right = nums.size()-1;
while (left <=right) {
int mid = left + (right - left)/2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (right < 0 || nums[right] != target) return -1;
return right;
}
leetcode实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
right < left，如果x平方根不是整数，那么将会处于(r, l)指针区间内，所以只保留整数意味着返回r所指的数。mid * mid == x 改为 mid == x / mid。 int mySqrt(int x) {
int left = 1, right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid == x / mid) {
return mid;
} else if (mid < x / mid){
left = mid + 1;
} else if (mid > x / mid) {
right = mid -1 ;
}
}
return right;
}
leetcode假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int target = nums[right];
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
right = mid - 1;
} else if (nums[mid] > target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums[left];
}
leetcode 整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
nums[0] <= nums[mid]或者nums[n-1] >= nums[mid]就能判断当前mid是否在有序的那一边 int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
if (nums.size() == 1) return nums[0] == target ? 0 : -1;
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) return mid;
if (nums[0] <= nums[mid]) { /// 左边有序
if (nums[left] <= target && nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { /// 右边有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
leetcode给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
target - nums[i]即可 vector<int> twoSum(vector<int>& numbers, int target) {
for (int i = 0; i < numbers.size(); ++i) {
int num2 = target - numbers[i];
int index2 = binarySearch(numbers, i, num2);
if (index2 != -1) return {i + 1 , index2 + 1};
}
return {};
}
int binarySearch(vector<int>& numbers, int index1, int target) {
int left = 0, right = numbers.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) {
if (mid != index1){
return mid;
} else {
left = mid + 1;
}
} else if (numbers[mid] < target) {
left = mid + 1;
} else if (numbers[mid] > target) {
right = mid - 1;
}
}
return -1;
}
leetcode你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
int firstBadVersion(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (!isBadVersion(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
leetcode给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。 在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"
输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
[right, left)区间内，因为是往右压缩，所以如果数组中存在目标字母，那就是right所指的字母，如果不存在，目标字母一定在right和left所指的字母之间。但题目要求找比目标字母稍大的字母，所以left所指正好满足。所以返回值要返回left指针。 char nextGreatestLetter(vector<char>& letters, char target) {
int left = 0, right = letters.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (letters[mid] == target) {
left = mid + 1;
} else if (letters[mid] < target) {
left = mid + 1;
} else if (letters[mid] > target) {
right = mid - 1;
}
}
return left >= letters.size() ? letters[0] : letters[left]
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。