当前位置: 首页 > 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];}
};

相关文章:

刷题日志【4】

目录 1、猜数字大小 1、猜数字大小 题意有点抽象&#xff0c;我大概讲一下&#xff0c;就是在1——n里面会有一个目标数&#xff0c;我们通过猜数字的方式逼近这个数字&#xff0c;直到解出这个数&#xff0c;之前我们是用二分法求最快达到求解的问题&#xff0c;这道题多了每…...

IDEA对windows下的docker里面的Weblogic 进行远程调试(漏洞环境搭建)部署Vulhub漏洞环境

参考书籍&#xff1a;《Java代码审计》入门篇 人民邮电出版社 话不多说&#xff0c;上教程&#xff01;&#xff01;&#xff01; 环境很重要&#xff01;&#xff01;&#xff01;&#xff01; 其他的环境不保证对 本机环境&#xff1a;java jdk 8 下载 选择 下载就行 然后 …...

【深度学习】Java DL4J基于多层感知机(MLP)构建公共交通优化模型

🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/?__c=1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编程,高并发设计,Springboot和微服务,熟悉Linux,ESXI虚拟化以及云原生Docker和K8s,热衷于探…...

医学分割数据集肾结石分割数据集labelme格式359张1类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;359 标注数量(json文件个数)&#xff1a;359 标注类别数&#xff1a;1 标注类别名称:["kidney stone"] 每个类别标注的框数&…...

Ansible自动化运维(五) 运维实战

Ansible自动化运维这部分我将会分为五个部分来为大家讲解 &#xff08;一&#xff09;介绍、无密钥登录、安装部署、设置主机清单 &#xff08;二&#xff09;Ansible 中的 ad-hoc 模式 模块详解&#xff08;15&#xff09;个 &#xff08;三&#xff09;Playbook 模式详解 …...

ReactPress最佳实践—搭建导航网站实战

Github项目地址&#xff1a;https://github.com/fecommunity/easy-blog 欢迎Star。 近期&#xff0c;阮一峰在科技爱好者周刊第 325 期中推荐了一款开源工具——ReactPress&#xff0c;ReactPress一个基于 Next.js 的博客和 CMS 系统&#xff0c;可查看 demo站点。&#xff08;…...

Dual-Write Problem 双写问题(微服务)

原文链接https://www.confluent.io/blog/dual-write-problem/ 双写问题发生于当两个外部系统必须以原子的方式更新时。 问题 说有人到银行存了一笔钱&#xff0c;触发 DepositFunds 命令&#xff0c;DepositFunds 命令被发送到Account microservice。 Account microservice需…...

文件转曲,限制PDF文件编辑的最佳方案!

随着数字化进程的推进&#xff0c;PDF文件凭借其多样化的功能和优越的兼容性已经被广泛使用&#xff0c;成为了现代文档交流和存储的重要工具&#xff0c;满足了不同用户和行业的需求。 虽然PDF格式文件的功能很多&#xff0c;常见的比如阅读、编辑、加密、转换、还可用于印刷…...

call,apply,bind 深入

显示绑定 我们通常会碰见丢失绑定的情况&#xff0c;例如系统函数setTimeOut function foo() { console.log( this.a ); } var obj { a: 2, foo: foo }; var a "oops, global"; // a是全局对象的属性 setTimeout( obj.foo, 100 ); // "oops, globalca…...

监测预警智能分析中心建设项目方案

随着科技的不断进步&#xff0c;地理信息与遥感技术在国家治理、环境保护、灾害预警等领域发挥着越来越重要的作用。监测预警智能分析中心的建设&#xff0c;旨在通过集成先进的遥感技术、地理信息系统&#xff08;GIS&#xff09;、大数据分析和人工智能&#xff08;AI&#x…...

redis stream轻量级消息队列

redis 5.0 之后新推出了stream数据结构&#xff0c;可以实现一个轻量级的消息队列&#xff0c;下面通过自定义注解和springboot使用一下redis stream 1.自定义注解 Target(ElementType.METHOD) Retention(value RetentionPolicy.RUNTIME) public interface MsgStreamListener …...

