算法分析与设计编程题 递归与分治策略
棋盘覆盖
题目描述


解题代码
// para: 棋盘,行偏移,列偏移,特殊行,特殊列
void dividedCovering(vector<vector<int>>& chessBoard, int dr, int dc, int sr, int sc, int size) {if (size == 1) return;size /= 2; // 划分为四部分if (sr < dr + size && sc < dc + size) { // 特殊点位于左上部分divideCovering(chessBoard, dr, dc, sr, sc, size);}else {int nr = dr + size - 1, nc = dc + size - 1; // 新覆盖点chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr, dc, nr, nc, size);}if (sr < dr + size && sc >= dc + size) { // 特殊点位于右上部分divideCovering(chessBoard, dr, dc + size, sr, sc, size);}else {int nr = dr + size - 1, nc = dc + size;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr, dc + size, nr, nc, size);}if (sr >= dr + size && sc < dc + size) { // 特殊点位于左下部分divideCovering(chessBoard, dr + size, dc, sr, sc, size);}else {int nr = dr + size, nc = dc + size - 1;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr + size, dc, nr, nc, size);}if (sr >= dr + size && sc >= dc + size) { // 特殊点位于右下部分divideCovering(chessBoard, dr + size, dc + size, sr, sc, size);}else {int nr = dr + size, nc = dc + size;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr + size, dc + size, nr, nc, size);}
}void chessBoardCovering(vector<vector<int>>& chessBoard, int sr, int sc) {int n = chessBoard.size();divideCovering(chessBoard, 0, 0, sr, sc, n);
}
线性时间选择
题目描述

