数据结构----算法--分治,快速幂
数据结构----算法–分治,快速幂
一.分治
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.分治的概念 分治法:分而治之 将一个问题拆解成若干个解决方式完全相同的问题 满足分治的四个条件 1.问题难度随着数据规模缩小而降低 2.问题可拆分 3.子问题间相互独立 4.子问题的解可合并 2.二分查找(折半搜索)…...
【ChatGPT 指令大全】怎么使用ChatGPT写履历和通过面试
目录 怎么使用ChatGPT写履历 寻求履历的反馈 为履历加上量化数据 把经历修精简 为不同公司客制化撰写履历 怎么使用ChatGPT通过面试 汇整面试题目 给予回馈 提供追问的问题 用 STAR 原则回答面试问题 感谢面试官的 email 总结 在职场竞争激烈的今天,写一…...
微服务:从header中获取用户存入当前线程
1、从网关gateway工程filter中解析token携带的当前用户信息并添加到header中 //获取token携带的idObject userid claimsBody.get("id");//在header中添加新的信息ServerHttpRequest serverHttpRequest request.mutate().headers(httpHeaders -> {httpHeaders.ad…...
C语言系列之原码、反码和补码
一.欢迎来到我的酒馆 讨论c语言中,原码、反码、补码。 目录 一.欢迎来到我的酒馆二.原码 二.原码 2.1在计算机中,所有数据都是以二进制存储的,但不是直接存储二进制数,而是存储二进制的补码。原码很好理解,就是对应的…...
程序框架——UI管理模块
UI基类BasePanel 负责帮助我们通过代码快速的找到所有的子控件,方便我们在子类中处理逻辑,节约找控件的工作量。 public class BasePanel : MonoBehaviour {//通过里式转换原则 来存储所有的控件private Dictionary<string, List<UIBehaviour>…...
MySQL 慢查询探究分析
目录 背景: mysql 整体结构: SQL查询语句执行过程是怎样的: 知道了mysql的整体架构,那么一条查询语句是怎么被执行的呢: 什么是索引: 建立索引越多越好吗: 如何发现慢查询࿱…...
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的语法和表达式后,后面开发起来会更加得心应手。接下来好好研究一下Thymeleaf如何实现完整的Web系统页面布局。 1.引入代码片段 在模板中经常希望包含来自其他模板页面的内容,如页脚、页眉、菜单等。为了做到这一点&a…...
整理mongodb文档:删
个人博客 整理mongodb文档:删 求关注,哪儿不足,求大佬们指出,哪儿写的不够通俗易懂跟清晰,也求指出 文章概叙 本文主要是介绍了删除数据的几个方法,主要还是在介绍deleteMany、deleteOne以及remove,对于…...
篇二十三:设计模式的综合实例:构建完整项目
篇二十三:"设计模式的综合实例:构建完整项目" 开始本篇文章之前先推荐一个好用的学习工具,AIRIght,借助于AI助手工具,学习事半功倍。欢迎访问:http://airight.fun/。 另外有2本不错的关于设计模…...
FFmpeg常见命令行(三):FFmpeg转码
前言 在Android音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个, 对应的要学习的内容是:如何使…...
合宙Air724UG LuatOS-Air script lib API--scanCode
Table of Contents scanCode scanCode.request(cbFnc, timeout) scanCode 模块功能:扫码. 支持二维码、条形码扫描 scanCode.request(cbFnc, timeout) 设置扫码请求 参数 名称 传入值类型 释义 cbFnc function 扫码返回或者超时未返回的回调函数,回调…...
2023年新手如何学剪辑视频 想学视频剪辑如何入门
随着短视频、vlog等媒体形式的兴起,视频剪辑已经成为了热门技能。甚至有人说,不会修图可以,但不能不会剪视频。实际上,随着各种智能软件的发展,视频剪辑已经变得越来越简单。接下来,一起来看看新手如何学剪…...
C++的auto究竟是何方神圣
C的auto究竟是何方神圣 前言🙌auto(C 11) 的使用细则auto是什么? auto声明的变量是在什么时期被编译器推导出来呢?为什么使用auto进行定义变量时,必须进行初始化? auto 的使用场景auto与指针和引…...
网络安全【黑客】面试题汇总
前言 一眨眼2023年已经过去一大半,不知道大家有没有找到心仪的工作。作为一个安全老鸟,工作这么多年,面试过很多人也出过很多面试题目,也在网上收集了各类关于渗透面试题目,里面有我对一些问题的见解,希望…...
docker菜谱大全
记录docker常用软件安装,感谢小马哥和杨师傅的投稿。😎😎😎 相关文档: DockerHub:https://hub.docker.com/Linux手册:https://linuxcool.com/Docker文档:https://docs.docker.com/Do…...
git: git checkout命令
git checkout 命令在Git中有不同的用法和功能,具体取决于您在命令后面提供的参数。以下是一些常见的用法: 1. 切换分支:您可以使用 git checkout <branch> 切换到指定的分支。例如,要切换到名为 "feature-branch"…...
以游戏编程的角度看待模拟时间的算法题——以PAT甲级1026 Table Tennis为例
对于需要模拟时间的算法题,可以将开始时间作为游戏的开始(如Unity的Start或UE的BeginPlay),每一秒的模拟作为游戏的画面更新(如Unity的Update或UE的Tick),结束时间可作为游戏的结束(…...
SNAT与DNAT原理
SNAT和DNAT (源地址转换和目标地址转换) SNAT:源地址转换。内网到外网转换的是源地址。 DNAT:目标地址转换:外网到内网转换的是目的地址 (把内部服务器的ip地址转换成一个所有人都可以访问的地址࿰…...
04-2_Qt 5.9 C++开发指南_SpinBox使用
文章目录 1. SpinBox简介2. SpinBox使用2.1 可视化UI设计2.2 widget.h2.3 widget.cpp 1. SpinBox简介 QSpinBox 用于整数的显示和输入,一般显示十进制数,也可以显示二进制、十六进制的数,而且可以在显示框中增加前缀或后缀。 QDoubleSpinBox…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
