2023-2-10刷题情况
青蛙过河
题目描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃 后使石头高度下降到 0 是允许的)。
小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过
y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式
输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。
第二行包含 n−1 个非负整数 1,2,⋯,H1,H2,⋯,Hn−11,2,⋯,H _1,H_2,⋯,H_n−11,2,⋯,H1,H2,⋯,Hn−1 , 其中 HiH_iHi 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 HiH_iHi 的石头, HiH_iHi =0 表示这个位置没有石头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例
样例输入
5 1
1 0 1 0
样例输出
4
样例说明
由于只有两块高度为 1 的石头,所以往返只能各用一块。第 1 块石头和对岸的距离为
4,如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。
评测用例规模与约定
30% : n <= 100
50% : n <= 1000
100%:1<=n<=105,1<=x<=109,1<=HI<=1041 <= n <= 10^5, 1 <= x <= 10^9, 1 <= H_I <= 10^41<=n<=105,1<=x<=109,1<=HI<=104
运行限制
- 最大限制时间: 1s
- 最大空间限制:256MB
思路
尽量大的里面选最小,很有可能是要使用二分(做题做出来的规律),能够跳跃的长度即为区间长度,能够跳过当前区间的条件是,当前区间的石头的长度和大于等于2x,区间长度在枚举的过程中需要逐步递增,且当前区间的石头总和在递增,这便有了单调性,然后就是在满足条件后,取最小值。
代码实现
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int n, k;static int[] arr;public static void main(String[] args) {Scanner sc = new Scanner(System.in);//在此输入您的代码...n = sc.nextInt();k = sc.nextInt();arr = new int[n];for(int i = 1; i < n; i++){arr[i] = arr[i-1] + sc.nextInt();}int l = 0, r = n+1;while(l < r){int mid = (l + r) >> 1;if(judge(mid)) r = mid;else l = mid + 1;}System.out.println(l);sc.close();}private static boolean judge(int x){int min = Integer.MAX_VALUE;for(int i = 1; i + x <= n; i++){min = Math.min(min, arr[i+x-1] - arr[i-1]);}if(min >= 2 * k) return true;return false;}
}
在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
样例
样例输入
nums = [5,7,7,8,8,10], target = 8
nums = [5,7,7,8,8,10], target = 6
nums = [], target = 0
样例输出
[3,4]
[-1,-1]
[-1,-1]
提示
- 0<=nums.length<=1050 <= nums.length <= 10^50<=nums.length<=105
- −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109
- nums是一个非递减数组nums 是一个非递减数组nums是一个非递减数组
- −109<=target<=109-10^9 <= target <= 10^9−109<=target<=109
思路
标准二分咯,今天就是做完上一题后,感觉自己的二分还不够熟练,今天特地练习一下。
代码实现
class Solution {public int[] searchRange(int[] nums, int target) {if(nums.length == 0) return new int[]{-1, -1};int[] ans = new int[2];int l = 0, r = nums.length;// 左闭右开区间,当nums[mid]= target时,r = mid, 也是一直在缩小区间范围。// 单一个开区间,开右区间好点,开左区间mid似乎得向上取整。// 这个二分的结果为第一个出现target的位置。while(l < r){int mid = (l + r) / 2;if(nums[mid] < target) l = mid + 1;else r = mid;}if(l == nums.length || nums[l] != target) return new int[]{-1, -1};ans[0] = (nums[l] == target ? l : -1);l = 0;r = nums.length - 1;// 左闭右闭区间,这样子容易求的第一个出现target和最后一个出现target的位置。// 改改if的条件技能修改结果为第一个出现target的位置或最后一个出现target的位置。while(l <= r){int mid = (l + r) / 2;if(nums[mid] > target) r = mid - 1;else l = mid + 1;}/* 左闭由开区间,但是mid得向上取整,即(left+right+1)/ 2;求的是最后一个出现target的位置。while(l < r){int mid = (l + r + 1) / 2;if(nums[mid] > target) r = mid - 1;else l = mid;}*/ans[1] = (nums[r] == target ? r : -1);return ans;}
}
掷骰子模拟
题目描述
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i](i 从 1 开始编号)。
现在,给你一个整数数组 rollMax 和一个整数 n,请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同,就认为这两个序列是不同的。由于答案可能很大,所以请返回 模 10^9 + 7 之后的结果。
样例
样例输入
n = 2, rollMax = [1,1,2,2,2,3]
n = 2, rollMax = [1,1,1,1,1,1]
n = 3, rollMax = [1,1,1,2,2,3]
样例输出
34
我们掷 2 次骰子,如果没有约束的话,共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组,数字 1 和 2 最多连续出现一次,所以不会出现序列 (1,1) 和 (2,2)。因此,最终答案是 36-2 = 34。
30
181
提示
- 1 <= n <= 5000
- rollMax.length == 6
- 1 <= rollMax[i] <= 15
思路
最优结果肯定为动态规划,但是,动态规划的转移转移方程式并不是很容易就想出来的。借此题使得如何将算法优化至动态规划。
代码实现
暴力递归模拟,递归程序中有几个需要关注的信息,上一个点数,持续了几个次,当前投掷了几个骰子。
暴力递归模拟,时间复杂度属于指数级,还是很容易超时的。
class Solution {private static final int MOD = (int)1e9+7;int[] rollMax;public int dieSimulator(int n, int[] rollMax) {int max = Arrays.stream(rollMax).max().getAsInt();this.rollMax = rollMax;cache = new int[n][6][max];for(int i = 0; i < n; i++)for(int j = 0; j < 6; j++)Arrays.fill(cache[i][j], -1);long res = 0;for(int i = 0; i < 6; i++){res += dfs(n-1, i, rollMax[i]-1);}return (int)(res % MOD);}private int dfs(int i, int last, int left){if(i == 0) return 1;long res = 0;for(int k = 0; k < 6; k++){if(k != last) res += dfs(i-1, k, rollMax[k]-1);else if(left > 0) res += dfs(i-1, k, left-1);}return (int)(res % MOD);}
}
记忆化搜索,将已经计算过的结果记录下来,下次遇到同等情况,直接返回记录的结果即可。
将已经计算的结果记录下来,能过很大程度的降低时间复杂度。
class Solution {private static final int MOD = (int)1e9+7;int[] rollMax;int[][][] cache;public int dieSimulator(int n, int[] rollMax) {int max = Arrays.stream(rollMax).max().getAsInt();this.rollMax = rollMax;cache = new int[n][6][max];for(int i = 0; i < n; i++)for(int j = 0; j < 6; j++)Arrays.fill(cache[i][j], -1);long res = 0;for(int i = 0; i < 6; i++){res += dfs(n-1, i, rollMax[i]-1);}return (int)(res % MOD);}private int dfs(int i, int last, int left){if(i == 0) return 1;if(cache[i][last][left] != -1) return cache[i][last][left];long res = 0;for(int k = 0; k < 6; k++){if(k != last) res += dfs(i-1, k, rollMax[k]-1);else if(left > 0) res += dfs(i-1, k, left-1);}return cache[i][last][left] = (int)(res % MOD);}
}
动态规划
记忆化的递归即是自上向下的执行程序,其实在递归的时候,状态转移方程式,就已经写在递归函数中了。
只需将自上向下的程序修改为自下向上,就是动态规划。
class Solution {private static final int MOD = (int)1e9+7;public int dieSimulator(int n, int[] rollMax){int len = rollMax.length;int max = Arrays.stream(rollMax).max().getAsInt();var dp = new long[n][6][max];for(int i = 0; i < 6; i++)Arrays.fill(dp[0][i], 1);for(int i = 1; i < n; i++){for(int last = 0; last < 6; last++){for(int left = 0; left < max; left++){long res = 0;for(int j = 0; j < len; j++){if(j != last) res += dp[i-1][j][rollMax[j]-1];else if(left > 0) res += dp[i-1][j][left-1];}dp[i][last][left] = res % MOD;}}}long ans = 0;for(int i = 0; i < 6; i++) ans += dp[n-1][i][rollMax[i]-1];return (int)(ans % MOD);}
}
相关文章:
2023-2-10刷题情况
青蛙过河 题目描述 小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头…...

