刷题日志【4】

目录

1、猜数字大小


1、猜数字大小

题意有点抽象,我大概讲一下,就是在1——n里面会有一个目标数,我们通过猜数字的方式逼近这个数字,直到解出这个数,之前我们是用二分法求最快达到求解的问题,这道题多了每次猜错都要付钱,不要求最快达到,只要求,不论题目的目标数是1——n里的哪一个,你口袋的钱在面对1——n的目标数时,都有解。

再简单点说,当n=5时,即总数字(1 2 3 4 5),不论目标数(x)是哪一个,你的钱都够逼出目标数,注意:这里不是指你的钱够面对目标数(x)的最差情况(如先猜:1 2 3······x,虽然这不一定是代价最高的,但估计不是最优的猜数字策略),而是钱够应对目标数为x的最佳情况(下面有举例解释)

1——10的最优策略如上,可以看到即使目标数是叶子节点(2,3 ,6 ,8 ,10),沿着各个支路进行代价累计发现最大的也只是(7->9->10)这一路,计算得到16(叶子节点是已经逼出来的答案,不算代价),所以一旦目标数不是叶子节点,那代价只会更小,所以以7为头节点的上图的策略是面对【1 ,10】的最佳策略 

这里其实就有一个隐藏关系:对应的一个【】一定是有一个对应的的最优策略,即 【i j】的区间左右相同时,就会是一样的策略,对应的代价也是相同,这里就是我们可以记忆化的地方

1、无记忆化 

class Solution {public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int i,int j){//边界条件:头节点为1->【1,0】->无意义return 0【1 0】理论情况不可能出现,不用代价//头节点:2->【1 1】return 0-->直接猜到了,所以【1 1】不用耗费代价
if(i>=j){return 0;}
int ret=INT_MAX;
for(int head=i;head<=j;head++)
{
int x=dfs(i,head-1);
int y=dfs(head+1,j);
//取两者较大值,满足最大值即该策略全部数字都可以达到
int cost=max(x,y)+head;
//遍历每一种不同的头节点,每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
ret=min(ret,cost);
}return ret;}
};

2、记忆化 

就比上面的多了memo【】【】对每一种下标的return进行记录

class Solution {int memo[201][201];public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int i,int j){//边界条件:头节点为1->【1,0】->无意义return 0【1 0】理论情况不可能出现,不用代价//头节点:2->【1 1】return 0-->直接猜到了,所以【1 1】不用耗费代价
if(i>=j){return 0;}
if(memo[i][j]!=0){return memo[i][j];}
int ret=INT_MAX;
for(int head=i;head<=j;head++)
{
int x=dfs(i,head-1);
int y=dfs(head+1,j);
//取两者较大值,满足最大值即该策略全部数字都可以达到
int cost=max(x,y)+head;
//遍历每一种不同的头节点,每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
ret=min(ret,cost);
}
memo[i][j]=ret;//记录下来,方便其他的遍历到【i j】区间
return ret;}
};

2、矩阵中最长递增路径 

 

 

 

 

 发现相同的下标对应的最长路径一定是一样的:只要matrix【2】的最长路径已知,matrix【3】规划的路径里,只要有matrix【2】,那么matrix【3】经过matrix【2】的最长路径一定是matrix【2】+1(加上他本身)

所以在这里可以记忆化

 

class Solution {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
//防止走回头录
bool check[201][201];
//备忘录
int memo[201][201];int m,n;public:int longestIncreasingPath(vector<vector<int>>& matrix) {m=matrix.size();n=matrix[0].size();int maxlength=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){check[i][j]=true;//dfs返回以【i ,j】为头节点的最长路径maxlength=max(maxlength,dfs(matrix,i,j));  check[i][j]=false;}}return maxlength;}int dfs(vector<vector<int>>& matrix,int i,int j) {//!=0即意味着这个位置之前记录过
if(memo[i][j]!=0)
{return memo[i][j];
}
int tmp=0;
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&matrix[x][y]>matrix[i][j])
{check[x][y]=true;
tmp=max(tmp,dfs(matrix,x,y));
check[x][y]=false;}}
memo[i][j]=1+tmp;
return memo[i][j];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/488680.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【蓝桥杯最新板】蓝桥杯嵌入式液晶上实现电子时钟