ORACLE SQL思路: 多行数据有相同字段就合并成一条数据 分页展示

数据 分数表&#xff1a; 学号&#xff0c;科目名&#xff08;A,B,C&#xff09;&#xff0c;分数 需求 分页列表展示&#xff0c; 如果一个学号的科目有相同的分数&#xff0c; 合并成一条数据&#xff0c;用 拼接 科目名 ORACLE SQL 实现 SELECT Z.*, SUBSTR(DECODE(f…...

UE5制作倒计时功能

设置画布和文本 文本绑定 格式化时间 转到事件图表&#xff0c;计算时间&#xff0c;时间结束后面的事件可以按自己需求写 进入关卡蓝图&#xff0c;添加倒计时UI...

若依-帝可得app后端

视频地址 https://www.bilibili.com/video/BV1pf421B71v?t=510.1 APP后端技术栈 架构解析 验证码功能 开发环境使用改的是固定的验证码 12345正式环境使用的是 阿里云的短信方案@Override public void sendSms(String mobile) {// String code = RandomUtil.randomNumbers(5);…...

Vulnstack红日安全内网域渗透靶场2实战攻略

一&#xff1a;环境搭建 新增的网卡VMnet2&#xff0c;ip调成10段。 PC配置如下&#xff1a; DC在该环境中充当是域控。DC配置如下 &#xff1a; WEB配置&#xff1a;需要两块网卡&#xff0c;相当于网关服务器。 作者把外网网段都写成了192.168.111.1/24&#xff0c;我们可以…...

苹果电脑可以安装windows操作系统吗?Mac OS X/OS X/macOS傻傻分不清?macOS系统的Java支持?什么是macOS的五大API法王?

苹果电脑可以安装windows操作系统吗? 先抛开虚拟机安装&#xff0c;苹果电脑可以安装Windows操作系统。苹果公司提供了一个名为Boot Camp的软件&#xff0c;它允许用户在Mac电脑上安装Windows操作系统。通过Boot Camp&#xff0c;用户可以在启动电脑时选择是要进入macOS还是Wi…...

benchANT (Time Series: Devops) 榜单数据解读

近日&#xff0c;国际权威数据库性能测试榜单 benchANT 更新了 Time Series: Devops&#xff08;时序数据库&#xff09;场景排名&#xff0c;KaiwuDB 数据库在 xsmall 和 small 两类规格下的时序数据写入吞吐、查询吞吐、查询延迟、成本效益等多项指标刷新榜单原有数据纪录 &a…...

React useEffect使用

useEffect依赖 是reac hook的函数 useEffect作用&#xff1a;不是由事件引起&#xff0c;而是由渲染本身引起的操作&#xff0c;比如发起请求&#xff0c;更改DOM 不发生任何的用户事件&#xff0c;组件渲染完毕之后就需要和服务器要数据&#xff0c;整个过程中属于‘只需要…...

Python随机抽取Excel数据并在处理后整合为一个文件

本文介绍基于Python语言&#xff0c;针对一个文件夹下大量的Excel表格文件&#xff0c;基于其中每一个文件&#xff0c;随机从其中选取一部分数据&#xff0c;并将全部文件中随机获取的数据合并为一个新的Excel表格文件的方法。 首先&#xff0c;我们来明确一下本文的具体需求。…...

Unix 和 Windows 的有趣比较

Unix 和 Windows NT 比较 来源于这两本书&#xff0c;把两本书对照来读&#xff0c;发现很多有意思的地方&#xff1a; 《Unix 传奇》 https://book.douban.com/subject/35292726/ 《观止 微软创建NT和未来的夺命狂奔 》 Showstopper!: The Breakneck Race to Create Windows…...

解决Android Studio Unexpected tokens (use ; to separate expressions on the same line)