解题代码
int partition(vector<int>& nums, int left, int right) {int randIdx = rand() % (right - left + 1) + left; // 选取随机pivotswap(randIdx, nums[left]);int pivot = nums[left];while (left < right) {while (left < right && nums[right] >= pivot) --right;nums[left] = nums[right];while (left < right && nums[left] <= pivot) ++left;nums[right] = nums[left];}nums[left] = pivot;return left;
}int dividedQuickSelect(vector<int>& nums, int left, int right, int k) {if (left >= right) return nums[left];int p = partition(nums, left, right); // 根据基准进行划分if (p == k) return nums[p]; // 划分基准正好为第k小的数else if (p > k) return divideQuickSelect(nums, left, p - 1, k); // 基准大于第k小else return divideQuickSelect(nums, p + 1, right, k); // 基准小于第k小
}int quickSelect(vector<int>& nums, int k) {srand((unsigned)time(nullptr)); // 设定随机种子return divideQuickSelect(nums, 0, nums.size() - 1, k - 1);
}
相关文章:
算法分析与设计编程题 递归与分治策略
棋盘覆盖 题目描述 解题代码 // para: 棋盘,行偏移,列偏移,特殊行,特殊列 void dividedCovering(vector<vector<int>>& chessBoard, int dr, int dc, int sr, int sc, int size) {if (size 1) return;size / 2…...
Java的XWPFTemplate工具类导出word.docx的使用
依赖 <!-- word导出 --><dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.7.3</version></dependency><!-- 上面需要的依赖--><dependency><groupId>org.ap…...
Science adv | 转录因子SPIC连接胚胎干细胞中的细胞代谢与表观调控
代谢是生化反应网络的结果,这些反应吸收营养物质并对其进行处理,以满足细胞的需求,包括能量产生和生物合成。反应的中间体被用作各种表观基因组修饰酶的底物和辅助因子,因此代谢与表观遗传密切相关。代谢结合表观遗传涉及疾病&…...
机器学习实战-系列教程7:SVM分类实战2线性SVM(鸢尾花数据集/软间隔/线性SVM/非线性SVM/scikit-learn框架)项目实战、代码解读
🌈🌈🌈机器学习 实战系列 总目录 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 SVM分类实战1之简单SVM分类 SVM分类实战2线性SVM SVM分类实战3非线性SVM 3、不同软间隔C值 3.1 数据标准化的影响 如图左边是没…...
DOM渲染与优化 - CSS、JS、DOM解析和渲染阻塞问题
文章目录 DOM渲染面试题DOM的渲染过程DOM渲染的时机与渲染进程的概述浏览器的渲染流程1. 解析HTML生成DOM树:遇到<img>标签加载图片2. 解析CSS生成CSSOM(CSS Object Model): 遇见背景图片链接不加载3. 将DOM树和CSSOM树合并生成渲染树:加载可视节点…...
基于小程序的理发店预约系统
一、项目背景及简介 现在很多的地方都在使用计算机开发的各种管理系统来提高工作的效率,给人们带来很多的方便。计算机技术从很大的程度上解放了人们的双手,并扩大了人们的活动范围,是人们足不出户就可以通过电脑进行各种事情的管理。信息系…...
MD5 算法流程
先通过下面的命令对 md5算法有个感性的认识: $ md5sum /tmp/1.txt 1dc792fcaf345a07b10248a387cc2718 /tmp/1.txt$ md5sum // 从键盘输入,ctrl-d 结束输入 hello, world! 910c8bc73110b0cd1bc5d2bcae782511 -从上面可以看到,一个文件或一…...
TCP/IP协议详解
TCP/IP(Transmission Control Protocol/Internet Protocol,传输控制协议/互联网协议)是互联网的基本协议,也是国际互联网络的基础。 TCP/IP 不是指一个协议,也不是 TCP 和 IP 这两个协议的合称,而是一个协…...
SSM SpringBoot vue快递柜管理系统
SSM SpringBoot vue快递柜管理系统 系统功能 登录 注册 个人中心 快递员管理 用户信息管理 用户寄件管理 配送信息管理 寄存信息管理 开发环境和技术 开发语言:Java 使用框架: SSM(Spring SpringMVC Mybaits)或SpringBoot 前端: vue 数据库:Mys…...
期权交易保证金比例一般是多少?
期权交易是一种非常受欢迎的投资方式之一,它为期权市场带来了更为多样化和灵活化的交易形式。而其中的期权卖方保证金比例是期权交易中的一个重要指标,直接关系到投资者的风险与收益,下文介绍期权交易保证金比例一般是多少?本文来…...
029:vue项目,勾选后今天不再弹窗提示
第029个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 (1)提供vue2的一些基本操作:安装、引用,模板使…...
Unet语义分割-语义分割与实例分割概述-001
文章目录 前言1、图像分割和图像识别1.语义分割2.实例分割 2、分割任务中的目标函数定义3.IOU 前言 大纲目录 1、图像分割和图像识别 下面是图像识别和图像分割的区别,图像识别就是识别出来,画个框,右边的是图像分割。 1.语义分割 两张图把…...
Linux常用命令字典篇
Linux命令 1. 翻页查看文件 less [-N] 文件名:可以向后翻页,也可以向前翻页,-N表示显示行号 more 文件名:仅可以向后翻页 2. 端口占用信息查看 netstat -tunlp | grep 端口号:查看端口号对应的信息 lsof i: 端口号…...
__declspec(novtable) 在C++
__declspec(novtable) 在C中接口中广泛应用. 不容易看到它是因为在很多地方它都被定义成为了宏. 比如说ATL活动模板库中的ATL_NO_VTABLE, 其实就是__declspec(novtable). __declspec(novtable) 就是让类不要有虚函数表以及对虚函数表的初始化代码, 这样可以节省运行时间和空间.…...
ChatGPT充值,银行卡被拒绝
目录 前言步骤1. 魔法地址选择2. 选择手机号码(归属地)3. 勾选,服从协议4. 填写信息5. 完善账单地址6. 订阅成功 前言 大家好,今天我在订阅ChatGPT4时,遭遇了银行卡被拒绝的尴尬境地。这里有个技巧,我来给…...
算法通过村第七关-树(递归/二叉树遍历)白银笔记|递归实战
文章目录 前言1. 深入理解前中后序遍历从小到大递推分情况讨论,明确结束条件组合出完整的方法:从大到小 画图推演 总结 前言 提示:没有客观公正的记忆这回事,所有的记忆都是偏见,都是为自己的存活而重组过的经验。--国…...
抖音小程序开发教学系列(6)- 抖音小程序高级功能
第六章:抖音小程序高级功能 6.1 抖音小程序的支付功能6.1.1 接入流程6.1.2 注意事项 6.2 抖音小程序的地理位置和地图功能6.2.1 接入流程6.2.2 使用方法 6.3 抖音小程序的实时音视频功能6.3.1 接入流程6.3.2 使用方法 6.4 抖音小程序的小游戏开发6.4.1 基本流程6.4.…...
SpringBoot运行原理
目录 SpringBootApplication ComponentScan SpringBootConfiguration EnableAutoConfiguration 结论 SpringbootApplication(主入口) SpringBootApplication public class SpringbootConfigApplication {public static void main(String[] args) {…...
为什么Proteus串口无法正常显示
我以前就可以正常显示,但是最近一段时间,发现串口无法正常显示,试了很多办法都不行, 然后今天干好有点时间就刷了个机,然后居然就好了, 这就说明:Proteus不正常可能是病毒破坏了某个文件导致异…...
Furion api npm web vue混合开发
Furion api npm web vue混合开发 Furion-api项目获取swagger.json文件复制json制作ts包删除非.ts文件上传到npm获取npm包引用 Furion-api项目获取swagger.json文件 使用所有接口合并的配置文件 复制json制作ts包 https://editor.swagger.io 得到 typescript-axios-clien…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
