掌握数据结构和算法，蓝翔北大都不怕- 大数跨境

首页

掌握数据结构和算法，蓝翔北大都不怕

秘塔科技

2018-07-27

导读：这是一篇由HR小姐姐操刀的题解

夏至已至，招聘程序员，绝大部分公司的技术面都会有代码能力测试。招聘季不少公司甚至会进行在线编程测试，统一做题，自动评分，然后直接带走排名靠前的程序员，简单又粗暴，实用又高效。

这些题目的考点包括搜索、排序、动规、贪心……都是我们在数据结构与算法的课上打过交道的东东。然而，当这些知识点隐藏在题目里面的时候，你能够发现吗？

今天胖涵涵带大家看一套2018年北大的保研英语考试题，再次预习复习一下这些知识点。

此处插播一条广告：秘塔科技招人啦！

发送图片简历到公众号后台便有机会收获面试邀请。

A题：计算两个日期之间的天数

样例输入： 2008 1 1 2009 1 1 样例输出： 366

这是一道大一上的常规练习题，俗称签到题。本题没有算法上的考点，只是写起来较为琐碎。

解题分三步走：

先看两个日期之间相差的完整的年份，加365或366。
再看相差的完整的月份，加28或29或30或31。
再看剩下的不完整的月份，加上余下的天数。

闰年的问题随时都要考虑，题目已经提示我们闰年的计算方法：

 
 
 
  
  
  if 能被100整除:
  
  
      if 能被400整除:
  
  
          return 闰年
  
  
  else:
  
  
      if 能被4整除:
  
  
          return 闰年

B题：回文子串

给定一个字符串，寻找并输出字符串中最长回文子串。回文串即从左到右和从右到左读都一样的字符串。如果字符串中包含多个回文子串，则返回第一个。
  
  
  
   
   
   样例输入：

   
   
   ab

   
   
   babadec

   
   
   scdedcd

   
   
   样例输出：

   
   
   a

   
   
   bab

   
   
   cdedc

  
  
  

假设字符串长度为 n，则共有个子串，再判断每个子串是否是回文子串，复杂度为。

这里提供一个更高效的动态规划的解法：

令 F[i,j]表示从 i 位置开始长度为 j 的子串是否为回文串：如果是， F=1；如果不是， F=0。

递推式：

 
 
 
  
  
  
  
  
  F[i,1] = 1
  
  
  F[i,2] = (str[i] == str[i+1])
  
  
  F[i,j] = (F[i+1,j-2] and str[i] == str[i+j])

最后在 F[i,j]中找到符合题意的解。

动规算法复杂度为。本题写起来较为简单。

C题：投骰子

（题目很长，顺便考了英语。简化版题目如下。）给一个包含几个骰子的图像，确定骰子上的点数，按升序输出。假设图像仅包含三种不同的像素：背景，骰子，骰子上的点。定义：

共边的像素是相连的，即对角的像素不算相连

仅由非背景像素组成的所有最大连通像素集是一个骰子，由骰子上的点像素组成的最大连通像素集是骰子上的一个点

 
 
 
  
  
  样例输入：
  
  
  ..............................
  
  
  ..............................
  
  
  ...............*..............
  
  
  ...*****......****............
  
  
  ...*X***.....**X***...........
  
  
  ...*****....***X**............
  
  
  ...***X*.....****.............
  
  
  ...*****.......*..............
  
  
  ..............................
  
  
  ........***........******.....
  
  
  .......**X****.....*X**X*.....
  
  
  ......*******......******.....
  
  
  .....****X**.......*X**X*.....
  
  
  ........***........******.....
  
  
  ..............................
  
  
  （看出来了吗？上图共有4个骰子，左上是2点，

  
  
  右上是1点，左下是2点，右下是4点。）
  
  
  样例输出：1 2 2 4

这是一道广度优先搜索的题目，推荐用队列实现。有些同学在面试的时候会给出深度优先的方案，然而一旦数据量变大，递归那么多层会内存溢出（俗称爆栈）。

好了我们已经知道了广搜，然而本题实现起来还是很麻烦。

