#include<vector> usingnamespace std; classSolution { public: intsearch(vector<int> &nums, int target){ /*int start = 0; int end = nums.size() - 1; while (end >= start) { if (nums[(end + start) / 2] < target) { start = (end + start) / 2 + 1; } else if (nums[(end + start) / 2] > target) { end = (end + start) / 2 - 1; } else return (end + start) / 2; } return -1;*/ // 47/47 cases passed (36 ms) // Your runtime beats 30.04 % of cpp submissions // Your memory usage beats 16.35 % of cpp submissions (27 MB) //!他妈的要注意左边的+1和右边的-1 int left = 0; int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right] while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <= int middle = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2 if (nums[middle] > target) { right = middle - 1; // target 在左区间,所以[left, middle - 1] } elseif (nums[middle] < target) { left = middle + 1; // target 在右区间,所以[middle + 1, right] } else { // nums[middle] == target return middle; // 数组中找到目标值,直接返回下标 } } // 未找到目标值 return-1; // 47/47 cases passed (28 ms) // Your runtime beats 80.11 % of cpp submissions // Your memory usage beats 16.35 % of cpp submissions (27 MB) //把(end + start) / 2打包成middle更快 } };
278.第一个错误的版本
c++
// The API isBadVersion is defined for you. // bool isBadVersion(int version);
classSolution { public: intfirstBadVersion(int n){ if (isBadVersion(1)) return1; int left = 1; int right = n; while (right > left + 1) { int middle = left + (right - left) / 2; if (isBadVersion(middle)) { right = middle; } else { left = middle; } } return right; // 22/22 cases passed (0 ms) // Your runtime beats 100 % of cpp submissions // Your memory usage beats 39.66 % of cpp submissions (5.9 MB) //!注意第一个是不是坏版本 } };
35.搜索插入位置
以前做的又优化了一遍,记住了二分查找的解题思路了以后快很多(指写代码快很多)
c++
#include<iostream> #include<vector> usingnamespace std; classSolution { public: intsearchInsert(vector<int> &nums, int target){ int left = 0, right = nums.size() - 1; while (right >= left) { int middle = left + (right - left) / 2; if (nums[middle] > target) right = middle - 1; elseif (nums[middle] < target) left = middle + 1; else return middle; } return left; // 64/64 cases passed (4 ms) // Your runtime beats 78.56 % of cpp submissions // Your memory usage beats 72.89 % of cpp submissions (9.4 MB) //老版本 /*if (nums.at(0) > target) { nums.push_back(nums.at(nums.size() - 1)); for (int i = nums.size() - 1; i > 0; i--) { nums.at(i) = nums.at(i - 1); } nums.at(0) = target; return 0; } for (int i = 0; i < nums.size(); i++) { if (nums.at(i) == target) { return i; } if (nums.at(i) > target && nums.at(i - 1) < target) { nums.push_back(nums.at(nums.size() - 1)); for (int j = nums.size() - 1; j >= i + 1; j--) { nums.at(j) = nums.at(j - 1); } nums.at(i) = target; return i; } } if (nums.at(nums.size() - 1) < target) { nums.push_back(target); return nums.size() - 1; } return -1;*/ // 62/62 cases passed (4 ms) // Your runtime beats 88.27 % of cpp submissions // Your memory usage beats 74.81 % of cpp submissions (9.3 MB) // FinishedTODO:代码有些复杂,有空的时候优化一下代码 } };