[TOC](Unexpected tokens (use ; to separate expressions on the same line)) 问题描述&#xff1a;Unexpected tokens (use ; to separate expressions on the same line) 原因&#xff1a;Android Studio 更新到最新的版本之后&#xff0c;gradle工程目录结构发生改变 问…...

【Office】Office实现shift+鼠标滚轮左右滑动

Office实现shift鼠标滚轮左右滑动 windows系统安装office之后发现&#xff0c;使用shift鼠标滚轮不能够实现左右滑动&#xff0c;我记得以前的office好像是可以的&#xff0c;然后在网上找了一下&#xff0c;找到了一个插件可以实现这个功能 OfficeScroll插件 下载地址&…...

1.C语言 typedef的使用方法

描述作用 1.typedef主要通途给类型起一个别名&#xff0c;比如给int类型取个中文名字 zhengxingint。 2.typedef可以简化struct关键字 3.typedef可以区分数据类型 4.typedef提高代码的平台可移植性。 举例 取别名 #include "stdio.h" #include "string.h&q…...

人工智能原理实验四:智能算法与机器学习

一、实验目的 本实验课程是计算机、智能、物联网等专业学生的一门专业课程&#xff0c;通过实验&#xff0c;帮助学生更好地掌握人工智能相关概念、技术、原理、应用等&#xff1b;通过实验提高学生编写实验报告、总结实验结果的能力&#xff1b;使学生对智能程序、智能算法等…...

redis 架构详解

Redis架构详解可以从以下几个方面进行阐述&#xff1a; 一、部署架构 Redis有多种部署架构&#xff0c;适用于不同的应用场景和需求&#xff0c;主要包括以下几种&#xff1a; 单机模式&#xff08;Standalone Mode&#xff09; 特点&#xff1a;部署简单&#xff0c;配置方便…...

shell脚本自动发布Java应用

单体项目或定制化小应用&#xff0c;频繁发布会有些麻烦&#xff0c;用脚本实现git提交完代码自动发布&#xff0c;并完成jar包备份 1.前提条件&#xff1a;linux安装了JDK、Maven、Git 安装参考链接&#xff1a; jdk安装 https://blog.csdn.net/weixin_44904239/article/de…...

微信小程序调用腾讯地图-并解读API文档 JavaScript SDK和 WebService API

搜索&#xff1a;腾讯位置服务 找到API文档&#xff1a; 入门中第一步&#xff1a;申请开发者密钥key 前往控制台&#xff1a; 创建应用并获取key: 设置key的时候&#xff0c;还需要小程序的APPID。所以要前往微信公众平台中获取小程序的APPID&#xff1a; 限制要求&#xff1a…...

go build command

文章目录 1.简介2.格式3.选项4.示例5.小结参考文献 1.简介 go build 是 Go 语言工具链中的一个命令&#xff0c;它用于编译 Go 源代码并生成可执行文件。 2.格式 go build [-o output] [build flags] [packages]可选的 -o 选项强制 build 将生成的可执行文件或对象写入指定的…...

前端面试题目 (Node.JS-Express框架)[二]

在 Express 中如何使用 Passport.js 进行身份认证? Passport.js 是一个 Node.js 的身份验证中间件&#xff0c;它可以很容易地与 Express 集成。下面是一个简单的示例&#xff0c;展示了如何使用 Passport.js 进行基本的身份认证。 安装依赖 npm install express passport …...

云和恩墨 zCloud 与华为云 GaussDB 完成兼容性互认证

近日&#xff0c;云和恩墨&#xff08;北京&#xff09;信息技术有限公司&#xff08;以下简称&#xff1a;云和恩墨&#xff09;的多元数据库智能管理平台 zCloud 与华为云计算技术有限公司&#xff08;以下简称&#xff1a;华为云&#xff09;的 GaussDB 数据库完成了兼容性互…...

go-zero(十三)使用MapReduce并发

