二分

二分模板 1.二分模板二分的本质并不是单调性，而是一种边界。 定义某种性质，使得右半边的部分全部满足该种性质，而左半边的部分全部都不满足该种性质。而二分可以寻找性质的边界。 12345678910111213141516171819//区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:while (low < high) { int mid = low + high + 1 >> 1; if (check(mid)) low = mid; else high = mid - 1;}//区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:while (low < high) { int mid = low + high >> 1; if (check(mid)) high = mid;//check判断mid是否满足性质 else low = mid + 1;}//小数二分const double eps = 1e-6;//eps表示精度 取决于题目对精度的要求while (high - low > 1e-8) { double mid = (low + high) / 2; if (check(mid)) low = mid; else high = mid;} 1.AcWing789.数的范围 123456789101112131415161718192021222324252627282930313233343536373839#include<iostream>using namespace std;const int MAX = 1e6 + 10;int n, m, arr[MAX];//整数二分模板//思路：对数组进行二分 分别查找某个数字出现范围的起始坐标与终止坐标int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", ...

第一个错误的版本 原题链接：https://leetcode.cn/problems/first-bad-version/ 你是产品经理，目前正在带领一个团队开发新的产品。 不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。 实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 1.二分答案01123456789101112131415class Solution {public: int firstBadVersion(int n) { long long l = 1, r = n; while (l != r) { long long mid = (l + r) /2; if (isBadVersion(mid)) { r = mid; } else { l = mid + 1; } } return l; }};

x的平方根 原题链接：https://leetcode.cn/problems/sqrtx/ 给你一个非负整数 x ，计算并返回 x 的 算术平方根。 由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。 注：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 1.二分答案10123456789101112131415class Solution {public: int mySqrt(int x) { long long l = 0, r = x; while (l != r) { long long mid = (r + l + 1) / 2; if (mid * mid <= x) { l = mid; } else { r = mid - 1; } } return r; }};

两数之和 原题链接：https://leetcode.cn/problems/two-sum/ 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }}; 2.二分查找思想：sort排序 + 二分查找 使用for循环遍历数组中的每一个数字 在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret 如果找到该数字则直接输出其下标(初始若有序的情况下) 实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？ 1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;} 12345678910111213141516171819202122 ...

吃瓜群众 原题链接：http://oj.haizeix.com/problem/386 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M 堆瓜中查找对应数量的一堆瓜，并输出那堆瓜的编号，若找不到对应数量的一堆，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为对应数量的瓜的编号，若没有对应数量的瓜，则输出 0。 样例： 1235 31 3 26 7 1526 99 3 123302 1.参考解答思路1：暴力查找，每一组群众都对瓜堆进行遍历，时间复杂度为O(n^2)必超时 思路2： 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 利用sort函数对node自定义类型按照瓜的数量num进行排序 二分查找在瓜堆中查找，如果找到输出瓜堆数量num，否则输出0 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<iostream>#include<algorithm>#include<cstring>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cnt < b.cnt;}int main(){ int n, m; //2.进行瓜堆信息的录入 scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i)& ...

吃瓜群总升级版 原题链接：http://oj.haizeix.com/problem/387 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M堆瓜中查找大于等于需要数量的第一堆瓜，并输出那堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为大于等于需要数量的第一堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 样例： 1235 51 3 26 7 1527 10 3 4 2 1234505242 1.思路分析二分查找特殊情况的探讨01： 二分查找特殊情况的探讨10： 2.参考解答 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 若所有瓜堆的数量均小于需要数量输出0，否则输出大于等于需要数量的第一堆瓜的编号 方法1：建立一个最大虚拟瓜堆并将瓜堆数量置为0，当正常瓜堆中没有瓜堆满足条件时输出虚拟瓜堆数量 方法2：用最大的瓜堆的瓜数量判断，如果最大瓜堆数量大于需求则有答案进行二分，否则直接输出0 利用sort函数对node自定义类型按照瓜的数量num进行排序 利用二分查找在瓜堆中查找，如果找到输出瓜堆数量num 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<algorithm>#include<cstdio>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cn ...

OnlineJ两数之和 原题链接：http://oj.haizeix.com/problem/599 题目描述 给定一个从小到大的数组和一个目标数t，在其中找到两个数，使得两数之和与目标数相等，输出两个数在数组中的位置。 输入 第一行输入两个整数 n, t（1 ≤ n ≤ 1000000, 1 ≤ t ≤ 20000000） 接下来一行 n 个数，均小于10,000,000 输出 输出两个用空格隔开的数表示位置（从零开始计数），答案有唯一解 126 151 5 6 7 10 26 11 4 1.暴力法：1234567891011121314151617181920212223#include<iostream>#include<cstdio>using namespace std;int num[1000005];int n, target;int main() { scanf("%d%d", &n, &target); for (int i = 0; i < n; ++i) { scanf("%d", &num[i]); } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (num[i] + num[j] == target) { cout << i << " " << j << endl; return 0; } } } cout << "not fimd" << endl; return 0;} 注意：由于数据范围(1≤n≤1000000, 1≤t≤20000000)，暴力枚举的时间复杂度为O(n^2)一定会超时，空间复杂度为O(1) 2.二分法：=&# ...