20200917算法培训

一、KMP

实现KMP算法,并求next[]与nextval[]

输入描述:输入一行字符串,其中只含字母
输出描述:见示例

示例1:
输入:
ababaaababaa
输出:

a[i]ababaaababaa
next[i]011234223456
nextval[i]010104210104

二、统计单词数

来源:牛客网

一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。
现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章
中的某一独立单词在不区分大小写的情况下完全相同(参见样例1 ),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2 )

输入描述:
共 2 行。
第 1 行为一个字符串,其中只含字母,表示给定单词;
第 2 行为一个字符串,其中只可能包含字母和空格,表示给定的文章
输出描述:
一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从 0 开始);如果单词在文章中没有出现,则直接输出一个整数 -1。

示例1:
输入:
To
to be or not to be is a question
输出:
2 0
说明:
输出结果表示给定的单词 To 在文章中出现两次,第一次出现的位置为0。

示例2:
输入:
to
Did the Ottoman Empire lose its power at that time
输出:
-1

三、回文数

来源:牛客网

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个10进制数56,将56加65(即把56从右向左读),得到121是一个回文数。
又如:对于10进制数87:
STEP1:87+78 = 165
STEP2:165+561 = 726
STEP3:726+627 = 1353
STEP4:1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。
写一个程序,给定一个N(2<=N<=10,N=16)进制数M,求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”

输入描述:
两行,分别为N,M
输出描述:
STEP=ans

示例1:
输入:
9
87
输出:
STEP=6

四、出现次数最多的数

http://118.190.20.162/view.page?gpid=T5
给定n个正整数,找出它们中出现次数最多的数。如果这样的数有多个,请输出其中最小的一个。

输入描述:
输入的第一行只有一个正整数n(1 ≤ n ≤ 1000),表示数字的个数。
输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
输出描述:
输出这n个次数中出现次数最多的数。如果这样的数有多个,输出其中最小的一个。

示例1:
输入:
6
10 1 10 20 30 20
输出:
10

五、有趣的数

http://118.190.20.162/view.page?gpid=T2
我们把一个数称为有趣的,当且仅当:

  1. 它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。
  2. 所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。
  3. 最高位数字不为0。
    因此,符合我们定义的最小的有趣的数是2013。除此以外,4位的有趣的数还有两个:2031和2301。
    请计算恰好有n位的有趣的数的个数。由于答案可能非常大,只需要输出答案除以1000000007的余数。

输入描述:
输入只有一行,包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出描述:
输出只有一行,包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

示例1:
输入:
4
输出:
3

六、质数因子

输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 )

输入描述:
输入一个long型整数
输出描述:
按照从小到大的顺序输出它的所有质数的因子,以空格隔开。最后一个数后面也要有空格。

示例1:
输入:
180
输出:
2 2 3 3 5

七、递归实现组合型枚举

来源:牛客网

从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。

输入描述:
两个整数n,m。
输出描述:
按照从小到大的顺序输出所有方案,每行1个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 9 12排在1 3 10 11前面)。

示例1:
输入:
5 3
输出:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

《20200917算法培训》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注