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

终极指南:五分钟让Win11老游戏重获联机能力的完整解决方案

终极指南&#xff1a;五分钟让Win11老游戏重获联机能力的完整解决方案 【免费下载链接】ipxwrapper 项目地址: https://gitcode.com/gh_mirrors/ip/ipxwrapper 还在为Win11系统下无法联机玩《星际争霸》《魔兽争霸2》《暗黑破坏神》等经典游戏而烦恼吗&#xff1f;今天…...

QT6 + CMake + QML开发:你的图片和QML文件加载不出来?可能是.qrc没配对

QT6 CMake QML开发&#xff1a;资源加载失败的终极排查指南 当你花了几个小时精心设计了QML界面&#xff0c;却在运行时看到一片空白或"找不到文件"的错误提示时&#xff0c;那种挫败感每个QT开发者都深有体会。特别是在QT6和CMake的现代开发环境中&#xff0c;资源…...

EcomGPT-7B镜像免配置实操:Docker Compose一键编排(含Redis缓存服务)

EcomGPT-7B镜像免配置实操&#xff1a;Docker Compose一键编排&#xff08;含Redis缓存服务&#xff09; 你是不是也遇到过这样的烦恼&#xff1f;想试试最新的AI电商大模型&#xff0c;结果光是环境配置就折腾了大半天。各种Python版本、PyTorch版本、依赖库冲突&#xff0c;…...

ASLR:现代操作系统中的内存安全守护者

1. ASLR&#xff1a;现代操作系统的内存安全基石 想象一下你家的门锁每天都会自动更换位置——这就是ASLR&#xff08;地址空间布局随机化&#xff09;对计算机程序做的事。作为现代操作系统最基本的安全机制之一&#xff0c;ASLR通过打乱程序在内存中的"居住地址"&…...

LeetCode 3418:机器人获取最大金币数(动态规划+状态压缩)

LeetCode 3418&#xff1a;机器人获取最大金币数&#xff08;动态规划状态压缩&#xff09; LeetCode 3418. 机器人可以获得的最大金币数【动态规划状态压缩】 问题描述 给定一个 m x n 的网格&#xff0c;机器人从左上角 (0, 0) 出发前往右下角 (m-1, n-1)&#xff0c;仅能向右…...

Planetscale:免费云数据库的快速入门与实战指南

1. Planetscale是什么&#xff1f;为什么开发者都在用&#xff1f; 第一次听说Planetscale时&#xff0c;我也和大多数开发者一样好奇&#xff1a;这个号称"开发者友好"的云数据库到底有什么特别&#xff1f;用了半年后终于明白&#xff0c;它就像是数据库界的GitHub…...

PyTorch 2.8多场景实操:科研训练+工程推理+内容创作的统一技术底座

PyTorch 2.8多场景实操&#xff1a;科研训练工程推理内容创作的统一技术底座 1. 为什么选择PyTorch 2.8作为统一技术底座 PyTorch 2.8作为当前最主流的深度学习框架之一&#xff0c;已经成为学术界和工业界的首选工具。这个基于RTX 4090D 24GB显卡深度优化的镜像&#xff0c;…...

DLSS Swapper终极指南:5分钟掌握游戏性能优化新技能

DLSS Swapper终极指南&#xff1a;5分钟掌握游戏性能优化新技能 【免费下载链接】dlss-swapper 项目地址: https://gitcode.com/GitHub_Trending/dl/dlss-swapper 你是否曾因游戏帧率不足而烦恼&#xff1f;是否想尝试新版本DLSS却担心兼容性问题&#xff1f;DLSS Swap…...

基于WPS云服务架构的Vue文档预览组件技术实现与性能优化

基于WPS云服务架构的Vue文档预览组件技术实现与性能优化 【免费下载链接】wps-view-vue wps在线编辑、预览前端vue项目&#xff0c;基于es6 项目地址: https://gitcode.com/gh_mirrors/wp/wps-view-vue 在微前端架构和云原生应用日益普及的技术背景下&#xff0c;企业级…...

突破QQ音乐格式壁垒:QMCDecode全方位解密方案与跨场景应用指南

突破QQ音乐格式壁垒&#xff1a;QMCDecode全方位解密方案与跨场景应用指南 【免费下载链接】QMCDecode QQ音乐QMC格式转换为普通格式(qmcflac转flac&#xff0c;qmc0,qmc3转mp3, mflac,mflac0等转flac)&#xff0c;仅支持macOS&#xff0c;可自动识别到QQ音乐下载目录&#xff…...