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

C/C++ 二分查找面试算法题

1.二分查找(有序数组)

https://blog.csdn.net/qq_63918780/article/details/122527681

1 #include <stdio.h>2 #include <string.h>3 4 int func(int *a,int j,int x)5 {6     int len = j - 1,i = 0,min;7     while(i<len)8     {9        min = (i+len)/2;
10        if(a[min] > x)
11        {
12           len = min-1;
13        }
14        else if(a[min] < x)
15        {
16           i = min+1;
17        }
18        else
19        {
20           break;
21        }
22     }
23     return min;
24 }
25 
26 int main() 
27 {
28     int j,x,num;
29     int a[] = {1,2,3,4,5,6,7,8,9};
30     printf("输入要查找的数\n");
31     scanf("%d",&x);
32     j = sizeof(a)/sizeof(a[0]);
33     num = func(a,j,x);
34     printf("要查找的数为a[%d]\n",num);
35     
36     return 0;
37 }

2.搜索二维矩阵

https://blog.csdn.net/qq_47406941/article/details/110091759

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。

  • 每行的第一个整数大于前一行的最后一个整数。

1 #include <stdio.h>2 3 #define N 34 #define M 45 6 int main()7 {8     int x,i = 0,j = M -1;9     int a[N][M] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
10     printf("输入一个要查找的数\n");
11     scanf("%d",&x);
12     while(1)
13     {
14         if(x == a[i][j])
15         {
16             printf("找到了\n");
17             break;
18         }
19         else if(x > a[i][j])
20         {
21             if(i < N-1)
22             {
23                 i++;
24             }
25             else
26             {
27                 printf("没找到\n");
28                 break;   
29             }
30         }
31         else
32         {
33             if(j > 0)
34             {
35                 j--;
36             }
37             else
38             {
39                 printf("没找到\n");
40                 break;   
41             }
42         }
43     }
44 
45     return 0;
46 }

3.旋转数组最小数

把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。

例如,数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

https://blog.csdn.net/weixin_43804406/article/details/107956124 

1 #include <stdio.h>2 #include <string.h>3 4 int top(int *a,int len)5 {6    int i,j = a[0];7    for(i = 0;i<len;i++)8    {9        if(j > a[i])
10        {
11            return a[i];
12        }
13    }
14    return -1;
15 }
16 
17 int func(int *a,int len)
18 {
19     int i = 0,j = len - 1,min;
20     while(i<=j)
21     {
22         min = (i+j)/2;
23         
24         if(a[min] == a[i] && a[min] == a[j])
25         {
26             return top(a,len);
27         }
28         
29         if(a[min] > a[i])
30         {
31             i = min+1;
32         }
33         else if(a[min] < a[j])
34         {
35             j = min-1;
36         }
37         else
38         {
39             break;
40         }
41     }
42     return a[min];
43 }
44 
45 int main() 
46 {
47     int a[] = {3,4,5,1,2};
48     int len = sizeof(a)/sizeof(a[0]);
49     int i = func(a,len);
50     printf("%d\n",i);
51     
52     return 0;
53 }

4.搜索旋转排序数组

https://blog.csdn.net/jakercl/article/details/125586657

整数数组 nums 按升序排列,数组中的值互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了旋转,

使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标从 0 开始计数)。

例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 a 和一个整数 x,如果 nums 中存在这个目标值 x ,则返回它的下标,否则返回 -1 。
必须设计一个时间复杂度为 O(logn) 的算法解决此问题

1 #include <stdio.h>2 #include <stdlib.h>3 4 #define N 95 6 int func(int a[])7 {8     int i = 0,j = N-1,min,x;9     printf("输入要查找的数字\n");
10     scanf("%d",&x);
11     while(i<=j)
12     {
13         min = (i+j)/2;
14         if (a[min] == x)
15         {
16             return min;
17         }
18         if (a[i] <= a[min]) //如果左半区间有序
19         {
20             if (a[i] <= x && x < a[min])//目标值在左侧
21             {
22                 j = min - 1;
23             }
24             else//目标值在右侧
25             {
26                 i = min + 1;
27             }
28         }
29         else
30         { //如果右半区间有序
31             if (a[min] < x && x <= a[j])//目标值在右侧
32             {
33                 i = min + 1;
34             }
35             else//目标值在左侧
36             {
37                 j = min - 1;
38             }
39         }
40     }return -1;
41 }
42 
43 int main() 
44 {
45     int a[N] = {5,6,7,8,9,1,2,3,4};
46     int i = func(a);
47     printf("输入的数字的坐标为a[%d]\n",i);
48     
49     return 0;
50 }

