力扣-14天算法入门
第1天 二分查找
第2天 双指针
第3天 双指针
第4天 双指针
第5天 双指针
第6天 滑动窗口
第7天 广度优先搜索 / 深度优先搜索
第8天 广度优先搜索 / 深度优先搜索
第9天 广度优先搜索 / 深度优先搜索
第10天 递归 / 回溯
第11天 递归 / 回溯
第12天 动态规划
第13天 位运算
第14天 位运算
前言
本系列文章是我的力扣刷题记录,采用c++进行编写
一、二分查找-查找一个数
难度(简单)
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
分析：
根据题意这里是让我们找到 一个数组中的一个数，找到就返回该数在数组中的下标，数组中没有这个数就返回-1。
这是一个非常普遍的一个二分查找问题，我们只需要利用二分法对其逐步逼近就能得出。
具体步骤为：
我们先找出数组的左右区间，根据区间大小求出中间数的下标，然后只要中间数和目标数相等就返回该数下标，倘若中间数大于目标值，右边界左移，小于就另左边界右移。
具体代码如下：
class Solution {
public:
int search(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)
{
return mid;
}
else if(nums[mid] < target)
{
left = mid + 1;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
}
return -1;
}
};
二、二分查找-第一个错误的版本
难度(简单)
题目：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2
输入：n = 1, bad = 1
输出：1
分析：
这一题和第一题大同小异，但这里要注意的是，当前版本是正确的话，后面的都是正确的。
我们对中间版本进行判断如果中间版本正确就令right = mid，否则就另left = mid+1。
具体代码如下：
class Solution {
public:
int firstBadVersion(int n)
{
int left = 1;
int right = n;
while(left<right){
int mid = left + (right - left) / 2;
if (isBadVersion(mid))
{
right = mid;
}
else
{
left = mid+1;
}
}
return left;
}
};
三、二分查找-搜索插入位置
难度(简单)
题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
具体代码如下：
class Solution {
public:
int searchInsert(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)
{
return mid;
}
else if(nums[mid]<target)
{
left = mid+1;
}
else if(nums[mid]>target)
{
right = mid - 1;
}
}
return left;
}
};
总结
期待大家和我交流，留言或者私信，一起学习，一起进步！
|