【二分算法】

17. 二分查找(easy)

算法流程:

算法代码:

int search(int* nums, int numsSize, int target)
{
	// 初始化 left 与 right 指针
	int left = 0, right = numsSize - 1;
	// 由于两个指针相交时,当前元素还未判断,因此需要取等号
	while (left <= right)
	{
		// 先找到区间的中间元素
		int mid = left + (right - left) / 2;
		// 分三种情况讨论
		if (nums[mid] == target) return mid;
		else if (nums[mid] > target) right = mid - 1;
		else left = mid + 1;
	}
	// 如果程序⾛到这⾥,说明没有找到⽬标值,返回 -1
	return -1;
}

总结朴素二分模板

18. 在排序数组中查找元素的第⼀个和最后⼀个位置(medium)

算法思路:

寻找左边界思路:

寻找右边界思路:

⼆分查找算法总结:

模板记忆技巧:

C++ 算法代码:

class Solution
{
public:
	vector<int> searchRange(vector<int>& nums, int target)
	{
		// 处理边界情况
		if (nums.size() == 0) return { -1, -1 };

		int begin = 0;
		// 1. ⼆分左端点
		int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) left = mid + 1;
			else right = mid;
		}

		// 判断是否有结果
		if (nums[left] != target) return { -1, -1 };
		else begin = left; // 标记⼀下左端点

		// 2. ⼆分右端点
		left = begin, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left + 1) / 2;
			if (nums[mid] <= target) left = mid;
			else    right = mid - 1;
		}
		return { begin, right };
	}
};

19. 搜索插⼊位置(easy)

解法(⼆分查找算法):

C++ 算法代码:

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)
                left = mid + 1;
            else
                right = mid;
        }
        if(nums[left] < target) return right + 1;
        return left;
    }
};

20. x 的平⽅根(easy)

解法⼀:(暴⼒查找)

C++ 算法代码:

class Solution{
public:
 int mySqrt(int x) {
	 // 由于两个较⼤的数相乘可能会超过 int 最⼤范围
	 // 因此⽤ long long
	 long long i = 0;
	 for (i = 0; i <= x; i++)
	 {
		 // 如果两个数相乘正好等于 x,直接返回 i
		 if (i * i == x) return i;
		 // 如果第⼀次出现两个数相乘⼤于 x,说明结果是前⼀个数
		 if (i * i > x) return i - 1;
		 }
	 // 为了处理oj题需要控制所有路径都有返回值
	 return -1;
	 }
};

解法⼆(⼆分查找算法):

C++ 算法代码:

class Solution
{
public:
	int mySqrt(int x)
	{
		if (x < 1) return 0; // 处理边界情况
		int left = 1, right = x;
		while (left < right)
		{
			long long mid = left + (right - left + 1) / 2; // 防溢出
			if (mid * mid <= x) left = mid;
			else right = mid - 1;
		}
		return left;
	}
};

21. 山峰数组的峰顶(easy)

解法⼀(暴⼒查找):

算法代码:

class Solution {
public:
	int peakIndexInMountainArray(vector<int>& 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(vector<int>& arr) {
        int left = 1;
        int right = arr.size() - 2;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1])
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

22. 寻找峰值(medium)

解法⼆(⼆分查找算法):

C++ 算法代码:

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] > nums[mid + 1]) right = mid;
			else left = mid + 1;
		}
		return left;
    }
};

23. 搜索旋转排序数组中的最⼩值(medium)

解法(⼆分查找):

C++ 算法代码:

class Solution
{
public:
	int findMin(vector<int>& nums)
	{
		int left = 0, right = nums.size() - 1;
		int x = nums[right]; // 标记⼀下最后⼀个位置的值
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] > x) left = mid + 1;
			else right = mid;
		}
		return nums[left];
	}
};

24. 0〜n-1 中缺失的数字(easy)

解法(⼆分查找算法):

C++ 算法代码:

