首页 > 试题广场 >

数字字符

[编程题]数字字符
  • 热度指数:3340 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
在十进制表示中,任意一个正整数都可以用字符 ’0’-‘9’ 表示出来。但是当 ’0’-‘9’ 这些字符每种字符的数量有限时,可能有些正整数就无法表示出来了。比如你有两个 ‘1’ ,一个 ‘2’ ,那么你能表示出 11,12,121 等等,但是无法表示出 10,122,200 等数。
现在你手上拥有一些字符,它们都是 ’0’-‘9’ 的字符。你可以选出其中一些字符然后将它们组合成一个数字,那么你所无法组成的最小的正整数是多少?

数据范围:字符串长度满足 ,字符串中只包含 '0'-'9' 字符。

输入描述:
第一行包含一个字符串,表示你可以使用的字符。


输出描述:
输出你所无法组成的最小正整数
示例1

输入

55

输出

1
示例2

输入

123456789

输出

10
#方法很明了,一看就懂,大家加油!

arr = input()
#输入列表
list1 = []
for i in arr:
list1.append(int(i))
# 0--9
list2 = [0,1,2,3,4,5,6,7,8,9]
#存入缺失的数字(已经有序)
list3 = []
for i in list2:
if i not in list1:
list3.append(i)
list4 = []    #出现次数
#判断缺不缺
if len(list3) == 1:
if list3[0] == 0:
pass
else:
MIN = list3[0]
print(MIN)
elif len(list3) >1:
if list3[0] == 0:
MIN = list3[1]
print(MIN)
else:
MIN = list3[0]
print(MIN)
else:
list4.append(list1.count(1))
list4.append(list1.count(2))
list4.append(list1.count(3))
list4.append(list1.count(4))
list4.append(list1.count(5))
list4.append(list1.count(6))
list4.append(list1.count(7))
list4.append(list1.count(8))
list4.append(list1.count(9))
# 出现最少的次数
min_count = min(list4)
# 出现次数最少的 数字,此处取索引的特点是:相同出现次数,只取第一次出现的位置,再 +1,相当于直接排序

# 即:不缺数字的情况下,出现次数最少的 最小的数字是 :
num = list4.index(min_count) + 1
count = min_count
for i in range(count+1):
print(num,end='')
编辑于 2019-08-07 14:54:25 回复(0)

#!/usr/bin/env python

#! * coding:utf-8 *

"""
在十进制表示中,任意一个正整数都可以用字符’0’-‘9’表示出来。但是当’0’-‘9’
这些字符每种字符的数量有限时,可能有些正整数就无法表示出来了。比如你有两个‘1’,
一个‘2’,那么你能表示出11,12,121等等,但是无法表示出10,122,200等数。
现在你手上拥有一些字符,它们都是’0’-‘9’的字符。你可以选出其中一些字符然后
将它们组合成一个数字,那么你所无法组成的最小的正整数是多少?
"""
def minInt(num):
num_list = list(str(num))

# print(num_list.sort())
num_list.sort()
# print(num_list)
# 初始化词典,value值为0
d = {}
for i in range(0, 10):
    d[i] = 0

for e in num_list:
    d[int(e)] += 1
l = []
for j in range(0,10):
    if d[j] == 0:
        l.append(j)
# print(l)
if len(l) == 1:
    if l[0] == 0:
        print(10)
    else:
        print(l[0])
else:
    if l[0] == 0:
        print(l[1])
    else:
        print(l[0])

if name == 'main':

# num = 123456789
num = int(input())
minInt(num)
编辑于 2019-04-14 10:15:33 回复(0)
def how(input_num):
    nums = [0]*10
    for i in range(10):
        nums[i] = input_num.count(str(i))
    return nums

input_str = how(input())
num = 1
output = 0
while True:
    if how(str(num)) > input_str:
        print(num)
        break
    num += 1
发表于 2019-04-01 10:27:28 回复(0)
nums = input()
num_count = [0,0,0,0,0,0,0,0,0,0]
for n in nums:
    d = (int)(n)
    if d==0:
        num_count[9] += 1
    else:
        num_count[d-1] += 1
        
min_digit = num_count[0]
min_di = 0
for i in range(1,10):
    if num_count[i] < min_digit:
        min_digit = num_count[i]
        min_di = i

if min_di == 9:
    print('1'+'0'*(min_digit+1))
else:
    print(str(min_di+1)*(min_digit+1))

我的思路是,先看看数据具有怎样的特征:
1-9 ,需要有1-9每个最少有一个
10, 需要有一个0(同时还需要有一个1,但是判断到10的时候肯定已经满足了)
11,需要两个1
12-19,需要的条件之前已经满足了,不可能出问题
20,已经满足
21,已经满足
22,需要两个2
如此类推

最后可以发现这样一个规律:最小的数字,总是和0-9这十个数字里谁最少有关

比如说只有一个1,但是其他数字都有两个,那么就是11成为第一个无法输出的数字;就算有的数字超过了2个,它达到多少,还是被最小的1所阻拦

因此思路就很简单了:
1,算出每个数字的数量
2,找到最少的那个数字
3,根据最少数字的次数得到最小量

这个算法的好处就在于只和输入相关,而与这个最小数字能有多大无关,就算是9999999999,也和1没有什么差别

如果要改进的话,那么就是写一个正则直接找到最少出现的数字已经出现的次数,然后答案就出来了
发表于 2019-01-25 13:25:53 回复(0)

问题信息

上传者:小小
难度:
4条回答 7952浏览

热门推荐

通过挑战的用户

查看代码