2017百度、腾讯春招笔试

在经历惨烈的春招后,还是回头看看,好好总结总结。还是需要多练习、多见识,锻炼自己的编程思想,这样在临场时思路更清晰、编码更稳健、排错更及时。

需要申明的是,下面都是自己的解题思路或者查询到的解题方法,不见得是最优解法,欢迎交流,指错扔砖。

腾讯

1、构造回文

题目描述:给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?输出需要删除的字符个数。

输入例子:

abcda

google

输出例子:

2

2

第一时间想到的是递归遍历出这个最长回文串,但是提交发现运行超时,输出描述上写着1<=s.length<=1000 ,看来确实很大。

后来看讨论中给出一个思路:将求最长回文串问题转化为,求原字符串和其反串(即原字符串逆转)的最长公共子序列(不是子串,可不连续但是顺序一致)的长度,通过动态规划法即可简洁的写出。详尽的关于求最长公共子序列的动态规划算法可参考 万仓一黍 http://www.cnblogs.com/grenet/archive/2010/06/03/1750454.html

2、字符移位

题目描述: 小Q最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。你能帮帮小Q吗?

输入例子:

AkleBiCeilD

输出例子:

kleieilABCD

题目中的不能申请额外空间一开始让我很迷惑,原来是指空间复杂度为O(1) 常数级而不是不能定义变量之类的。

但是后来在java 实现中会发现:标准输入中只能等到String 对象,但是显然String 对字符操作不方便(当然你要是转空子直接遍历 、CharAt()判断、输出也能得到想要的输出),在String 类的一些操作类中char [] 的一些方法 如:replace()、replaceAll() ,看似很简洁其实你查看java源码会发现其中使用了很多StringBuffer、StringBuilder,不符合空间复杂度。

所以建议用C、C++来编写,核心代码:

3、有趣的数字

题目描述::有n个数,两两组成二元组,差最小的有多少对呢?差最大呢?

输入描述:输入包含多组测试数据,对于每组测试数据:N – 本组测试数据有n个数,a1,a2…an – 需要计算的数据,1<=N<=100000,0<=ai<=INT_MAX.

输出描述:对每组,输出两个数,第一个数表示差最小的对数,第二个数表示差最大的对数。

输入例子:

6
45 12 45 32 5 6

输出例子:

1  2

其中也没有什么特殊算法,咋一看感觉只需要n^2,不过时间复杂度太大。

百度

1、回家

题目描述:一个数轴上共有N个点,第一个点的坐标是度度熊现在位置,第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。

但是除了0号坐标和N-1号坐标,他可以在其余的N-2个坐标中选出一个点,并直接将这个点忽略掉,问度度熊回家至少走多少距离?

输入例子:

4

1 4 -1 3

输出例子:

4

求解是先找出那个需要直接忽略掉的坐标点,而判断一个点是不是最值得忽略,判断去除这个点后能让要走的距离减少最多。这样题目就很清晰了

2、不等式数列

题目描述:对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>’ 和 ‘<‘ )使其成为一个合法的不等式数列。但是现在手中只有k个小于符号即(‘<”)和n-k-1个大于符号(即’>’),想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

如n=3、k=1,则有3>1<2、2>1<3、1<3>2,1<3>2,满足条件的有4种

输入描述:

包含两个整数n和k(k < n ≤ 1000)

输出描述:

满足条件的排列数,对2017取模

解题思路:

用dp[i][j]表示有 i 个数字及 j 个小于号所能组成的数量(大于号数量当然是i – j – 1 个)

归纳:在dp[i][j]的前提下,加入第 i+1 个数字即 i+1,分为四种情况

  1. 如果将i+1插入当前序列的开头,即有了1<2(或2>1),加入后成为3>1<2,会发现等于同时加入了一个大于号!(此时可以无视1与2内部的关系,因为 i+1>i )
  2. 如果将i+1插入当前序列末尾,即1<2(或2>1)变成了 1<2<3,会发现等于同时加入了一个小于号! (此时可以无视1与2之间的关系,因为i+1>i)
  3. 如果将i+1加入一个小于号之间,即已经有 1<2了,向中间加入3,会发现变成了1<3>2,等于同时加入了一个大于号!
  4. 如果将i+1加入一个大于号中间,即有了2>1,变成了2<3>1,等于同时加入了一个小于号!

则可知dp[i][j]的值等于上述值的和:

  1. dp[i-1][j]—-只加了一个大于号及 i
  2. dp[i – 1][j – 1] —-只加了一个小于号及 i
  3. dp[i – 1][j] * j  —-在其中的每个小于号之间,加入 i 和大于号
  4. dp[i – 1][j – 1] * (i- j – 1) —-在其中的每个大于号之间,加入 i 和小于号

可得 dp[i][j] = (dp[i – 1][j – 1] * (i – j) + dp[i – 1][j] * (j + 1)) 再对2017取模

之后问题便迎刃而解。

 

发表评论

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

*