首页 > 试题广场 >

用 0 - 9 这 10 个数字组成一个首尾相连的字符串，每

[单选题]
用 0 - 9 这 10 个数字组成一个首尾相连的字符串，每个数字可以重复出现多次，并且字符串中任意 2 个数字都相邻出现过。此字符串最小长度是（） 
  • 47
  • 48
  • 49
  • 50
查看答案及解析
添加回答
高辉_gh头像 高辉_gh
很简单，数字0必须与其他9个数字相邻，则0最少出现5次。每个数字的地位均等，根据对称性，50
发表于 2019-04-01 00:08:24 回复(7)
ChubbyDog头像 ChubbyDog
将每一个数字看作一个节点，因为数字组成环，所以每一个节点(数字)的出度(OD)等于入度(ID)。

当看作是完全无向图的时候，共有 n*(n-1)/2条边，每一个节点有(n-1)条边。
（1）当节点数目n为奇数的时候，每一个节点有(n-1)条边，此时的n-1为偶数，如果直接将边变为有向的（不增加边数，只是将无向边变为有向的出或入边），可以有(n-1)/2条出边或入边。 此时的边数目为 n*(n-1) /2 ，对应的节点也为 n*(n-1) /2

(2) 当节点数n为偶数的时候，每一节点有(n-1)条边，但此时n-1为奇数，无法分出均等的出边和入边，也就是说会存在某个节点用尽这n-1条边时还存节点尚未访问，此时只有再附加出边，使出度等于入度。所以要附加出边或者入边，最少的附加方案就是让每条边的出度=入度。也就是出度=入度=⌈(n-1)/2⌉ 。此时的节点数目(边数目) = n * (⌈(n-1)/2⌉)  = n*n /2 。

总结： 数字数目 = n * (⌈( n - 1 ) / 2 ⌉)

本题中节点数目为n=10，为偶数，所以需要的数字数目为10 * 10 / 2 = 50

--------------------
利用对称性只能解决数字为偶数的情形，在数字为奇数的时候，

发表于 2020-08-02 09:49:17 回复(1)
光电管头像 光电管
就我没看懂这道题啥意思吗
发表于 2022-03-06 16:15:48 回复(0)
大卫不加班头像 大卫不加班
完全无向图，边的数量
发表于 2019-09-02 22:43:25 回复(5)
长夜漫漫头像 长夜漫漫
一个数字出现一次可以多出两个相邻数字，十个数字去掉本身共需要九个相邻数字，所以一个数字要至少出现五次才能保证它与其它任意数字都相邻出现过，十个数字就是5*10=50个字符串？？？
发表于 2019-03-30 20:39:02 回复(0)
V__z头像 V__z
10个数字，对于每个数字来说，与其他数字相邻最少需要这个数字出现5次，所以10个数字，最少需要出现50次
发表于 2022-09-23 10:03:38 回复(0)
照晾头像 照晾
可以抽象为：完全无向图，从某一个节点出发，每次走一条边，要求可重复的遍历所有的边，并且回到这个节点，最少需要走多少次。
高赞回答只可以证明次数一定不少于50次，但是无法说明50次一定可以走遍所有的边并且回到出发点。
发表于 2021-10-15 22:06:10 回复(0)
16级老腊肉头像 16级老腊肉
由于是首尾相接，所以每个数一定会和两个数相邻，考虑最极端情况，每个数都和两个不同的数相邻，那么要想和其他数都相邻则需该数出现五次，5*10=50
发表于 2019-04-02 19:47:14 回复(0)
牛客200660548号头像 牛客200660548号
忘记算0011这样的了，我说怎么没有正确答案
编辑于 2024-03-14 17:01:21 回复(0)
D5rrr头像 D5rrr
33
发表于 2023-02-12 00:14:03 回复(0)
一个未知程序员头像 一个未知程序员
有没有哪位大佬能把这个字符串写出来，实在想不出
发表于 2022-09-10 10:15:49 回复(0)
不可略懂头像 不可略懂
首尾相连不应该会有一个字符被头尾共用了吗？所以我选了49
发表于 2020-08-15 14:26:29 回复(0)
耀神头像 耀神
数字0必须与其他9个数字相邻，则0最少出现5次。每个数字的地位均等，根据对称性，50
发表于 2019-10-10 23:58:18 回复(0)
提交观点

问题信息

C++工程师 Momenta 字符串 2019 Java工程师
来自：Momenta2019...
上传者：小小
难度：
13条回答 9725浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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