首页 > 试题广场 >

牛妹的项链

[编程题]牛妹的项链
  • 热度指数：630 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛妹收到了一个项链，这个项链一共有n个珠子，每个珠子都有一个颜色a_i。这n个珠子构成了一个环。

不知为何，牛妹想从项链上截下一段连续的珠子，但是牛妹不喜欢同一个颜色出现两次，所以截下来的这一段珠子中没有相同的颜色。现在牛妹想知道她可以截下的最长的一段珠子为多长？

第个珠子与第个珠子和第个珠子相邻。(i>1且i<n)
特别的，与第1个珠子相邻的珠子为第2个，第n个珠子。
与第n个珠子相邻的珠子为第n-1个，第1个珠子。
示例1

输入

4,[3,1,1,2]

输出

3

说明

牛妹可以选择在第3个珠子的左边和右边各切一刀，截取第4个，第1个和第2个珠子连起来的连续珠子。

备注:

第一个参数n代表珠子个数
第二个参数vector<int> a包含n个元素代表每个珠子的颜色。
算法知识视频讲解
开通博客
头像 球球了给孩子一个offer吧
发表于 2021-08-11 17:50:08
题目关键信息：1.数组a代表项链的每颗珠子，不同的数字代表不同颜色的珠子，而且这是个环形数组，首尾是相连的2.求最长连续不重复子序列的长度方法一：暴力用list存储最长不重复子序列，因为是环形珠子，考虑首尾相连的情况，将珠子复制一份接到后面，因此循环从0到2n，每次取a[i%n],如果list中不存 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-11 21:10:26
题意整理 牛妹有一条由n个珠子组成的项链，每个珠子都有自己的颜色。 现在牛妹要截取一段尽可能长的珠子，但是截下的这一段不能有相同颜色的珠子。 方法一（暴力统计） 1.解题思路 简要分析：由于项链总共有n颗珠子，我们可以枚举所有的起始位置，然后从每个起始位置开始，最多截取n个珠子，每一个起始位置（ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-10 19:50:07
思路： 题目的主要信息： 用数组a表示项链的不同颜色，即不同数字表示不同颜色，且首尾相接 从数组中取出一段数字都不同的连续子序列，求子序列最长长度，需要注意首尾相接的情况 方法一：动态规划具体做法：我们可以将数组首尾相接，组成一个的新数组，就不需要再处理循环了。我们用表示以第个珠子结尾的最长连续 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 SandMonth
发表于 2021-09-13 08:51:01
牛妹的项链 有一个项链共有n个珠子,每个珠子都有一个颜色,这n珠子构建成一个环,牛妹想要一段最长的珠子其中同一个颜色不出现两次。 案例输入：4,[3,1,1,2]返回值：3说明：牛妹可以选择在第3个珠子的左边和右边各切一刀，截取第4个，第1个和第2个珠子连起来的连续珠子。 方法一 暴力 遍历a中 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-15 19:36:43
题目描述牛妹收到了一个项链，这个项链一共有n个珠子，每个珠子都有一个颜色 ai 。这n个珠子构成了一个环。 不知为何，牛妹想从项链上截下一段连续的珠子，但是牛妹不喜欢同一个颜色出现两次，所以截下来的这一段珠子中没有相同的颜色。现在牛妹想知道她可以截下的最长的一段珠子为多长？ 第i个珠子与第i+1个珠 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
5条回答 2460浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号