class Solution {
public:
	int missingNumber(vector<int>&nums)
	{
		int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] == mid) left = mid + 1;
			else right = mid;
		}
		return left == nums[left] ? left + 1 : left;
	}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/538139.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024最新仿默往IM即时通讯系统源码(PC+WEB+IOS+Android)客户端

简介: 2024最新仿默往IM即时通讯系统源码(PC+WEB+IOS+Android)客户端 系统功能配置灵活、海量并发、稳定可靠、数据安全,2小时快速部署、数据安全、单聊群聊、系统通知等通信功能,支持App、PC、Web等多端快速接入。 群功能:设置群二维码,群公告,昵称,头像,群共享文件…

零基础教程|四步学会自制宣传手册

在当今竞争激烈的市场中&#xff0c;一本精美而引人注目的宣传手册是吸引客户和推广产品的重要工具。但对于许多人来说&#xff0c;制作宣传手册似乎是一项艰巨的任务&#xff0c;特别是对于零基础的人来说。然而&#xff0c;通过以下四个简单的步骤&#xff0c;您也可以轻松学…

解决redis乱码问题

目录 1.问题 2.查看redis序列化机制 3.设置redis的序列化器 1.问题 在使用redis最为缓存时&#xff0c;发现key乱码问题 这是由于redis的序列化机制导致的 2.查看redis序列化机制 3.设置redis的序列化器 Configuration Data public class RedisConfig {/*** redis序列化*…

应急响应-战前反制主机HIDSElkeid蜜罐系统HFish

知识点 战前-反制-平台部署其他更多项目&#xff1a; https://github.com/birdhan/SecurityProduct HIDS&#xff1a;主机入侵检测系统&#xff0c;通常会有一个服务器承担服务端角色&#xff0c;其他主机就是客户端角色&#xff0c;客户端加入到服务端的检测范围里&#xff…

【漏洞复现】通天星CMSV6车载视频监控平台MobileAction文件读取漏洞

Nx01 产品简介 通天星车载视频监控平台软件拥有多种语言版本&#xff0c;应用于公交车车载视频监控、校车车载视频监控、大巴车车载视频监控、物流车载监控、油品运输车载监控等公共交通上。 Nx02 漏洞描述 通天星CMSV6车载视频监控平台MobileAction文件读取漏洞&#xff0c;攻…

C语言---顺序表(二)

文章目录 前言1.准备工作2.代码的实现2.1.顺序表的创建、销毁和打印2.2.顺序表的扩容、头插\删、尾插\删2.2.1.扩容2.2.2.尾插2.2.3.头插2.2.3.尾删2.2.4.头删 2.3.指定位置之前插入/删除数据/查找数据2.3.1.指定位置之前插入数据2.3.2.指定位置之前删除数据2.3.3.查找特定数据…

ChatGPT基础(二) ChatGPT的使用和调优

文章目录 ChatGPT的特性采用关键词进行提问给ChatGPT指定身份提升问答质量的策略1.表述方式上的优化2.用"继续"输出长内容3.营造场景4.由浅入深&#xff0c;提升问题质量5.预设回答框架和风格 ChatGPT的特性 1.能够联系上下文进行回答 ChatGPT回答问题是有上下文的&…

Samba实现windows和Linux共享文件,环境搭建

​ 搭建步骤 安装sambad sudo apt-get install samba samba-common 创建samba用户和密码 此处使用 Linux 账号和密码作为 samba 的账号和密码。Linux 账号为 shelmean shelmeanmachine:[~] $ sudo smbpasswd -a shelmean New SMB password: Retype new SMB password: Add…

MongoDB副本集部署(windows)

环境准备 本教程演示mongodb4.4 副本集部署&#xff08;一主两从&#xff0c;伪分布式&#xff09; 节点配置主节点localhost:27017从节点1localhost:27018从节点2localhost:27019 每一个节点&#xff08;实例&#xff09;都创建对应的数据文件&#xff08;data&#xff09;…

记一次空迭代器导致的崩溃分析

