首页 > 试题广场 >

脸滚键盘

[编程题]脸滚键盘
  • 热度指数：4720 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

av394281 中，充满威严的蕾米莉亚大小姐因为触犯某条禁忌，被隙间妖怪八云紫（紫m……èi）按住头在键盘上滚动。
同样在弹幕里乱刷梗被紫姐姐做成罪袋的你被指派找到大小姐脸滚键盘打出的一行字中的第 `k` 个仅出现一次的字。
(为简化问题，大小姐没有滚出 ascii 字符集以外的字)


输入描述:
每个输入都有若干行，每行的第一个数字为`k`，表示求第`k`个仅出现一次的字。然后间隔一个半角空格，之后直到行尾的所有字符表示大小姐滚出的字符串`S`。


输出描述:
输出的每一行对应输入的每一行的答案，如果无解，输出字符串`Myon~`

(请不要输出多余的空行）

为了方便评测，如果答案存在且为c，请输出[c]
示例1

输入

2 misakamikotodaisuki
3 !bakabaka~ bakabaka~ 1~2~9!
3 3.1415926535897932384626433832795028841971693993751o582097494459211451488946419191919l91919hmmhmmahhhhhhhhhh
7 www.bilibili.com/av170001
1 111

输出

[d]
[9]
[l]
[7]
Myon~

备注:
字符串S仅包含可见ascii码，长度不超过100000
算法知识视频讲解
添加回答
Python
0b100001101000头像 0b100001101000
334 ms 4484K Python 3 
try:
    while 1:
        s = input().strip().split(' ',1)
        n,l,o,r,f = int(s[0]),s[1],[],[],1
        for i in l:
            if i not in r and l.count(i)==1:
                o.append(i)
                if len(o)==n:
                    print('['+i+']')
                    f = 0
                    break
            else: r.append(i)
        if f: print("Myon~")
except:
    pass
编辑于 2019-09-10 02:10:16 回复(1)
Python
白色纯度头像 白色纯度
这道题目的数据读取有很大问题，思路就是用哈希表存储并记录字符出现的次数。然后遍历字符串，与哈希表中出现一次的字符做统计，统计到k时输出就行。数据读取很重要，不然的话AC率超低！ 
import sys
def kAndsInput(Tmp):
    for i in range(len(Tmp)):
        if Tmp[i] == ' ':
            break
    k = int(Tmp[0:i])
    s = Tmp[i+1:]
    return k, s
def select_kth(s,k):
    if not s:
        return 'Myon~'
    dic = {}
    for i in s:
        dic[i] = dic.get(i,0)+1
    l = 0
    while l<len(s):
        if dic[s[l]]==1:
            k -= 1
            if k==0:
                return '['+s[l]+']'
        l += 1
    return 'Myon~'
if __name__=='__main__':
    Tmp = []
    try:
        while True:
            line = sys.stdin.readline().strip()
            if line == '':
                break
            Tmp.append(line)
    except:
        pass
    for i in range(len(Tmp)):
        k,string = kAndsInput(Tmp[i])
        print(select_kth(string,k))


发表于 2019-08-18 11:27:34 回复(1)
Python
朱兆坤头像 朱兆坤
因为限制了ASCII的字符集，所以可以方便地利用hash表实现O(1)时间的查找。对于每一行输入，得到k和字符串s。第一遍扫描s，建立hash表，如果该字符仅被访问一次，那么hash表对应的位置值为1。第二遍扫描s，就可以得到结果了。这题最头疼的是输入的处理，有哪位大佬看看我这个处理有什么问题？通过的输入处理方式借用@Je t＇aime的方法。
通过的代码： 
import sys
import re
input_strs = []
for s in sys.stdin:
	input_strs.append(s.strip())
# 计算部分, 输入包含多行, 每行单独计算第k个仅出现一次的字符.
for line in input_strs:
	r = re.match('(\d+) (.*)', line)
	if r:
		k = int(r.group(1))
		line_str = r.group(2)
	else:
		continue
	hash_table = [0 for _ in range(128)]
	for i in range(len(line_str)):
		hash_table[ord(line_str[i])] += 1
	# 第二次扫描字符串, 搜索第k个仅出现一次的字符.
	count = 0
	for i in range(len(line_str)):
		if hash_table[ord(line_str[i])] == 1:
			count += 1
		if count == k:
			print('[' + line_str[i] + ']')
			break
	if count < k:
		print('Myon~')
只能通过46.7%的方法： 
# 输入处理
import sys
import re
input_strs = []
for s in sys.stdin:
	input_strs.append(s.strip())
# 计算部分, 输入包含多行, 每行单独计算第k个仅出现一次的字符.
for line in input_strs:
	# k指输入中的k
	k = 0
	# 需要检测的字符串
	line_str = ""
	for i in range(len(line)):
		if line[i] >= '0' and line[i] <= '9':
			k += k * 10 + int(line[i])
		else:
			if line[i] != ' ':
				print("problem.")
			line_str = line[i + 1:]
			break
	# 第一次扫描字符串, 建立hash索引.
	hash_table = [0 for _ in range(128)]
	for i in range(len(line_str)):
		hash_table[ord(line_str[i])] += 1
	# 第二次扫描字符串, 搜索第k个仅出现一次的字符.
	count = 0
	for i in range(len(line_str)):
		if hash_table[ord(line_str[i])] == 1:
			count += 1
		if count == k:
			print('[' + line_str[i] + ']')
			break
	if count < k:
		print('Myon~')


发表于 2019-08-09 16:05:04 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 哔哩哔哩 测试工程师 PHP工程师 查找 模拟 2019 Java工程师
来自：哔哩哔哩 2019秋招...
上传者：小小
难度：
3条回答 11689浏览

热门推荐

通过挑战的用户

查看代码

相关试题

脸滚键盘

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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