W公司2016春招笔试
难度:★★★★
不得不说某公司真低调,这样就不说是什么公司了。笔试的形式很简单,两道题,在 3 天内完成其中的一道。于是也就分享其中一道吧……
第一道题:最大价值链
这道题使我想起了以前在 POJ 里做过的一道题。给定一个迷宫(矩阵),负值代表墙,从右下角开始,累加走过的路(不可回头),直到走到最右边(或者右上角)。并且,这个题还有一个『传送』功能,当向下穿越到上面的时候,当前结果清零,以下一步的方案计算收益。
这道题一看就是动态规划的思想,但是怎么个动态规划法,还是值得商量的。一开始开错题。由于不可以向左走,所以往右走就是自由的。但是如果往上走或者往下走,下一步就不能是上一个动作的相反方向了。
既然是动态规划,那么我们就考虑一下状态方程吧…… 设当前坐标为 $(x, y)$ 、方向为 $d$。那么递推方程就是:
$$ F(x,y,d)= \begin{cases}
M_{(x,y)}+\max\{ F(i+1,j,0), F(i, j-1,1), F(i,j+1,2) \}, & d=0 \\
M_{(x,y)}+\max\{ F(i+1,j,0), F(i,j-1,1) \}, & d=1 \\
M_{(x,y)}\max\{ F(i+1,j,0), F(i,j+1,2) \}, & d=2
\end{cases} $$
并且,
$$ d = \begin{cases} 0, \text{from right} \\ 1, \text{from up} \\ 2, \text{from down} \end{cases} $$
好像有什么不对——还没有考虑边界的情况(穿越),如果考虑穿越,而且不能走重复的路,那么情况就复杂很多了。
那么我们再定义三个执行条件:
- 如果没有路了,即遇到的方块 $M_{(x,y)}=-1$ :
- 如果在边界,返回 0 ;
- 如果不在边界,返回 -1 (死胡同);
- 否则,
- 如果不在边界,尝试向上、下、右的顺序,按照上述状态方程找路;
- 如果当前是边界,并且上一步没找到路线,则设置此刻最大的价值是自身;
- 如果在边界,尝试穿越,并与上一步获得的值对比,取最大值。
写了近一晚才勉强跑出来,Java 和 C++ 的非多值返回算法,使得这份代码传递了很多『输出参数』,调试很不容易……做完都不知道有没有漏掉情况。
小结 总的来说,这次笔试题很考算法的基础知识、对细节的捕捉和缜密的逻辑,这道题初看就是 Medium 类型的,但是实际上难度系数还是很高的。
【W公司2016春招笔试】再感叹一下,这家公司真的很低调。
推荐阅读
- 游戏IP(立足于玩家情感的粉丝经济)
- 社保代缴公司服务费包含哪些
- 员工的微信朋友圈是公司的宣传阵地吗()
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- 2019-2-26
- 2018年6月30日
- 人至不惑之年
- 暴君公司|暴君公司 第十八章 做会员吗
- 2019.3.29
- 恩|恩 有点喜欢你