一. 崩溃代码&#xff1a; class EasySelect::Impl { public:Impl() default;std::vector<int> waitForReadable ();void addFd (int fd);void removeFd (int fd);void stopWait ();private:std::vector<int> m_fds;std::mutex m_fdsMutex;std::mutex m_pipeMute…

MySQL数据导出导出的三种办法(13/16)

数据导入导出 基本概述 目前常用的有3中数据导入与导出方法&#xff1a; 使用mysqldump工具&#xff1a; 优点&#xff1a; 简单易用&#xff0c;只需一条命令即可完成数据导出。可以导出表结构和数据&#xff0c;方便完整备份。支持过滤条件&#xff0c;可以选择导出部分数据…

python知识点汇总(十一)

python知识点总结 1、当Python退出时&#xff0c;是否会清除所有分配的内存&#xff1f;2、Python的优势有哪些&#xff1f;3、什么是元组的解封装4、Python中如何动态获取和设置对象的属性&#xff1f;5、创建删除操作系统上的文件6、主动抛出异常7、help() 函数和 dir() 函数…

数据结构-----枚举、泛型进阶(通配符?)

文章目录 枚举1 背景及定义2 使用3 枚举优点缺点4 枚举和反射4.1 枚举是否可以通过反射&#xff0c;拿到实例对象呢&#xff1f; 5 总结 泛型进阶1 通配符 ?1.1 通配符解决什么问题1.2 通配符上界1.3 通配符下界 枚举 1 背景及定义 枚举是在JDK1.5以后引入的。主要用途是&am…

加速杂交水稻走向世界 政协委员建议在湖南设立一“协会”一“中心”

中新网北京3月8日电 (刘曼)针对中国杂交水稻海外“飘香”的现象&#xff0c;全国政协委员、湖南省政协副主席、民盟湖南省委会主委何寄华建议&#xff0c;在湖南建立杂交水稻国际合作交流协会、设立杂交水稻国际科技合作技术转移中心&#xff0c;支持杂交水稻走向世界。 全国政…

计算机基础知识-第7章-程序的本质(2)——算法与数据结构概论

一、算法数据结构程序 提出这一公式并以此作为其一本专著的书名的瑞士计算机科学家尼克劳斯沃思&#xff08;Niklaus Wirth&#xff09;由于发明了多种影响深远的程序设计语言&#xff0c;并提出结构化程序设计这一革命性概念而获得了1984年的图灵奖。他是至今惟一获此殊荣的瑞…

Python爬取链家数据

技术&#xff1a;requests、BeautifulSoup、SQLite 解析页面&#xff0c;存数据到SQLite数据库&#xff0c;到时候你用navicat导出成csv什么的就行 1、确定城市 以天津为例&#xff0c;网页是https://tj.lianjia.com/ershoufang/rs/ 把上面这些地区名字复制 2、爬取数据内容…

三天做完pandas数据分析50题第一天

三天做完pandas数据分析50题第一天 第1题 将python的list转换为Series第2题 将字典转换为Series第3题 将Series转换成python的list第4题 使用numpy创建series。第5题 如何为Series添加新的元素&#xff1f;第6题 使用字典创建DataFrame第7题 给DataFrame设置索引列第8题 生成一…

每日一题---OJ题: 合并两个有序链表

嗨!小伙伴们,好久不见啦! 今天我们来看看一道很有意思的一道题---合并两个有序链表 嗯,题目看上去好像不难,我们一起画图分析分析吧! 上图中,list1有3个结点,分别为1,2,3 ; list2中有3个结点,分别为1,3,4, 题目要求我们要将这两个链表合并到一起,并且是升序,最后将链表返回。 …

光威神策PRO PCIe 5.0 SSD发布,国产固态硬盘进入10G俱乐部

全球半导体供应链的紧张局势和闪存资源的短缺让许多行业都面临着不小的压力 &#xff0c; 连带的也让消费者难以获取物美价廉的闪存产品 。但是&#xff0c;总有一些企业能够逆流而上&#xff0c; 像是 光威科技这家国产存储品牌&#xff0c; 最近就给国内消费者 带来了一个惊喜…