电脑网站安全证书有问题如何解决百度收录批量查询工具

当前位置： 首页 > news >正文

电脑网站安全证书有问题如何解决,百度收录批量查询工具,扬州做企业网站哪家公司好,不会做网站#1024程序员节#xff5c;征文# 正文#xff1a; 二分查找#xff08;binary search#xff09;是一种基于分治策略的高效搜索算法。它利用数据的有序性#xff0c;每轮缩小一半搜索范围#xff0c;直至找到目标元素或搜索区间为空为止#xff0c;其实有时候数据没有序…#1024程序员节征文# 正文 二分查找binary search是一种基于分治策略的高效搜索算法。它利用数据的有序性每轮缩小一半搜索范围直至找到目标元素或搜索区间为空为止其实有时候数据没有序也能用二分查找思想解题遇到具体的题我们具体分析。 我们要想搞清楚二分查找的思想是什么就需要结合具体的题目进行理解单单靠定义是不行的下面让我们进入刷题的节奏吧 一、二分查找 704. 二分查找 - 力扣LeetCode 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target  写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2: 输入: nums [-1,0,3,5,9,12], target 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1提示 你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。 这道题用暴力解法是很好写的只需从前向后遍历数组若找到返回下标否则返回-1。它的时间复杂度为O(N)。 这道题的题目就是二分查找我们以这个题为代表引出二分查找的思想。 首先这道题目中的数组是升序的那么给你一个target目标值要查找target对应的下标。 我们可以先拿到数组中间的数(nums[mid])让这个数与target作比较 1、如果相等就直接返回它的下标(mid)即可。 2、如果nums[mid]大于target因为是升序那么后面的值必定大于target所以只需在[0,mid-1]这个区间找即可(这样数据的范围就减少一半了)。 3、如果nums[mid]小于target因为是升序那么前面的值必定小于target所以只需在[mid1,n)这个区间找即可(n为元素个数,这样数据的范围也减少一半)。 如果数据量是100w比较一次如果运气好就直接找到如果运气不好我比较一次就可以减少50w的数据量可想而知这个算法如果适合使用那是非常厉害的。 可能会有人问可以从1/3的位置或1/4的位置处找一个数进行比较可以吗 答案是可以的但是这可能不会太稳定以1/3位置为例运气好可能一次过滤掉大部分数据(³⁄₄)运气不好可能就只过滤掉1/4的数据。 经过大量研究认为还是取中间的数更优。 回到这题代码实现 class Solution { public:int search(vectorint nums, int target) {int left 0,rightnums.size()-1;while(left right) //这里不是而是因为leftright时对应的值可能就是目标值{int mid (right-left)/2 left; //中间位置下标if(nums[mid] target)right mid-1; //只需更新rightelse if(nums[mid] target)left mid1; //只需更新leftelsereturn mid;}return -1; //没有找到的情况} }; 这道题的代码实现非常简单但有一个点需要说明一下就是求中间位置的下标。 一些同学可能会这样写 int mid (left right) / 2; 这样写会面临一个问题当left和right数极大时它们两个相加可能会超出int最大值这样计算出的mid就不正确了我们改写为上面的形式就不会出现越界的情景。 还需注意一个点 对于本题这两种写法写任意一个都可以。  二分查找的时间复杂度分析 时间复杂度为logN的算法可比时间复杂度为N的厉害太多了。  1024个数据时间复杂度为N的算法最多需要找1024次时间复杂度为logN的算法最多只需要找10次。 1024*1024个数据(大约100万)时间复杂度为N的算法最多需要找100w次时间复杂度为logN的算法最多只需要找20次。 二、在排序数组中查找元素的第一个和最后一个位置 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [5,7,7,8,8,10], target 8 输出[3,4] 示例 2 输入nums [5,7,7,8,8,10], target 6 输出[-1,-1] 示例 3 输入nums [], target 0 输出[-1,-1]提示 0 nums.length 10^5-10^9  nums[i]  10^9nums 是一个非递减数组-10^9  target  10^9 这道题的暴力解法是很好想出来的遍历数组首次遇到target记录它的下标然后接着遍历记录最后一个值为target的下标最后返回即可。 暴力解法代码实现 //暴力解法 class Solution { public:vectorint searchRange(vectorint nums, int target) {int nnums.size();vectorint ret;for(int i0;in;i){if(nums[i]target)ret.push_back(i);}if(ret.empty())return {-1,-1};return {ret[0],ret[ret.size()-1]};} }; 这道题可以直接用二分查找吗 这道题可以用二分查找思想但是不能直接套用第一题的模板样式分析 这道题为什么可以用二分思想呢那么如何使用二分查找思想呢 分析(以示例1为例) 别的一些细节请大家在代码实现中仔细品味。  代码实现 //二分思想 class Solution { public:vectorint searchRange(vectorint nums, int target) {if(nums.empty())return {-1,-1};vectorint ret;//1、二分左端点int left 0,rightnums.size()-1; while(left right){int mid (right-left)/2 left;if(nums[mid] target)left mid1;elseright mid;}if(nums[left] ! target) return{-1,-1};ret.push_back(left);//2、二分右端点left 0,right nums.size()-1;while(leftright){int mid (right-left1)/2left;if(nums[mid] target)right mid-1;elseleft mid;}ret.push_back(right);return ret;} }; 三、搜索插入位置 35. 搜索插入位置 - 力扣LeetCode 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2示例 2: 输入: nums [1,3,5,6], target 2 输出: 1示例 3: 输入: nums [1,3,5,6], target 7 输出: 4提示: 1 nums.length 10^4-10^4 nums[i] 10^4nums 为 无重复元素 的 升序 排列数组-10^4 target 10^4 这道题其实和第二题本质上是一样的只是换一种形式和说法就是第二题中求左端点的下标的问题。因为nums是无重复元素的升序排列数组可以实现分段所以就是第二题的变形我们直接上代码 //二分思想 class Solution { public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(left right){int mid (right-left)/2left;if(nums[mid] target)leftmid1;elserightmid;}if(nums[right] target) //处理特殊情况应对示例3出现的情况return right1;return right;} }; 它的复杂度也符合题目中的O(logN)。  四、x 的平方根 69. x 的平方根 - 力扣LeetCode 给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1 输入x 4 输出2示例 2 输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。提示 0 x 2^31 - 1 这道题的暴力解法就是从1开始遍历看看哪个数的平方等于x就返回如果大于x就返回一个数。 经过前面几个题的解题过程这道题不就是第二道题中求右端点位置下标的变形嘛。想象数组中的元素从1到x简直不要太一样了直接上代码 class Solution { public:int mySqrt(int x) {int left 1,right x;while(leftright){long long mid (right-left1)/2left; if(mid*mid x) //为了防止溢出mid的类型用long longright mid-1;elseleft mid;}return right;} };五、山脉数组的峰顶索引 852. 山脉数组的峰顶索引 - 力扣LeetCode 给定一个长度为 n 的整数 山脉 数组 arr 其中的值递增到一个 峰值元素 然后递减。 返回峰值元素的下标。 你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。 示例 1 输入arr [0,1,0] 输出1示例 2 输入arr [0,2,1,0] 输出1示例 3 输入arr [0,10,5,2] 输出1提示 3 arr.length 10^50 arr[i] 10^6题目数据 保证 arr 是一个山脉数组 这道题用暴力解法就是从头遍历数组如果当前数比后一个大那么这个数就是峰值返回其下标即可。 暴力解法代码 class Solution { public:int peakIndexInMountainArray(vectorint arr) {int n arr.size();// 遍历数组内每⼀个元素直到找到峰顶for (int i 1; i n - 1; i)// 峰顶满⾜的条件if (arr[i] arr[i - 1] arr[i] arr[i 1])return i;// 为了处理 oj 需要控制所有路径都有返回值return -1;} }; 这道题中的数组是可以分段的分析如下 这道题的本质就是第二道题求左端点问题。 代码如下: //二分思想 class Solution { public:int peakIndexInMountainArray(vectorint arr) {int narr.size();int left 1,rightn-2; //峰顶不可能是第一个元素和最后一个元素while(left right){int mid (right-left)/2left;if(arr[mid] arr[mid1])left mid1;elseright mid;}return left;} }; 时间复杂度满足O(logN)。  六、 寻找峰值 162. 寻找峰值 - 力扣LeetCode 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] nums[n] -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 示例 1 输入nums [1,2,3,1] 输出2 解释3 是峰值元素你的函数应该返回其索引 2。 示例 2 输入nums [1,2,1,3,5,6,4] 输出1 或 5 解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5 其峰值元素为 6。提示 1 nums.length 1000-2^31 nums[i] 2^31 - 1对于所有有效的 i 都有 nums[i] ! nums[i 1] 经过题目描述这道题会有以下几种情况 我们可以将以上3中情况抽象为2种 代码实现 //二分思想 class Solution { public:int findPeakElement(vectorint nums) {int n nums.size();int left0,rightn-1;while(leftright){int mid (right-left)/2left;if(nums[mid]nums[mid1])left mid 1;elseright mid;}return left;} }; 时间复杂度满足O(logN)。   五、六两题种数据并没有序我们也能用二分查找思想解题所以我们不要将二分思想局限到只能在有序数组中去运用。 七、寻找旋转排序数组中的最小值 153. 寻找旋转排序数组中的最小值 - 力扣LeetCode 已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到 若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7] 注意数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [3,4,5,1,2] 输出1 解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2 输入nums [4,5,6,7,0,1,2] 输出0 解释原数组为 [0,1,2,4,5,6,7] 旋转 3 次得到输入数组。示例 3 输入nums [11,13,15,17] 输出11 解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示 n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转 这道题的暴力解法是遍历数组如果当前值比下一个值大就返回下一个元素如果遍历完没有找到就返回第一个元素。暴力解法的时间复杂度是O(N)。 这道题很明显有分段情况我们可以考虑用二分思想 这道题本质上就是第二题中的求左端点问题。 代码实现 //二分思想(以D为基准) class Solution { public:int findMin(vectorint nums) {int nnums.size();int base nums[n-1]; //以最后一个元素为基准值int left0,rightn-1;while(leftright){int mid (right-left)/2left;if(nums[mid] base)leftmid1;elseright mid;}return nums[left]; } }; 以D为基准值这段代码可以应对旋转后保持不变的情况。  我们也可以以A为基准值 //二分思想(以A为基准) class Solution { public:int findMin(vectorint nums) {int nnums.size();int base nums[0]; //以第一个元素为基准值int left0,rightn-1;while(leftright){int mid (right-left)/2left;if(nums[mid] base)rightmid;elseleft mid1;}if(n 1 || nums[left]nums[left-1]) //处理旋转后保持不变的情况以及数组只有一个元素的情况return nums[0];return nums[left];} }; 时间复杂度满足O(logN)。 八、点名 LCR 173. 点名 - 力扣LeetCode 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席请返回他的学号。 示例 1: 输入: records [0,1,2,3,5] 输出: 4示例 2: 输入: records [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7提示 1 records.length  10000 这个题的解题方法有很多 1、异或法 开一个n个元素的数组记录从0~n-1的所有值。新数组中所有数和records中所有元素异或异或是同0不1所有异或后剩下的那个值就是缺席同学的学号。 代码实现 //异或法 class Solution { public:int takeAttendance(vectorint records) {int ret0; //记录最终结果int n records.size()1;vectorint tmp(n); //新开的数组for(int i0;in;i)tmp.push_back(i);for(auto e: records)ret^e;for(auto e:tmp)ret^e;return ret;} }; 代码还可以更简洁  //异或法 class Solution { public:int takeAttendance(vectorint records) {int ret0;int n records.size();for(int i0;i n;i){if(i n)ret ret ^ records[i] ^ i;elseret^i;}return ret;} }; 2、 数学法(高斯求和) 利用高斯求和公式求出0~n-1所有数的和然后减去records中所有元素相加的和结果就是缺席同学的学号。 代码实现 // 数学法(高斯求和) class Solution { public:int takeAttendance(vectorint records) {int n records.size() 1;int sum1 ((0 (n - 1)) * n) / 2; // 0~n-1的和int sum2 0; // recoeds中所有元素的和for (auto e : records)sum2 e;return sum1 - sum2;} }; 3、哈希思想  记录records中每个元素出现的次数然后从0开始遍历如果次数是0就返回对应的数字。 代码实现 //哈希映射 class Solution { public:int takeAttendance(vectorint records) {int n records.size()1;unordered_mapint,int hash; for(auto e:records)hash[e]; //记录每个元素出现的次数for(int i0;in;i)if(hash[i]0)return i; //缺失的数字return -1;} }; 4、遍历法 //直接遍历法 class Solution { public:int takeAttendance(vectorint records) {int n records.size();int i0;for(i0;in;i){if(records[i] ! i)return i;}if(i n) //处理数组是[0,1,2]类似这种的情况return i;return -1;} }; 5、二分查找法 通过前面七道题的熏陶这道题大家自己想如何用二分查找。 我在这里给出代码大家可以参考一下 //二分查找 class Solution { public:int takeAttendance(vectorint records) {int left0,rightrecords.size()-1;while(left right){int mid (right-left)/2left;if(records[mid] mid)leftmid1;elserightmid;}if(records[right] right) //处理类似[0,1,2]这种数组的情况return right1;return right;} };