go zero 使用MapReduce并发 一、MapReduce 介绍 MapReduce 是一种用于并行计算的编程模型&#xff0c;特别适合在大规模数据处理场景中简化逻辑代码。 官方文档&#xff1a; https://go-zero.dev/docs/components/mr 1. MapReduce 的核心概念 在 MapReduce 中&#xff0c;主…...

【鸿蒙实战开发】数据的下拉刷新与上拉加载

本章介绍 本章主要介绍 ArkUI 开发中最常用的场景下拉刷新, 上拉加载&#xff0c;在本章中介绍的内容在实际开发过程当中会高频的使用,所以同学们要牢记本章的内容。下面就让我们开始今天的讲解吧&#xff01; List 组件 在 ArkUI 中List容器组件也可以实现数据滚动的效果&a…...

SQL中的替换函数replace() 使用

这条 SQL 语句的作用是将 tool_tool 表中所有 link 字段包含 https://www.xxspvip.cn 的记录中的 https://www.xxspvip.cn 替换为 http://192.168.1.1。具体解释如下&#xff1a; SQL 语句分解 UPDATE tool_toolSET link REPLACE(link, https://www.xxspvip.cn, http://192.…...

算法(三)——贪心算法

文章目录 定义基本原理基本思路优缺点优点缺点 经典案例及解析找零问题问题描述贪心思路算法解析java代码示例 活动选择问题问题描述贪心思路算法解析java代码示例 车辆路径问题问题描述贪心思路算法分析java代码示例 定义 贪心算法是指在求解问题时&#xff0c;总是做出在当前…...

【Iot】前端串口serialport.js串口通信库快速入门(附经验总结)

前端串口serialport.js串口通信库快速入门(附经验总结) 一、serialport简介1.1 安装1.2 基本用法1.3 完整示例代码二、问题2.1 数据包被拆分(已解决)2.2 串口返回的多种数据,如何区分类别(待解决)公司项目需要开发一个windows客户端,提供串口modbusRTU数据读取、处理、显…...

【学一点儿前端】本地或jenkins打包报错:getaddrinfo ENOTFOUND registry.nlark.com

问题 今天jenkins打包一个项目&#xff0c;发现报错了 error An unexpected error occurred: “https://registry.nlark.com/xxxxxxxxxx.tgz: getaddrinfo ENOTFOUND registry.nlark.com”. 先写解决方案 把yarn.lock文件里面的registry.nlark.com替换为registry.npmmirror.…...

STEM真题 第五题 比 n 小的最大数

题目描述 给定一个正整数 n&#xff0c;请将 n 中的每位数字重新排列并组成一个新数&#xff0c;要求新数的值要小于 n&#xff0c;请找出所有 符合要求的新数中最大的那个正整数&#xff0c;如果不存在这样的正整数&#xff0c;则输出 -1。例 1&#xff1a;n 312&#xff0…...

Mysql基础操作(1)

目录 简介 1. 数据库的创建与删除 1.1 创建数据库 1.2 删除数据库 2. 表的创建与删除 2.1 创建表 2.2 删除表 3. 数据插入 4. 数据查询 4.1 基本查询 4.2 条件查询 4.3 多条件查询 4.4 排序查询 4.5 分页查询 5. 数据更新 6. 数据删除 7. 总结 简介 MySQL 是一…...

React Image Crop——在React应用中轻松实现图片裁剪功能

React Image Crop是一个用于在React应用程序中裁剪和调整图像的库。它提供了一个简单而强大的界面&#xff0c;允许用户选择和调整裁剪区域&#xff0c;并生成裁剪后的图像。 什么是React Image Crop&#xff1f; React Image Crop是一个开源的React组件&#xff0c;用于在浏览…...

CQRS Design Pattern in Microservices - CQRS模式

