跳房子(字节算法题)

2023-10-07 18:50
文章标签 算法 字节 跳房子

本文主要是介绍跳房子(字节算法题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

存在n+1个房间,每个房间依次为房间1 2
3…i,每个房间都存在一个传送门,i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问),每次移动他有两种移动策略:
A. 如果访问过当前房间 i 偶数次,那么下一次移动到房间i+1;
B. 如果访问过当前房间 i 奇数次,那么移动到房间pi; 现在路人甲想知道移动到房间n+1一共需要多少次移动;

输入描述: 第一行包括一个数字n(30%数据1<=n<=100,100%数据 1<=n<=1000),表示房间的数量,接下来一行存在n个数字
pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述: 输出一行数字,表示最终移动的次数,最终结果需要对1000000007 (10e9 + 7) 取模。
示例1
输入
3
1 2 2

输出
8

思路:动态规划

在这里插入图片描述
递推:
dp[i]表示走到第i个房子前经历的步数
dp[1] = 0
dp[2] =2
dp[3] =4
dp[4] = dp[3]+1 +(dp[3]-dp[2])+1

找规律:i从1开始
dp[1] =0
当p[i] == i 时 dp[i] =dp[i-1]+2;
当p[i] != i 时 dp[i] = dp[i-1] +1+(dp[i-1]-dp[p[i-1]])+1=2*dp[i-1] - dp[p[i-1]] +2;

再进行合并:
dp[1] =0
当i>1时: dp[i] =2*dp[i-1] - dp[p[i-1]] +2;

题解(java)

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] p = new int[n+1];long[] dp = new long[n+2];dp[1]=0;p[1] = in.nextInt();long mod = (long)(1e9+7);for(int i=2;i<=n;i++){p[i] = in.nextInt();dp[i] = (2*dp[i-1]-dp[p[i-1]]+2) % mod;}dp[n+1] = (2*dp[n]-dp[p[n]]+2) % mod;
//        System.out.println(dp[n+1]);System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);}
}

测试用例:
70
1 1 2 3 4 3 5 2 2 4 8 6 13 6 13 3 5 4 5 10 11 9 11 8 12 24 21 6 9 29 25 31 17 27 3 17 35 5 21 11 27 14 33 7 33 44 22 33 21 11 38 46 53 46 3 22 5 27 55 22 41 25 56 61 27 28 11 66 68 13

一开始对第一次输出的dp[n+1]为负值不理解,将所有的dp[i]与dp[p[i]]的情况输出:
发现%mod操作后,存在 2dp[i-1]< dp[p[i-1]的情况

dp[1]0  dp[p[1]0
dp[2]2  dp[p[2]0
dp[3]6  dp[p[3]2
dp[4]12  dp[p[4]6
dp[5]20  dp[p[5]12
dp[6]30  dp[p[6]6
dp[7]56  dp[p[7]20
dp[8]94  dp[p[8]2
dp[9]188  dp[p[9]2
dp[10]376  dp[p[10]12
dp[11]742  dp[p[11]94
dp[12]1392  dp[p[12]30
dp[13]2756  dp[p[13]2756
dp[14]2758  dp[p[14]30
dp[15]5488  dp[p[15]2756
dp[16]8222  dp[p[16]6
dp[17]16440  dp[p[17]20
dp[18]32862  dp[p[18]12
dp[19]65714  dp[p[19]20
dp[20]131410  dp[p[20]376
dp[21]262446  dp[p[21]742
dp[22]524152  dp[p[22]188
dp[23]1048118  dp[p[23]742
dp[24]2095496  dp[p[24]94
dp[25]4190900  dp[p[25]1392
dp[26]8380410  dp[p[26]2095496
dp[27]14665326  dp[p[27]262446
dp[28]29068208  dp[p[28]30
dp[29]58136388  dp[p[29]188
dp[30]116272590  dp[p[30]58136388
dp[31]174408794  dp[p[31]4190900
dp[32]344626690  dp[p[32]174408794
dp[33]514844588  dp[p[33]16440
dp[34]29672731  dp[p[34]14665326
dp[35]44680138  dp[p[35]6
dp[36]89360272  dp[p[36]16440
dp[37]178704106  dp[p[37]44680138
dp[38]312728076  dp[p[38]20
dp[39]625456134  dp[p[39]262446
dp[40]250649817  dp[p[40]742
dp[41]501298894  dp[p[41]14665326
dp[42]987932464  dp[p[42]2758
dp[43]975862165  dp[p[43]514844588
dp[44]436879737  dp[p[44]56
dp[45]873759420  dp[p[45]514844588
dp[46]232674247  dp[p[46]436879737
dp[47]28468759  dp[p[47]524152
dp[48]56413368  dp[p[48]514844588
dp[49]-402017850  dp[p[49]262446
dp[50]-804298144  dp[p[50]742
dp[51]-608597021  dp[p[51]312728076
dp[52]-529922109  dp[p[52]232674247
dp[53]-292518456  dp[p[53]-292518456
dp[54]-292518454  dp[p[54]232674247
dp[55]-817711153  dp[p[55]6
dp[56]-635422303  dp[p[56]524152
dp[57]-271368749  dp[p[57]20
dp[58]-542737516  dp[p[58]14665326
dp[59]-100140349  dp[p[59]-817711153
dp[60]617430457  dp[p[60]524152
dp[61]234336757  dp[p[61]501298894
dp[62]-32625378  dp[p[62]4190900
dp[63]-69441654  dp[p[63]-635422303
dp[64]496538997  dp[p[64]234336757
dp[65]758741239  dp[p[65]14665326
dp[66]502817147  dp[p[66]29068208
dp[67]976566088  dp[p[67]742
dp[68]953131429  dp[p[68]502817147
dp[69]403445706  dp[p[69]953131429

java中%运算
-5%3=-5-(-5/3向下取整 *3)=-5-(-3)=-2

这篇关于跳房子(字节算法题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/159743

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系