当前位置: 首页 > news >正文

刷题日志【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.lryc.cn/news/502317.html

相关文章:

  • 如何制作自己的字体文件.ttf
  • gradle在IDEA 中无法使用的启动守护线程的问题
  • Spring Boot 配置多数据源并手动配置事务
  • YashanDB 23.2 YAC 共享集群部署和使用自带YMP迁移工具进行数据迁移,效果很city
  • 【数学】矩阵的逆与伪逆 EEGLAB
  • 狐猬编程 C++ L3 第7课 字符串入门 元音字母
  • APP UI自动化测试的思路小结
  • 2412d,d的7月会议
  • ANOMALY BERT 解读
  • 定时/延时任务-Netty时间轮源码分析
  • React的一些主要优点是?
  • RabbitMQ 基本使用方法详解
  • [leetcode100] 101. 对称二叉树
  • Vue.createApp的对象参数
  • 短信验证码burp姿势
  • ubuntu WPS安装
  • 中粮凤凰里共有产权看房记
  • 学习笔记068——Hibernate框架介绍以及使用方法
  • Maven 安装配置(详细教程)
  • 虚幻开发中的MYPROJECTFORPLUG_API
  • 顺序栈及其实现过程
  • 内圆弧转子泵绘制工具开发
  • linux网络编程 | c | 多进程并发服务器实现
  • Vins_Fusion_gpu中source setup.bash
  • 怎么理解大模型推理时的Top_P参数?
  • hive+hadoop架构数仓使用问题记录
  • 前端的 Python 入门指南(三):数据类型对比 - 彻底的一切皆对象实现和包装对象异同
  • Axios结合Typescript 二次封装完整详细场景使用案例
  • 基于Kubesphere实现微服务的CI/CD——部署微服务项目(三)
  • 【使用webrtc-streamer解析rtsp视频流】