爱奇艺2018秋季校招测试工程师（第二场）
时长:120分钟 总分:100分
114浏览 1人已完成答题
题型介绍
| 题型 | 单选题 | 填空题 |
|---|---|---|
| 数量 | 10 | 3 |
6.
有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该...
有一个算法的递推关系式为：T(n) = 9 T(n / 3) + n，则该算法的时间复杂度为（）(^符号是幂的意思)
11.
排序
牛牛有一个长度为n的整数序列,牛牛想对这个序列进行重排为一个非严格升序序列。牛牛比较懒惰,他想移动尽量少的数就完成重排,请你帮他计算一下他最少需要移动多少个序列中的元素。(当一个元素不在它原来所在的位置,这个元素就是被移动了的)
输入描述：
输入包括两行,第一行一个整数n(1 &le n &le 50),即序列的长度
第二行n个整数x[i](1 &le x[i] &le 100),即序列中的每个数输入样例：
3
3 2 1 输出描述：
输出一个整数,即最少需要移动的元素个数输出样例
2
12.
判断题
牛牛参加了一场考试,考试包括n道判断题,每做对一道题获得1分,牛牛考试前完全没有准备,所以考试只能看缘分了,牛牛在考试中一共猜测了t道题目的答案是"正确",其他的牛牛猜为"错误"。考试结束后牛牛知道实际上n道题中有a个题目的答案应该是"正确",但是牛牛不知道具体是哪些题目,牛牛希望你能帮助他计算可能获得的最高的考试分数是多少。
输入描述：
输入包括一行,一行中有三个正整数n, t, a(1 &le n, t, a &le 50), 以空格分割输入样例：
3 1 2 输出描述：
输出一个整数,表示牛牛可能获得的最高分是多少。输出样例
2
13.
字符串价值
有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 * 4 + 2 * 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。 输入描述： 输入包括两行,第一行一个字符串s,字符串s的长度length(1 &le length &le 50),其中只包含小写字母('a'-'z')。 第二行包含一个整数k(0 &le k &le length),即允许移除的字符个数。输入样例： aba 1 输出描述： 输出一个整数,表示得到的最小价值输出样例 2
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 * 4 + 2 * 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。 输入描述： 输入包括两行,第一行一个字符串s,字符串s的长度length(1 &le length &le 50),其中只包含小写字母('a'-'z')。 第二行包含一个整数k(0 &le k &le length),即允许移除的字符个数。输入样例： aba 1 输出描述： 输出一个整数,表示得到的最小价值输出样例 2
