二分法模板以及例题 (三)

167. 两数之和 II - 输入有序数组
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]。
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]
解题思路：首先散列表可以直接秒了，双指针也秒了
二分法是这里面性能不好的一种做法nlog(n),得遍历后找，其他两个O(n)

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {for(int i=0, j=numbers.size()-1;i<j;i++){int l =i+1,r =j;int mid;while(l<r){mid = (l+r+1)/2;if(numbers[i]+numbers[mid]>target)r=mid-1;else l=mid;}if(numbers[i]+numbers[l]==target)return {i+1,l+1};}return {};}
};

240. 搜索二维矩阵 II

解题思路：双指针秒了，ij从左下角开始，搜索二维矩阵I 是拍平二维数组然后二分，这题应该也是考虑如何拍平
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

这里也可以二分，分从这以后的版本都是错误，从这以前的版本可能正确的，直接使用二分法模板一

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left=0;int right=n;int mid=0;while(left<right){mid = (right - left) / 2 + left; if(isBadVersion(mid)){right=mid;}elseleft=mid+1;}return left;}
};

300. 最长递增子序列
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution {
public:int lengthOfLIS(vector<int>& nums) { int ans=1;int n=nums.size();vector<int>dp(n,1);for(int i=0;i<n;++i){for(int j=0;j<i;++j){if(nums[i]>nums[j]){dp[i]=max(dp[i],dp[j]+1);if(ans<dp[i])ans=dp[i];}}}return ans;}};

349. 两个数组的交集
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
611. 有效三角形的个数
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
658. 找到 K 个最接近的元素
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]