一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 981|回复: 4
收起左侧

[编程题] Epic OA 上的一道题~~【snake sequences】

[复制链接] |试试Instant~ |关注本帖
sherry900105 发表于 2014-12-14 23:46:07 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Question:

You are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or the number below it is +1 or -1 its value. For example,

1 3 2 6 8
-9 7 1 -1 2
1 5 0 1 9

In this grid, (3, 2, 1, 0, 1) is a snake sequence.

Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).

这是Careercup上的一道Epic OA的Code题,小女子看了好久,包括自己研究和看Careercup上别人po的答案。
但是我发现大多数答案都是最后只return了最大snake sequences的长度但是并没有给出这个蛇形序列是啥。。可是我觉得题里是要求把蛇形序列也print出来。。请问地里有没有人做过这道题或者能给出一个比较全面的答案啊?

在此跪谢了~~~

评分

1

查看全部评分

Adeath 发表于 2014-12-15 01:54:28 | 显示全部楼层
先用DP求出终止于每个格子的最大长度,然后在最大长度的格子做DFS,输出序列
回复 支持 1 反对 0

使用道具 举报

 楼主| sherry900105 发表于 2014-12-15 02:51:48 | 显示全部楼层
Adeath 发表于 2014-12-15 01:54
先用DP求出终止于每个格子的最大长度,然后在最大长度的格子做DFS,输出序列

那就是得差不多两次遍历这个格子了哦。。虽然第二次不是完全遍历。。有没有一次遍历就能得到长度和得到蛇形序列的方法啊。。= =
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-15 03:11:19 | 显示全部楼层
本帖最后由 Adeath 于 2014-12-15 03:16 编辑
sherry900105 发表于 2014-12-15 02:51
那就是得差不多两次遍历这个格子了哦。。虽然第二次不是完全遍历。。有没有一次遍历就能得到长度和得到蛇 ...

直接每个格子做DFS或者DP计算长度的同时cache序列
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-15 03:24:26 | 显示全部楼层
而且有必要提一下  遍历几遍没有太大关系  关键你做的操作是什么  比如
  1. for(i=0;i<100;i++){
  2. a++;
  3. }
  4. for(i=0;i<100;i++){
  5. a++;
  6. }
复制代码
  1. for(i=0;i<100;i++){
  2. a++;
  3. a++;
  4. a++;
  5. a++;
  6. a++;
  7. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 18:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表