第一步，计算有几个骰子。遍历像素点，遇到第一个非背景像素，标记为1号骰子，开始广搜和它相连通的非背景像素，全部标记为1。继续遍历像素点，遇到第二个未被标记的非背景像素，标记为2号骰子，开始广搜……
第二步，计算有几个骰子上的点。遍历像素点，遇到第一个骰子上的点的像素，做好已访问标记，开始广搜。检查和骰子上的点相连通的骰子号码，对应号码的骰子点数+1。继续遍历。
排序，输出。

D题：欧元效率

给定一系列硬币的面额，计算交易特定金额所需的硬币数量。我们认为每次交易使用的硬币数量越少越有效率。举个例子，当硬币面额为1 2 5 10 20 50的时候，交易68元需要的硬币数量为3，即20+50-2=68。每组给出6个面额，最小面额都是1，最大面额不超过100。输出交易金额1到100所需硬币数量的平均值和最大值。

 
 
 
  
  
  样例输入：
  
  
  1 2 5 10 20 50
  
  
  1 24 34 39 46 50
  
  
  1 2 3 7 19 72
  
  
  样例输出：
  
  
  2.96 5
  
  
  2.52 3
  
  
  2.80 4
  
  
  可以看出，当面额组合为1 24 34 39 46 50的时候，

  
  
  每次交易最多使用3枚硬币，不考虑计算上的麻烦，

  
  
  买东西还是很方便的。

本题是一道隐藏的背包问题。直观的看，把硬币当做物品，面额当做物品的价值，每个物品可以拿0个，1个，甚至-1个。物品可以取负数个，处理起来非常棘手，我们需要把问题进行适当的转化。

转化过程：用表示总金额为 X 所需的最少硬币数量，表示交易金额为 X 所需的最少硬币数量。令。其中 V 表示交易金额，A 表示买家付的总金额，B 表示卖家找回的总金额。则。

求 X 的过程是一个标准的背包问题：考虑面额为的硬币，尝试用去替换小面额硬币：。

求出 F 后，再求 G，整体复杂度为。

下面讨论的定义域，即买家最多付给卖家多少钱。简单估算最多付100张，最大面额99，最大上限为9900。这样已经可以顺利AC这道题了，有兴趣的同学可以尝试继续计算更小的上限。

E题：重要逆序对

给定N个数的序列，定义一个数对为“重要逆序对”的充要条件为且。求给定序列中“重要逆序对”的个数。
  
  
  
   
   
   样例输入
   
   
   10

   
   
   0
 9 8 7 6 5 4 3 2 1
   
   
   样例输出

   
   
   16

  
  
  

求逆序对最经典的方法的是借助归并排序。

在归并两个有序序列，之前，我们观察到，若>，则均大于且与形成逆序对的关系，在本次归并过程中，这个数中与形成逆序关系的一共有个。归并以后，这个数组成的序列内不再有逆序对。

本题求重要逆序对，把上述>的判断条件换成 $>$ 即可。

归并排序的复杂度为，归并前计算逆序对的复杂度为是线性的，则本题的复杂度也为。

F题：电车

每个路口有一些出口通往其他的路口，出口处有一个方向转换器。如果方向转换器指向的方向不是电车想去的方向，则需要司机手动转动方向转换器，反之则不需要。给出一张地图、起始路口A和目标路口B，计算从A到B最少要转动方向转换器的次数。

本题是一道最短路径的题目。

路口就是图的结点，如果路口A通往路口B，则添加一条由A结点到B结点的有向边。如果方向转换器初始指向B，则这条边的权重为0，否则权重为1。

有向图建好了以后直接使用Dijkstra算法就可以啦。

G题：食物链

已知有三类动物A,B,C，这三类动物的食物链构成了环形。A吃B， B吃C，C吃A。有两种说法对动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。某人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。根据给定的N和K句话，输出假话的总数。

本题是并查集的经典练习题。建模方面有一点难度。

在同一集合中的结点表示相互之间可以推导出食物链关系。我们给边Father[a] = b做标记：