5.搜索插入位置

https://blog.csdn.net/m0_61465701/article/details/122599140

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

示例 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
示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:

输入: nums = [1], target = 0
输出: 0

1 #include <iostream>2 #include <vector>3 using namespace std;4 5 class node{6 public:7     int searchinsert(vector<int>& nums,int target){8         int l = 0,r = nums.size() - 1;9         while(l<r){
10             int mid = l + (l+r)/2;
11             if(nums[mid]>=target) r = mid;
12             else l = mid +1;
13         }
14         return r;
15     }
16 };
17 
18 int main() 
19 {
20     node n;
21     vector<int> cur = {1,2,4,6,8,9};
22     cout << n.searchinsert(cur,3) << endl;
23     
24     return 0;
25 }

6.c++实现X的平方根(力扣69题)

1 #include <iostream>2 using namespace std;3 4 class node1{5 public:6      int mysqrt(int x){7         int l = 0,r = x;8         while(l<r){9            int min = l + (r-l)/2 +1;
10            if(min*min <= x) l = min;
11            else r = min -1;
12         }
13         return l;
14      } 
15 };
16 
17 int main()
18 {
19    int x = 6;
20    node1 n;
21    cout << n.mysqrt(x) << endl;
22     
23    return 0;
24 }

相关文章:

C/C++ 二分查找面试算法题

1.二分查找&#xff08;有序数组&#xff09; https://blog.csdn.net/qq_63918780/article/details/122527681 1 #include <stdio.h>2 #include <string.h>3 4 int func(int *a,int j,int x)5 {6 int len j - 1,i 0,min;7 while(i<len)8 {9 …...

Linux基本指令(上)——“Linux”

各位CSDN的uu们好呀&#xff0c;今天&#xff0c;小雅兰的内容是Linux啦&#xff01;&#xff01;&#xff01;主要是Linux的一些基本指令和Linux相关的基本概念&#xff08;系统层面&#xff09;&#xff0c;下面&#xff0c;让我们进入Linux的世界吧&#xff01;&#xff01;…...

XSS详解

XSS一些学习记录 XXS短标签、属性、事件、方法短标签属性事件函数弹窗函数一些对于绕过有用的函数一些函数使用payload收集 浏览器编码问题XML实体编码URL编码JS编码混合编码 一些绕过方法利用constructor原型污染链构造弹框空格绕过圆括号过滤绕过其他的一些绕过 参考 XXS短标…...

【图论】判环问题

&#xff08;未更新完、做到相关题再更新相关部分 文章目录 无向图判断有无环并输出环上点 无向图判断有无环并输出环上点 例题&#xff1a;H. Mad City 利用变种拓扑排序&#xff0c;先把度为1的点存入队中&#xff0c;每次取出队头&#xff0c;遍历邻接点&#xff0c;再将该…...

将3D MAX设计模型导入NX1988

将3D MAX设计模型导入NX1988 概述导入流程导出喜欢的模型对模型进行修改模型贴图 概述 一般家装设计都不会用NX之类的产品设计软件&#xff0c;也没有通用的文件格式可以互相转换&#xff0c;本文的目的是将从网上下载的一些设计较好的3D MAX模型导入到NX软件中借用&#xff0…...

操作系统原理实验三:页面调度算法程序

实验三&#xff1a;页面调度算法程序 课程名称&#xff1a;操作系统原理 项目名称&#xff1a;页面调度算法程序 实验&#xff08;实训&#xff09;类型&#xff1a;验证性实验 实验&#xff08;实训&#xff09;课时&#xff1a;2 [目的和要求] 目的&#xff1a; 加深对请…...

QT实现tcp服务器客户端

服务器.cpp #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);// 此时&#xff0c;服务器已经成功进入监听状态…...

tcp拥塞控制原理

18.3 拥塞控制 我们在向对端发送数据时&#xff0c;并不是一股脑子任意发送&#xff0c;因为TCP建立连接后&#xff0c;就是建立了一根管道&#xff0c;这跟管道上&#xff0c;实际上有很多的工作设备&#xff0c;比如路由器和交换机等等&#xff0c;他们都会对接收到的TCP包进…...

【C++设计模式之简单工厂模式】分析及示例

简介 简单工厂模式是一种常见的设计模式&#xff0c;用于创建多种相似对象的实例&#xff0c;属于创建型。 它通过一个工厂类来解耦客户端代码和对象的创建过程&#xff0c;使得客户端无需直接和具体的产品类交互&#xff0c;而只需要通过工厂类获取所需的产品实例即可。 原理…...