Python学习-----无序序列2.0(集合的创建、添加、删除以及运算)
目录 前言: 什么是集合 集合的三大特性 1.集合的创建 (1)直接创建 (2)强制转换 2.集合的添加 (1)add()函数 (2)update() 函数 3.集合元…...
2023最详细的接口测试用例设计教程
一、接口测试流程 1、需求讨论 2、需求评审 3、场景设计 4、数据准备 5、测试执行 二、分析接口文档元素 1、接口名称 2、接口地址 3、支持格式 4、请求方式 5、请求参数(参数名称、类型、是否必填、参数说明等) 6、返回参数(返回…...

【数据库】 数据库的理论基础详解
目录 一, 什么是数据库 二, 数据库管理系统(DBMS) 三,数据库与文件系统的区别 1,对比区别: 2,优缺点总结: 四,数据库的发展史 五,常见数据库 1, 关系型…...

Linux环境运行Maven 生成的hadoop jar包
运行命令: hadoop jar ./jar包名字 class对象路径 输入路径 输出路径 linux内部jar包测试 cd 到以下目录,创建以下文件夹 [rootreagan180 ~]# cd /opt/soft/hadoop313/share/hadoop/mapreduce/ 创建文件夹(读取路径) [roo…...

ThreadPoolExecutor原理解析
1. 工作原理1.1 流程图1.2 执行示意图从上图得知如果当前运行的线程数小于corePoolSize(核心线程数),则会创建新线程作为核心线程来执行任务(注意,执行这一步需要获取全局锁)。如果运行的线程等于或多于corePoolSize,则将任务加入BlockingQue…...

谷粒学苑第二章前端框架-2.2前端框架开发过程
一、前端框架开发过程 第一步:添加路由 src/router模块用来管理路由。 第二步:点击某个路由,显示路由对应页面内容 component: () > import(/views/table/index), 表示路由对应的页面,是views/table/index.vue页面 第三步&a…...

权限管理实现的两种方式(详解)
登录的接口请求的三个内容:1. token2. 用户信息、角色信息3. 菜单信息第一种:基于角色Role的动态路由管理 (不推荐,但市场用的比较多)首先列出枚举每个角色对应几个路由,然后根据用户登录的角色遍历枚举出来的角色动态注册对应的路…...
【C++】智能指针思路解析和模拟实现
此篇文章就从以下几个方面出发,带你了解智能指针的方方面面1.为什么需要智能指针当我们开辟内存并使用的时候,我们的顺序应该是这样:开辟内存-》使用内存-》释放内存问题就出现在第三步,开辟好了,也使用了,…...
SpringCloud(18):Sentinel流控降级入门
Sentinel本地应用流控降级实现分为三步: 创建本地应用搭建本地Sentinel控制台本地应用接入本地Sentinel控制台1 本地应用创建 整体流程分析 创建springboot项目在项目的pom.xml文件中引入sentinel-core的依赖坐标创建TestController,定义使用限流规则运行测试具体流程 1.创…...

C++【多态】
文章目录1、多态的概念2、多态的定义及实现2-1、多态的构成条件2-2、虚函数2-3、虚函数的重写2-4 多态样例2-5、协变2-6、 析构函数与virtual2-7、函数重载、函数隐藏(重定义)与虚函数重写(覆盖)的对比2-8、override 和 final&…...
缓存预热、缓存雪崩、缓存击穿、缓存穿透,你真的了解吗?
缓存穿透、缓存击穿、缓存雪崩有什么区别,该如何解决? 1.缓存预热 1.1 问题描述 请求数量较高,大量的请求过来之后都需要去从缓存中获取数据,但是缓存中又没有,此时从数据库中查找数据然后将数据再存入缓存…...

【Java基础】018 -- 面向对象阶段项目上(拼图小游戏)
目录 拼图小游戏(GUI) 一、主界面分析 1、练习一:创建主界面1 2、练习二:创建主界面2(JFrame) 3、练习三:在游戏界面中添加菜单(JMenuBar) ①、菜单的制作 4、添加图片&a…...

【网络~】
网络一级目录二、socket套接字三、UDP数据报套接字四、TCP流套接字一级目录 1.局域网、广域网 2.IP地址是什么? IP地址是标识主机在网络上的地址 IP地址是如何组成的? 点分十进制,将32位分为四个部分,每个部分一个字节ÿ…...
手写JavaScript中的call、bind、apply方法
手写JavaScript中的call、bind、apply方法 call方法 call() 方法使用一个指定的 this 值和单独给出的一个或多个参数来调用一个函数。 function Product(name, price) {this.name name;this.price price; }function Food(name, price) {Product.call(this, name, price);t…...
JAVA练习46-将有序数组转换为二叉搜索树
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 前言 提示:这里可以添加本文要记录的大概内容: 2月10日练习内容 提示:以下是本篇文章正文内容,下面案例可供参考 一、题目-…...

linux(centos7.6)docker
官方文档:https://docs.docker.com/engine/install/centos/1安装之前删除旧版本的docker2安装yum install-y yum-utils3配置yum源 不用官网的外国下载太慢 推荐阿里云yum-config-manager --add-repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.r…...
微信小程序滚动穿透问题
文章目录1、catchtouchmove"true"2、page-meta3、wx.setPageStyle做小程序的开发业务中,经常会使用弹窗,当弹窗里的内容过多时,要滚动查看,然后经常会遇到滚动弹窗,弹窗底下页面也跟着滚。解决思路ÿ…...

安全—06day
负载均衡反向代理下的webshell上传负载均衡负载均衡下webshell上传的四大难点难点一:需要在每一台节点的相同位置上传相同内容的webshell难点二:无法预测下一次请求是哪一台机器去执行难点三:当我们需要上传一些工具时,麻烦来了&a…...

PostgreSQL入门
PostgreSQL入门 简介 PostgreSQL是以加州大学伯克利分校计算机系开发的POSTGRES, 版本 4.2为基础的对象关系型数据库管理系统(ORDBMS) 支持大部分SQL标准并且提供了许多现代特性 复杂查询外键触发器可更新视图事务完整性多版本并发控制 …...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...