这几年蓝桥杯比赛比较适合学生技能学习&#xff0c;考虑板子功能&#xff0c;提出完成的任务。 要求在液晶完成如下图效果&#xff1a; 主要是实现液晶显示时钟和数字时钟&#xff0c;具体样式可以依据实际情况微调。 实现过程&#xff1a; 1.需要画圆&#xff08;外圆、内圆…

Python知识分享第25天-快速排序算法

快速排序算法 快速排序&#xff08;QuickSort&#xff09;是一种基于分治法的高效排序算法。它通过选择一个“基准”元素&#xff0c;将数组分成两个子数组&#xff0c;其中一个子数组的所有元素都比基准小&#xff0c;另一个子数组的所有元素都比基准大&#xff0c;然后递归地…

Hive3.X——异常处理Could not create ServerSocket on address 0.0.0.0/0.0.0.0:10000

Hive3.X——异常处理Could not create ServerSocket on address 0.0.0.0/0.0.0.0:10000 01 前言 大数据系列&#xff0c;学到了Hive&#xff0c;搭建环境的时候&#xff0c;因为使用的是本机WSL2&#xff08;别问为啥不用VMware&#xff0c;问就是条件有限&#xff0c;而且WS…

[Java] 使用 VSCode 来开发 Java

目录 前言Java 环境怎么看自己是否已经配置完成&#xff1f;安装 JDK安装 Maven 环境修改 Maven 依赖源 完善 VS Code配置插件配置 Maven配置 Maven Settings配置 Maven 可执行文件地址 前言 由于使用 VSCode 编码已经成为习惯&#xff0c;并且它确实相对其他的 IDE 较为轻量化…

悬赏任务源码(悬赏发布web+APP+小程序)开发附源码

悬赏任务源码是指一个软件或网站的源代码&#xff0c;用于实现悬赏任务的功能。悬赏任务是指发布方提供一定的奖励&#xff0c;希望能够找到解决特定问题或完成特定任务的人。悬赏任务源码通常包括任务发布、任务接受、任务完成和奖励发放等功能的实现。搭建悬赏任务源码是一个…

可视化建模以及UML期末复习----做题篇

一、单项选择题。&#xff08;20小题&#xff0c;每小题2分,共40分&#xff09; 1、UML图不包括&#xff08; &#xff09; A、用例图 B、状态机图 C、流程图 D、类图 E、通信图 答案&#xff1a;C、流程图 UML中不包括传统意义上的流程图&#xff0c;流程图通常是指B…

SpringBoot中使用MyBatis-Plus详细介绍

目录 一、MyBatis-Plus的使用步骤 1.引入MybatisPlus的起步依赖 2.定义Mapper&#xff08;也叫dao&#xff09;层的接口 3.MyBatis-Plus中常用注解 4. 使用MyBatis-Plus时要做如下配置 5.条件构造器 Wrapper 一、MyBatis-Plus的使用步骤 1.引入MybatisPlus的起步依赖 My…

操作系统(4)操作系统的结构

一、无序结构&#xff08;整体结构或模块组合结构&#xff09; 1.特点&#xff1a; 以大型表格和队列为中心&#xff0c;操作系统的各部分程序围绕着这些表格进行。操作系统由许多标准的、可兼容的基本单位&#xff08;称为模块&#xff09;构成&#xff0c;模块之间通过规定的…

Windows桌面系统管理0:总目录

目 录 Windows桌面系统管理1计算机硬件组成及组装-CSDN博客文章浏览阅读353次&#xff0c;点赞14次&#xff0c;收藏3次。计算机硬件组成及组装https://blog.csdn.net/2401_86296728/article/details/144431553?fromshareblogdetail&sharetypeblogdetail&sharerId14…

在CentOS中安装和卸载mysql

在CentOS7中安装和卸载mysql 卸载mysql1、查看是否安装过mysql2、查看mysql服务状态3、关闭mysql服务4、卸载mysql相关的rpm程序5、删除mysql相关的文件6、删除mysql的配置文件my.cnf 安装mysql1、下载mysql相关的rpm程序2、检查/tmp临时目录权限3、安装mysql前的依赖检查3、安…

