DP

有些笔试题的存在意义就是搞笑么?

昨天有个以前一起玩 ACM 的队友跟我说个题, 说是前几天腾讯实习生招聘的笔试题之一, 原文如下

已知a[0],a[1]…a[n-1]
现在要构造b[0],b[1]…b[n-1]
其中 b[i]=a[0]*a[1]*….a[n-1]/a[i]
要求,不能用除法,不能使用其他任何存储变量,除了循环变量i,j之类的
要求O(1)的空间复杂度,O(n)的时间复杂度

关键是不能用除法

看到这题后的第一反应是这特么不会爆类型么? double 也经不起这么搞吧. 然后就冷静下来想怎么解决, 不能用除法就避开那个除法操作咯, 把 b[i] 的推导公式换成 a[0]*…*a[i-1]*a[i+1]*…*a[n-1] 就是了, 一看就像个 DP. 推了下后写了这么个代码 (假设所有数都是 int 且不爆类型大小)

// 先构造一遍, 使得 b[i] = a[0]*...*a[i-1]
b[0] = 1;
for (int i = 1; i < n; ++i) {
  b[i] = b[i-1]*a[i-1];
}

// 逆序, 使得遍历到 b[i] 时, sum = a[i+1]*...*a[n-1]
//这时候 b[i]*sum = a[0]*...*a[n-1]/a[i]
int sum = 1;
for (int i = n-1; i >= 0; --i) {
  b[i] *= sum;
  sum *= a[i];
}

然后被提醒说 sum 这个变量也不能有, 好像原文中是说了不能用其他存储变量… 但是这不还是 O(1) 的空间复杂度么, 腾讯好像经常喜欢搞这种无聊的要求 (卡一两个变量), 于是当场就怒了

叶文/Snoopy阿排 20:41:49
那把他写到循环里好了… -.-|
叶文/Snoopy阿排 20:42:32
老实说, 这个题出的很烂…
叶文/Snoopy阿排 20:42:36
烂的无与伦比
** 20:43:05
哈哈
叶文/Snoopy阿排 20:43:15
首先, 这种奇技淫巧没有任何意义
其次, 连乘更大的问题是爆数据类型…
** 20:44:41
是啊
** 20:44:51
关键一点就是没有任何意义
叶文/Snoopy阿排 20:45:41
而且, 要真抠细节, 他没说不能修改 a 的值, 我在做逆序的时候把 sum 换成 a[] 就行了

果然改 a 数组的值就达到目的了? 好像是? 这样有意思么?

最后, 真心求既不使用多余变量, 且不修改 a 的值的做法.

A Problem for Others

Gardon asked me to produce a problem for his own contest a weed ago, which contest celebrate for his remove. I make the problem that can be solved by a dynamic programming, which is my favorite recently, and used half a hour to write the standard code and the program to generate data. But when I asked flymouse to check the data he said that I make the problem hard to understand, I explained a minutes then decide to give up, replaced to rewrite the problem by English, maybe English is more understandable.