刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

密码锁

提示信息:

密码锁:由 n 个从左到右并排的圆环组成,每个圆环上都有 10 个数字(0~9),蓝色框内为密码显示区,每个圆环在密码显示区只能显示一个数字,如图所示。可以拨动圆环,来改变密码显示区显示的数字。

当密码显示区的数字与密码一致时,密码锁就会被打开。

编程实现:

有一个由 n 个圆环组成的密码锁,和一个 n 位的密码 S(S 由 1~9 中的数字(包含 1 和 9)组成)。每次操作只能选择一个或位置连续的多个圆环拨动。当 S 中的字符从左到右依次显示在密码显示区时,密码锁会被打开。

已知每个圆环在密码显示区初始数字都为 0,请计算最少需要操作多少次,才能打开密码锁。

注意:

1、如果选择了其中一个圆环,可将该圆环中任意一个数字拨动到密码显示区,表示 1 次操作;

例如:将第 3 个圆环拨动到数字 4,表示 1 次操作:

2、如果选择了位置连续的多个圆环,只能将这些圆环拨动成同一个数字,显示在密码显示区,表示 1 次操作。

例如:将连续的第 2 个到第 3 个圆环都拨动到数字 5,表示 1 次操作:

例如:n = 5,S = "12321";分别表示 5 个圆环组成的密码锁和密码 12321;将 5 位密码 1、2、3、2、1从左到右依次显示在密码显示区,以下是操作次数最少的方案:

第一次操作,将 5 个初始状态为 0 的圆环全部拨动到数字 1:

第二次操作,将第 2 个到第 4 个圆环全部拨动到数字 2:

第三次操作,将第 3 个圆环拨动到数字 3:

最少需要操作 3 次,才能打开密码锁。

输入描述:

第一行输入一个整数 n(1≤n≤100),表示组成的密码锁的圆环数及密码的位数

第二行输入一个长度为 n 的字符串 S,S 由 1~9 中的数字(包含 1 和 9)组成,表示密码

输出描述:

输出一个整数,表示最少需要操作多少次,才能打开密码锁


样例输入:

5
12321

样例输出:

3

使用微信搜索喵呜刷题,轻松应对考试!

答案:

根据题目描述,我们需要计算最少需要操作多少次,才能打开密码锁。首先,我们需要遍历密码S中的每个字符,对于每个字符,我们需要找到密码显示区中需要拨动的圆环,并将这些圆环拨动到当前字符。对于每个字符,我们需要找到所有需要拨动的圆环,这可以通过比较密码S中的当前字符和密码显示区中对应位置的字符来实现。如果密码显示区中对应位置的字符为0,则需要拨动该位置的圆环。然后,我们需要计算需要拨动的圆环数,这可以通过遍历密码S中的每个字符,并计算需要拨动的圆环数来实现。如果当前字符和上一个字符相同,则只需要拨动当前位置的圆环;否则,需要拨动从上一个不同字符的位置到当前位置的所有圆环。最后,我们将所有需要拨动的圆环数相加,即可得到最少需要操作多少次,才能打开密码锁。

解析:

【喵呜刷题小喵解析】:
本题是一道经典的动态规划问题,可以通过遍历密码S中的每个字符,并计算需要拨动的圆环数来实现。

首先,我们需要将密码显示区中的所有圆环都拨动到数字0,这可以通过一次操作完成。

然后,我们遍历密码S中的每个字符,对于每个字符,我们需要找到需要拨动的圆环,并将这些圆环拨动到当前字符。对于每个字符,我们需要找到所有需要拨动的圆环,这可以通过比较密码S中的当前字符和密码显示区中对应位置的字符来实现。如果密码显示区中对应位置的字符为0,则需要拨动该位置的圆环。

在遍历密码S中的每个字符时,我们需要记录需要拨动的圆环数,这可以通过使用一个变量来记录已经拨动的圆环数,并在需要拨动圆环时将其加1。

最后,我们将所有需要拨动的圆环数相加,即可得到最少需要操作多少次,才能打开密码锁。

需要注意的是,在遍历密码S中的每个字符时,我们需要特别处理密码S中的每个字符和上一个字符相同的情况。如果当前字符和上一个字符相同,则只需要拨动当前位置的圆环;否则,需要拨动从上一个不同字符的位置到当前位置的所有圆环。这是因为,如果当前字符和上一个字符相同,那么密码显示区中对应位置的字符已经为当前字符,不需要再次拨动。

因此,我们可以使用动态规划的思想,通过遍历密码S中的每个字符,并计算需要拨动的圆环数,来求解最少需要操作多少次,才能打开密码锁。
创作类型:
原创

本文链接:密码锁 提示信息: 密码锁:由 n 个从左到右并排的圆环组成,每个圆环上都有 10 个数字(0~9)

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share