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

数据结构----算法--分治,快速幂

数据结构----算法–分治,快速幂

一.分治

1.分治的概念

分治法:分而治之

将一个问题拆解成若干个解决方式完全相同的问题

满足分治的四个条件

1.问题难度随着数据规模缩小而降低

2.问题可拆分

3.子问题间相互独立

4.子问题的解可合并

2.二分查找(折半搜索) BinaryChop

前提:有序

时间复杂度O(log2的n次方)

1.循环实现二分查找

//循环
int BinaryChop1(int a[], int begin, int end ,int find) {if (a == nullptr || begin > end) return -1;while (begin<= end) {int mid = begin+(end- begin)/2 ;if (a[mid] == find) {cout << "找到了,返回在数组中的下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}}return -1;
}

2.递归实现二分查找

//递归
int BinaryChop2(int a[], int begin, int end, int find) {if (a == nullptr || begin > end) return -1;int mid = begin+(end- begin)/2;if (a[mid] == find) {cout << "找到了,返回数组下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}return BinaryChop2(a, begin, end, find);}

二.快速幂

求一个数的幂次方

例如2的50次方

//简单写法,这种写法求一个数的幂次方速度慢
int a=2;
for(int i=0;i<50;i++){a*=a;
}
//快速幂写法
int x=2
int n=50;
int ans=1;
while(n){temp=n&1;if(temp){ans*=x;}x*=x;n=n>>1;
}
printf("%d",ans);

快速幂就是将幂数二进制化

然后和1位与,如果得1 最终要输出的结果就乘以当前位的数,否则不乘

之后将幂数左移一位,当前位的数自乘

重复进行操作直到幂数为0结束

看一道具体的题(网址https://leetcode.cn/problems/powx-n/)

题目:实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,x的n次方 )。

代码如下

//这里的代码是c++语言下的
class Solution {
public:double myPow(double x, int n) {int Bool=0;int Bool2=0;int t=x;if(n==0&&x!=0){return 1;}if(x==0){return 0;}double ans=1;int temp=0;if(n<0){if(n==-2147483648){n=2147483647;Bool2=1;}else{n=abs(n);}Bool=1;}while(n){temp=n&1;if(temp){ans*=x;}x*=x;n=n>>1;}if(Bool2){ans*=t;}if(Bool){ans=1.0/ans;}return ans;}
};

相关文章:

数据结构----算法--分治,快速幂

数据结构----算法–分治,快速幂 一.分治 1.分治的概念 分治法&#xff1a;分而治之 将一个问题拆解成若干个解决方式完全相同的问题 满足分治的四个条件 1.问题难度随着数据规模缩小而降低 2.问题可拆分 3.子问题间相互独立 4.子问题的解可合并 2.二分查找(折半搜索)…...

【ChatGPT 指令大全】怎么使用ChatGPT写履历和通过面试

目录 怎么使用ChatGPT写履历 寻求履历的反馈 为履历加上量化数据 把经历修精简 为不同公司客制化撰写履历 怎么使用ChatGPT通过面试 汇整面试题目 给予回馈 提供追问的问题 用 STAR 原则回答面试问题 感谢面试官的 email 总结 在职场竞争激烈的今天&#xff0c;写一…...

微服务:从header中获取用户存入当前线程

1、从网关gateway工程filter中解析token携带的当前用户信息并添加到header中 //获取token携带的idObject userid claimsBody.get("id");//在header中添加新的信息ServerHttpRequest serverHttpRequest request.mutate().headers(httpHeaders -> {httpHeaders.ad…...

C语言系列之原码、反码和补码

一.欢迎来到我的酒馆 讨论c语言中&#xff0c;原码、反码、补码。 目录 一.欢迎来到我的酒馆二.原码 二.原码 2.1在计算机中&#xff0c;所有数据都是以二进制存储的&#xff0c;但不是直接存储二进制数&#xff0c;而是存储二进制的补码。原码很好理解&#xff0c;就是对应的…...

程序框架——UI管理模块

UI基类BasePanel 负责帮助我们通过代码快速的找到所有的子控件&#xff0c;方便我们在子类中处理逻辑&#xff0c;节约找控件的工作量。 public class BasePanel : MonoBehaviour {//通过里式转换原则 来存储所有的控件private Dictionary<string, List<UIBehaviour>…...

MySQL 慢查询探究分析

目录 背景&#xff1a; mysql 整体结构&#xff1a; SQL查询语句执行过程是怎样的&#xff1a; 知道了mysql的整体架构&#xff0c;那么一条查询语句是怎么被执行的呢&#xff1a; 什么是索引&#xff1a; 建立索引越多越好吗&#xff1a;   如何发现慢查询&#xff1…...

wpf 项目中使用 Prism + MaterialDesign

1.通过nuget安装MaterialDesign 2.通过nuget安装Prism 3.修改App.xmal <prism:PrismApplication x:Class"VisionMeasureGlue.App"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/…...

【Spring Boot】Thymeleaf模板引擎 — Thymeleaf页面布局

Thymeleaf页面布局 熟悉Thymeleaf的语法和表达式后&#xff0c;后面开发起来会更加得心应手。接下来好好研究一下Thymeleaf如何实现完整的Web系统页面布局。 1.引入代码片段 在模板中经常希望包含来自其他模板页面的内容&#xff0c;如页脚、页眉、菜单等。为了做到这一点&a…...

整理mongodb文档:删

个人博客 整理mongodb文档:删 求关注&#xff0c;哪儿不足&#xff0c;求大佬们指出&#xff0c;哪儿写的不够通俗易懂跟清晰&#xff0c;也求指出 文章概叙 本文主要是介绍了删除数据的几个方法&#xff0c;主要还是在介绍deleteMany、deleteOne以及remove&#xff0c;对于…...

篇二十三:设计模式的综合实例:构建完整项目

篇二十三&#xff1a;"设计模式的综合实例&#xff1a;构建完整项目" 开始本篇文章之前先推荐一个好用的学习工具&#xff0c;AIRIght&#xff0c;借助于AI助手工具&#xff0c;学习事半功倍。欢迎访问&#xff1a;http://airight.fun/。 另外有2本不错的关于设计模…...

FFmpeg常见命令行(三):FFmpeg转码

前言 在Android音视频开发中&#xff0c;网上知识点过于零碎&#xff0c;自学起来难度非常大&#xff0c;不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个&#xff0c; 对应的要学习的内容是&#xff1a;如何使…...

合宙Air724UG LuatOS-Air script lib API--scanCode

Table of Contents scanCode scanCode.request(cbFnc, timeout) scanCode 模块功能&#xff1a;扫码. 支持二维码、条形码扫描 scanCode.request(cbFnc, timeout) 设置扫码请求 参数 名称 传入值类型 释义 cbFnc function 扫码返回或者超时未返回的回调函数&#xff0c;回调…...

2023年新手如何学剪辑视频 想学视频剪辑如何入门

随着短视频、vlog等媒体形式的兴起&#xff0c;视频剪辑已经成为了热门技能。甚至有人说&#xff0c;不会修图可以&#xff0c;但不能不会剪视频。实际上&#xff0c;随着各种智能软件的发展&#xff0c;视频剪辑已经变得越来越简单。接下来&#xff0c;一起来看看新手如何学剪…...

C++的auto究竟是何方神圣

C的auto究竟是何方神圣 前言&#x1f64c;auto&#xff08;C 11&#xff09; 的使用细则auto是什么&#xff1f; auto声明的变量是在什么时期被编译器推导出来呢&#xff1f;为什么使用auto进行定义变量时&#xff0c;必须进行初始化&#xff1f; auto 的使用场景auto与指针和引…...

网络安全【黑客】面试题汇总

前言 一眨眼2023年已经过去一大半&#xff0c;不知道大家有没有找到心仪的工作。作为一个安全老鸟&#xff0c;工作这么多年&#xff0c;面试过很多人也出过很多面试题目&#xff0c;也在网上收集了各类关于渗透面试题目&#xff0c;里面有我对一些问题的见解&#xff0c;希望…...

docker菜谱大全

记录docker常用软件安装&#xff0c;感谢小马哥和杨师傅的投稿。&#x1f60e;&#x1f60e;&#x1f60e; 相关文档&#xff1a; DockerHub&#xff1a;https://hub.docker.com/Linux手册&#xff1a;https://linuxcool.com/Docker文档&#xff1a;https://docs.docker.com/Do…...

git: git checkout命令

git checkout 命令在Git中有不同的用法和功能&#xff0c;具体取决于您在命令后面提供的参数。以下是一些常见的用法&#xff1a; 1. 切换分支&#xff1a;您可以使用 git checkout <branch> 切换到指定的分支。例如&#xff0c;要切换到名为 "feature-branch"…...

以游戏编程的角度看待模拟时间的算法题——以PAT甲级1026 Table Tennis为例

对于需要模拟时间的算法题&#xff0c;可以将开始时间作为游戏的开始&#xff08;如Unity的Start或UE的BeginPlay&#xff09;&#xff0c;每一秒的模拟作为游戏的画面更新&#xff08;如Unity的Update或UE的Tick&#xff09;&#xff0c;结束时间可作为游戏的结束&#xff08;…...

SNAT与DNAT原理

SNAT和DNAT &#xff08;源地址转换和目标地址转换&#xff09; SNAT&#xff1a;源地址转换。内网到外网转换的是源地址。 DNAT&#xff1a;目标地址转换&#xff1a;外网到内网转换的是目的地址 &#xff08;把内部服务器的ip地址转换成一个所有人都可以访问的地址&#xff0…...

04-2_Qt 5.9 C++开发指南_SpinBox使用

文章目录 1. SpinBox简介2. SpinBox使用2.1 可视化UI设计2.2 widget.h2.3 widget.cpp 1. SpinBox简介 QSpinBox 用于整数的显示和输入&#xff0c;一般显示十进制数&#xff0c;也可以显示二进制、十六进制的数&#xff0c;而且可以在显示框中增加前缀或后缀。 QDoubleSpinBox…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

C++中vector类型的介绍和使用

文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...