云原生定义整理

云原生定义整理 Pivotal 是云原生应用的提出者&#xff0c;并推出了 Pivotal Cloud Foundry 云原生应用平台和 Spring 开源 Java 开发框架&#xff0c;成为云原生应用架构中先驱者和探路者。 Pivotal最初的定义 Pivotal公司的Matt Stine在2015年写了一本叫做<<迁移到云…...

华硕X555YI, Win11下无法调节屏幕亮度

翻出一个旧电脑华硕X555YI&#xff0c;装Win11玩&#xff0c;已经估计到会有一些问题。 果然&#xff0c;装完之后&#xff0c;发现屏幕无法调节亮度。试了网上的一些方法&#xff0c;比如修改注册表等&#xff0c;无效。 估计是显卡比较老&#xff0c;哪里没兼容。然后用驱动…...

踩坑 | vue动态绑定img标签src属性的一系列报错

文章目录 踩坑 | vue项目运行后使用require()图片也不显示问题描述vue中动态设置img的src不生效问题的原因require is not defined 解决办法1&#xff1a;src属性直接传入地址解决办法2 踩坑 | vue项目运行后使用require()图片也不显示 问题描述 在网上查阅之后&#xff0c;发…...

强化学习环境 - robogym - 学习 - 1

强化学习环境 - robogym - 学习 - 1 项目地址 https://github.com/openai/robogym 为什么选择 robogym 自己的项目需要做一些机械臂 table-top 级的多任务操作 robogym 基于 mujoco 搭建&#xff0c;构建了一个仿真机械臂桌面物体操作&#xff08;pick-place、stack、rearr…...

如果在 Mac 上的 Safari 浏览器中无法打开网站

使用网络管理员提供的信息更改代理设置。个人建议DNS解析&#xff0c;设置多个例如114.114.114.114 8.8.8.8 8.8.4.4 如果打不开网站&#xff0c;请尝试这些建议。 在 Mac 上的 Safari 浏览器 App 中&#xff0c;检查页面无法打开时出现的信息。 这可能会建议解决问题的…...

力扣练习——链表在线OJ

目录 提示&#xff1a; 一、移除链表元素 题目&#xff1a; 解答&#xff1a; 二、反转链表 题目&#xff1a; 解答&#xff1a; 三、找到链表的中间结点 题目&#xff1a; 解答&#xff1a; 四、合并两个有序链表&#xff08;经典&#xff09; 题目&#xff1a; 解…...

四、互联网技术——局域网拓扑结构

文章目录 一、局域网拓扑结构二、虚拟局域网VLAN三、交换机VLAN划分四、VLAN的作用五、交换机的端口类型六、经典三层网络架构七、例题:局域网带宽利用分析八、网络安全基础九、恶意软件十、防火墙与入侵检测技术 一、局域网拓扑结构 局域网的主要特征由网络的拓扑结构、所采用…...

Spring Webflux DispatcherHandler源码整理

DispatcherHandler的构造(以RequestMappingHandlerMapping为例) WebFluxAutoConfiguration中EnableWebFluxConfiguration继承WebFluxConfigurationSupportBean public DispatcherHandler webHandler() {return new DispatcherHandler(); }DispatcherHandler#setApplicationCon…...

【Netty】ByteToMessageDecoder源码解析

目录 1.协议说明 2.类的实现 3.Decoder工作流程 4.源码解析 4.1 ByteToMessageDecoder#channelRead 4.2 累加器Cumulator 4.3 解码过程 4.4 Decoder实现举例 5. 如何开发自己的Decoder 1.协议说明 Netty框架是基于Java NIO框架&#xff0c;性能彪悍&#xff0c;支持的协…...

DevEco Studio设置Nodejs提示路径只能包含英文、数字、下划线等

安装DevEco Studio 3.1.1 Release 设置Nodejs路径使用nodejs默认安装路径 &#xff08;C:\Program Files\nodejs&#xff09; 提示只能包含英文、数字、下划线等 , 不想在安装nodejs请往下看 nodejs默认路径报错 修改配置文件 1、退出DevEco Studio 2、打开配置文件 cmd控制台…...

大模型 Decoder 的生成策略

本文将介绍以下内容&#xff1a; IntroductionGreedy Searchbeam searchSamplingTop-K SamplingTop-p (nucleus) sampling总结 一、Introduction 1、简介 近年来&#xff0c;由于在数百万个网页数据上训练的大型基于 Transformer 的语言模型的兴起&#xff0c;开放式语言生…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...