当前位置: 首页 > 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;开放式语言生…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...