[互联网面试笔试汇总C/C++-5] 网易有道-3

第一题：一个长度为n的数组A，里面的元素只能是0或者1，另一个长度为n的数组B，B[i] = a[i-1]+a[i]+a[i+1]，B[0] = A[0]+A[1]，B[n-1] = A[n-2]+A[n-1]，给定B，求A。

分析：请看下面推倒公式：

B[i] = A[i-1] + A[i] + A[i+1];

B[i+1] = A[i] + A[i+1] + A[i+2];

B[i+1] - B[i] = A[i+2] - A[i-1];

A[i+2] = B[i+1]-B[i] + A[i-1];

其中B是已知的，所以有如下关系：

A[i+2] = c + A[i-1];c是常数。

也就是

A[i] = c + A[i-3];c是常数。

所以相当于我们主要能确定A[0],A[1],A[2]就可以求出所有的A[i]了。

下面分析一下数组B，考虑到A中的元素只能是0或者1这个条件，我们分下面几种情况来讨论。

1.B[0] = 0,那么必然A[0] = A[1] = 0,而A[2] = B[1] - B[0];也就是A[0],A[1],A[2]都知道了。

2.B[0] = 2,那么必然A[0] = A[1] = 1,而A[2] = B[1] - B[0];也就是A[0],A[1],A[2]都知道了。

3.B[0] = 1,那么有两种可能：

第一种：A[0] = 1,A[1] = 0,A[2] = B[1] - B[0];

第二种：A[0] = 0,A[1] = 1,A[2] = B[1] - B[0];

我们先假设第一种，可以根据上面的递推式求出A[3]---A[n-1],但是到这里的时候我们只用到了B[0]---B[n-2],还有最后一个B[n-1]没有用到，刚好可以用这个B[n-1] = A[n-2]+A[n-1]来检验一下我们的假设，如果正确，则ok；若不正确，则根据另一种假设来计算A。

体会：

刚开始没有用到A中每一个元素都只能是0和1这个条件，后来想到了才知道从B[0]开始下手，从而可见面试的时候看一下哪个条件还没用到对开拓自己的思路很有效果。最后B[n-1]的使用也是相同的道理。

第二题：三个字符串a,b,c，其中c由a和b里面的字符组成，要求c里面a和b中的字符要保持原相对位置不变。给定a,b,c，判断c是否符合条件，注意，ab里面可能有重复字符。
例子：a = "abc",b = "def",c = "abdecf"，满足。
a = "abc",b = "def",c ="acbdef"，不满足。

分析：

这个题目相对比较简单，可以用动态规划来解决。

假设a长度为m，b长度为n，则c长度为m+n，我们用dp(k,r,k-r)来表示c的前k个字符能否用a的前r个和b的前k-r个字符组成，返回值为boolean，其中r < k。

所以我们可以得到下面的关系：

1.当a[r] = c[k]且b[k-r] != c[k]时，dp(k,r,k-r) =dp(k-1,r-1,k-r);

2.当a[r] != c[k]且b[k-r] = c[k]时，dp(k,r,k-r) =dp(k-1,r,k-r-1);

3.当a[r] = c[k]且b[k-r] = c[k]时，dp(k,r,k-r) = dp(k-1,r-1,k-r) || dp(k-1,r,k-r-1);

4.当a[r] != c[k]且b[k-r] != c[k]时，dp(k,r,k-r) = false；

dp(m+n,m,n)就是最终的结果。

当然写代码的时候要注意优化代码。

第三题：linux下软连接和硬链接的区别。

答案博主正在整理，会尽快更新出来的~