epic online test 机经

一共有四个部分：数学，逻辑（限时两分钟），学习新语言，编程。除了逻辑，其他都不限时。但是时间跟最后 得分相关。
4道编程题分别是：
1. 去除字符串中的重复字符。
2. 一个图片，找最小分割数。（一维DP）
3. word search in a char matrix.
4. 有效电话号码（DFS）

xd1313113 发表于 2014-9-4 14:56
楼主能把第二题 和第四题 详细解释一下吗？不是太懂题目是做啥

好的。

第二题： 一个page大小是1000*1000，1表示白色的点，0表示黑色的点。
输入：图片（N*1000, 1000）
输出：分割图片成page的最小次数。
要求：在全都是1的一行分割；如果1000行以内找不到符合这种要求的行，即强行在1001行分割。

第四题：
输入：电话号码位数（N），电话号码中不能包含的三个数（num1,num2,num3)
输出：所有符合要求的电话号码
要求：1.不能包含输入中的三个数  2. 不能有连续的数，如122。。。3.如果出现数字4，则4必须在第一位。

感谢楼主
但是第二题还是没看懂题的意思。
请问是只能横着 分页 每次都是一行1才能分出一页么？  
然后的问题是怎么定义最少次数呢
如果只是找全是1的分割 那也求不出最少次数 因为是一定的呀 用不到dp呀 难道题目的意思是 有可能 两条全是1的分割线之间有可能超过1000行 然后这之间的部分 就可以分作2页或者更多
希望 lz补充一下 谢谢

jackjiang2 发表于 2014-10-3 01:09
感谢楼主
但是第二题还是没看懂题的意思。
请问是只能横着 分页 每次都是一行1才能分出一页么？  

可能我理解错了。。。 所以挂了。。。
题目意思是是一行全是1才能割，如果1000行都没有全部是1的一行，强行隔。求最小分割数。

我个人感觉最大/最小数问题一般都是DP。所以是按DP做的。

赞，想问下第二题，最小割的，能说详细一点你是怎么一维DP做的么？

siren01 发表于 2014-9-4 06:10
赞，想问下第二题，最小割的，能说详细一点你是怎么一维DP做的么？

dp[i] donates the min break from row 0 to row i, then iterate from row 0 to row N.

哈哈楼主的题目感觉比我难啊。。
我是
1. 去除字符串中的重复字符。
2. find well ordered SubStiring
3. additive sequence
4. 有效电话号码（DFS）

补充内容 (2014-9-4 12:58):
写错了， 我第四个是特别常见的keyPad题

lzd1127 发表于 2014-9-4 12:55
哈哈楼主的题目感觉比我难啊。。
.. 我是
1. 去除字符串中的重复字符。

你这。。。全部来自career cup啊。。  你是哪天做的题啊？

22691482 发表于 2014-9-4 12:58
你这。。。全部来自career cup啊。。  你是哪天做的题啊？

这周一。。。。。反正好简单

22691482 发表于 2014-9-4 12:58
你这。。。全部来自career cup啊。。  你是哪天做的题啊？

你的我也就第二个没见过。。

22691482 发表于 2014-9-4 12:58
你这。。。全部来自career cup啊。。  你是哪天做的题啊？

看错了，我的第一题和你不一样。。 我的是把string出现最多的char和出现最少的char换一换位置。。不过也是特别简单的

lzd1127 发表于 2014-9-4 13:02
看错了，我的第一题和你不一样。。 我的是把string出现最多的char和出现最少的char换一换位置。。不过也 ...

你的电话面试完了吗？ 我明天电话面试。

楼主能把第二题 和第四题 详细解释一下吗？不是太懂题目是做啥