原文链接 CQRS Design Pattern in Microservices - GeeksforGeeks 【文章看起来像是AI写的。。。 &#x1f602;&#x1f602;&#x1f602;】 简介 实现步骤 1&#xff0c;识别有界上下文&#xff1a;&#xff08;Identify Bounded Contexts:&#xff09; 2&#xff0c;命…...

Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:药品进销存信息管理系统(前后端源码 + 数据库 sql 脚本)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 项目介绍 1.1 项目功能 2.0 用户登录功能 3.0 首页界面 4.0 供应商管理功能 5.0 药品管理功能 6.0 采购记录管理功能 7.0 销售记录管理功能 8.0 退货记录管理功能…...

主流webgl 引擎 glsl 如何升级webgpu为 wgsl?

0、背景 SPIR-V、GLSL 和 WGSL 是三种不同的着色语言或中间表示形式&#xff0c;它们在现代图形编程中的关系如下&#xff1a; 1、playcanvas 方案: glsl 转 SPIR-V 转 wgsl 调研版本: "version": "2.4.0-dev"webgpu-shader.js transpile(src, shader…...

SSL证书部署(linux-nginx)

一、SSL证书的作用 HTTP协议无法加密数据,数据传输可能产生泄露、篡改或钓鱼攻击等问题。 SSL证书部署到Web服务器后,可帮助Web服务器和网站间建立可信的HTTPS协议加密链接,为网站安全加锁,保证数据安全传输。 二、前提条件 1.已通过数字证书管理服务控制台签发证书。 …...

SpringBoot3.3.0集成Knife4j4.5.0实战

原SpringBoot2.7.18升级至3.3.0之后&#xff0c;Knife4j进行同步升级(Spring Boot 3 只支持OpenAPI3规范)&#xff0c;从原3.0.3(knife4j-spring-boot-starter)版本升级至4.5.0(knife4j-openapi3-jakarta-spring-boot-starter)&#xff0c;以下是升级过程与注意事项等 版本信息…...

C# 的反射窗体的使用

C# 的反射窗体的使用 using System; using System.Reflection; using System.Windows.Forms;public class ReflectedFormFactory {public static Form CreateForm(string formName, string assemblyName){// 加载程序集Assembly assembly Assembly.Load(assemblyName);// 获取…...

大模型呼出机器人能够解决哪些问题?

大模型呼出机器人能够解决哪些问题&#xff1f; 原作者&#xff1a;开源呼叫中心FreeIPCC&#xff0c;其Github&#xff1a;https://github.com/lihaiya/freeipcc 大模型呼出机器人作为现代科技在客户服务领域的创新应用&#xff0c;能够解决多个方面的问题&#xff0c;以下是…...

密码学——密码学概述、分类、加密技术(山东省大数据职称考试)

大数据分析应用-初级 第一部分 基础知识 一、大数据法律法规、政策文件、相关标准 二、计算机基础知识 三、信息化基础知识 四、密码学 五、大数据安全 六、数据库系统 七、数据仓库. 第二部分 专业知识 一、大数据技术与应用 二、大数据分析模型 三、数据科学 密码学 大数据…...

Linux 入门教程:从命令行开始

Linux 是一个强大且灵活的操作系统&#xff0c;广泛应用于服务器、嵌入式设备、开发环境等领域。如果你是刚接触 Linux 的新手&#xff0c;最重要的一步就是掌握命令行操作。虽然 Linux 提供了图形界面&#xff0c;但很多强大功能只能通过命令行来实现。今天&#xff0c;我们就…...

Python中的异步编程:从基础到实践

在现代编程中,异步编程已经成为提高程序性能和响应能力的重要手段。Python,作为一种动态、解释型的高级编程语言,提供了多种异步编程的解决方案。本文将从Python异步编程的基础知识出发,逐步深入到实际应用中,帮助读者理解和掌握这一技术。 1. 异步编程简介 异步编程是一…...

如何使用 Python 实现简单的 Web 服务器?

为了实现一个简单的Web服务器&#xff0c;Python提供了多种方法。对于快速原型设计和学习目的来说&#xff0c;最简单的方法之一是使用内置的http.server模块。 然而&#xff0c;在实际开发中&#xff0c;更常见的做法是使用像Flask或Django这样的框架来构建更为复杂的应用程序…...