腾讯算法真题第八期：这些题你都能答出来吗？

每天整理十道历年腾讯算法工程师笔试真题，希望对大家有所帮助，欢迎大家在评论下方提出宝贵的建议～

题目1：某公司最近来了一个新员工 Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事 Cat 对 Fish 写的内容颇感兴趣，有一天他向 Fish 借来翻看，但却读不懂它的意思。例如“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是 “I am a student.”。Cat 对一一的翻转这些单词顺序可不在行，你能帮助他么？

观察字符串变化规律，你会发现这道题很简单。只需要对每个单词做翻转，然后再整体做翻转就得到了正确的结果。

题目2：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

首先我们考虑最简单的情况。如果只有 1 级台阶，那么显然只一种跳法。如果有 2 级台阶，那就有两种跳法：一种是分两次跳，每次跳 1 级；另一种是一次跳 2 级。

接着，我们来讨论一般情况。我们把 n 级台阶时的跳法看成是 n 的函数，记为 f (n)。当 n>2 时，第一次跳的时候就有两种不同的选择：一是第一次只跳 1 级，此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目，即为 f (n-1)；另外一种选择是跳一次跳 2 级，此时跳法数目等于后面剩下的 n-2 级台阶的跳法数目，即为 f (n-2)。因此 n 级台阶的不同跳法的总数 f (n)=f (n-1)+f (n-2)。分析到这里，我们不难看出这实际上就是斐波那契数列了。

题目3：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级…… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

当 n=1 时，结果为 1；

当 n=2 时，结果为 2；

当 n=3 时，结果为 4；

以此类推，我们使用数学归纳法不难发现，跳法 f (n)=2^(n-1)。

C++

Python2.7

题目4：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2

输出: 1->2

示例 2:

输入: 1->1->2->3->3

输出: 1->2->3

这道题让我们移除给定有序链表的重复项，那么可以遍历这个链表，每个结点和其后面的结点比较，如果结点值相同了，只要将前面结点的 next 指针跳过紧挨着的相同值的结点，指向后面一个结点。这样遍历下来，所有重复的结点都会被跳过，留下的链表就是没有重复项的了。

题目5：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

与上面那道不同的地方是这里要删掉所有的重复项，由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的 next 指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。