当前位置: 首页 > 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…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...