印闪网络:阿里云数据库MongoDB版助力金融科技出海企业降本增效

客户背景 上海印闪网络科技有限公司&#xff0c;于2017年1月成立&#xff0c;投资方包括红杉资本等多家国际知名风投公司。公司业务聚焦东南亚普惠金融&#xff0c;常年稳居行业头部。创始团队来自腾讯&#xff0c;中国团队主要由运营、风控及产研人员组成&#xff0c;核心成员…

网络基础 - TCP/IP 五层模型

文章目录 一、OSI 参考模型中各个分层的作用1、应用层2、表示层3、会话层4、传输层5、网络层6、数据链路层7、物理层 一、OSI 参考模型中各个分层的作用 1、应用层 2、表示层 负责设备固有数据格式和网络标准数据格式间的转换 3、会话层 4、传输层 负责连接的建立和断开&…

【数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】

目录&#x1f60b; 任务描述 测试说明 我的通关代码: 测试结果&#xff1a; 任务描述 本关任务&#xff1a;实现希尔排序算法。 测试说明 平台会对你编写的代码进行测试&#xff1a; 测试输入示例&#xff1a; 10 9 8 7 6 5 4 3 2 1 0 (说明&#xff1a;第一行是元素个数&a…

网络编程 | TCP套接字通信及编程实现经验教程

1、TCP基础铺垫 TCP/IP协议簇中包含了如TCP、UDP、IP、ICMP、ARP、HTTP等通信协议。TCP协议是TCP/IP协议簇中最为常见且重要的通信方式之一&#xff0c;它为互联网上的数据传输提供了可靠性和连接管理。 TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议…

【最新】北大数字普惠金融指数数据集-省市县(2011-2023年)

一、数据介绍 数据名称&#xff1a;第六期北大数字普惠金融指数-省市县 数据年份&#xff1a;2011-2023年 数据范围&#xff1a;全国31个省、337个地级以上城市以及2800个县 数据说明&#xff1a;编制方法请参阅《经济学&#xff08;季刊&#xff09;》中的《测度中国数字普…

GNSS误差源及差分定位

GNSS误差源&#xff1a; &#xff08;一&#xff09;卫星星历误差 由星历信息所得出的卫星位置坐标与实际位置坐标的偏差就是星历误差。星历信息是由 GPS 地面部分测量计算后传入空间部分的。由于卫星在运动中要受到各种摄动力的作用, 而地面部分又很难精确测量这些作用力,…

频域采样引起Gibbs效应——频域采样FIR滤波器设计的主要问题(答作者问)

还是这个图&#xff0c;我不明白廖老师为什么纠结这几个图不放过。Rafael Gonzalez的《数字图像处理》概念不清楚的地方&#xff0c;我就直接放过了&#xff0c;我为什么要和基础差的人纠结。 现在的问题是图(c )到图(d)为什么会产生Gibbs效应。这与补零&#xff08;哪怕是异想…

软考中级-软件设计师通过心路经验分享

执念&#xff0c;第四次终于通过了 没买书&#xff0c;下班后每天2小时&#xff0c;四个2个月终于过了 学习经验&#xff1a; 1.下班后学习真的靠毅力&#xff0c;和上学的时候考证不是一个状态&#xff0c;大家要及时调整&#xff0c;否则过程很痛苦 2.失败三次的经验&#xf…

Cesium中实现仿ArcGIS三维的动态图层加载方式

Cesium 加载 ArcGIS 动态图层的方式 如果你在 Cesium 中加载过 ArcGIS 的动态图层&#xff0c;你会发现&#xff0c;Cesium 对于动态图层仍然采用类似切片图层的逻辑进行加载。也就是每个固定的瓦片 export 一张图片。 这样会造成一些问题&#xff1a; 请求量大&#xff0c;…

zerotier实现内网穿透(访问内网服务器)

moo 内网穿透工具 实用工具&#xff1a;zerotier 目录 内网穿透工具 Windows下zerotier安装 ubuntu系统下的zerotier安装 使用moon加速 Windows下zerotier安装 有了网络之后&#xff0c;会给你一个网络id&#xff0c;这个网络id是非常重要的&#xff0c;其它设备要加入…