May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2544|回复: 15
收起左侧

[找工就业] Epic OA 的snake sequence怎么解?

[复制链接] |试试Instant~ |关注本帖
基德不爱吃鱼 发表于 2015-3-30 01:46:29 | 显示全部楼层 |阅读模式

2015(1-3月)-[13]EE硕士+fresh grad 无实习/全职 - 网上海投| 码农类全职@Epicfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
     Snake Sequence
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 . visit 1point3acres.com for more.
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).



如果要打印出snake sequence如何打印?  假如有多条sequence的长度相同的话?
求大神们指点


. 1point 3acres 璁哄潧
补充内容 (2015-3-30 02:18):
补充一下  这道题是用DP做的
peace 发表于 2015-4-16 09:57:13 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这题我也是先dp得到以每个点为蛇尾所能达到的最长的长度,然后从最长长度那个点开始找snake,类似word search那种dfs
  1. import java.util.ArrayList;
  2. import java.util.Arrays;. from: 1point3acres.com/bbs
  3. . visit 1point3acres.com for more.
  4. public class SnakeSequence {
  5.         public static void main(String[] args) {. 鍥磋鎴戜滑@1point 3 acres
  6.                 int[][] grid = {
  7.                                 {1, 3, 2, 3, 4},
  8.                                 {1, 2, 1, 2, 3},. visit 1point3acres.com for more.
  9.                                 {1, 5, 0, 1, 9}
  10.                 };. 1point 3acres 璁哄潧
  11.                
  12.                 ArrayList<String> result = getLongestLength(grid);
  13.                 for (String s : result) {
  14.                         System.out.println(s);
  15.                 }. 1point3acres.com/bbs
  16.         }
  17.        
  18.         public static ArrayList<String> getLongestLength(int[][] grid) {
  19.                 int[][] lengthGrid = new int[grid.length][grid[0].length];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.                 for (int i = 0; i < grid.length; i++) {
  21.                         for (int j = 0; j < grid[0].length; j++) {
  22.                                 lengthGrid[i][j] = 1;
  23.                         }
  24.                 }
  25.                
  26.                 //initialize the first column
  27.                 for (int i = 1; i < grid.length; i++) {
  28.                         if (Math.abs(grid[i][0] - grid[i - 1][0]) == 1) {
  29.                                 lengthGrid[i][0] = lengthGrid[i - 1][0] + 1;
  30.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.                 }
  32.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.                 //initialize the first row
  34.                 for (int j = 1; j < grid[0].length; j++) {. 鍥磋鎴戜滑@1point 3 acres
  35.                         if (Math.abs(grid[0][j] - grid[0][j - 1]) == 1) {
  36.                                 lengthGrid[0][j] = lengthGrid[0][j - 1] + 1;
    . 鍥磋鎴戜滑@1point 3 acres
  37.                         }
  38.                 }
  39.                 . 1point3acres.com/bbs
  40.                 for (int i = 1; i < grid.length; i++) {
  41.                         for (int j = 1; j < grid[0].length; j++) {
  42.                                 if (Math.abs(grid[i][j] - grid[i][j - 1]) == 1) {
  43.                                         lengthGrid[i][j] = Math.max(lengthGrid[i][j - 1] + 1, lengthGrid[i][j]);
  44.                                 }
  45.                                 if (Math.abs(grid[i][j] - grid[i - 1][j]) == 1) {
  46.                                         lengthGrid[i][j] = Math.max(lengthGrid[i - 1][j] + 1, lengthGrid[i][j]);
  47.                                 }
  48.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  49.                 }
  50.                
  51.                 System.out.println(Arrays.deepToString(lengthGrid));
  52.                 int maxLength = 1;. 鍥磋鎴戜滑@1point 3 acres
  53.                 for (int i = 0; i < grid.length; i++) {
  54.                         for (int j = 0; j < grid[0].length; j++) {
  55.                                 if (maxLength < lengthGrid[i][j]) {
  56.                                         maxLength = lengthGrid[i][j];
  57.                                 }
  58.                         }
  59.                 }
  60.                 System.out.println("The max length is " + maxLength);
  61.                
  62.                 ArrayList<String> result = new ArrayList<>();
  63.                 //to find out the longest snake sequences
  64.                 for (int i = 0; i < grid.length; i++) {
  65.                         for (int j = 0; j < grid[0].length; j++) {
  66.                                 if (lengthGrid[i][j] == maxLength) {
  67.                                         StringBuilder sb = new StringBuilder();
  68.                                         sb.append(grid[i][j]);
  69.                                         findSnakeSequence(i, j, grid, maxLength, sb, result);
  70.                                 }-google 1point3acres
  71.                         }
  72.                 }
  73.                 return result;
  74.         }
  75.        
  76.         public static void findSnakeSequence(int i, int j, int[][] grid, int length, StringBuilder sb, ArrayList<String> result) {
  77.                 if (sb.length() == length) {
  78.                         result.add(sb.toString());
  79.                         return;
  80.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  81.                
  82.                 if (i - 1 >= 0 && Math.abs(grid[i][j] - grid[i - 1][j]) == 1) {. 1point3acres.com/bbs
  83.                         sb.insert(0, grid[i - 1][j]);
  84.                         findSnakeSequence(i - 1, j, grid, length, sb, result);
  85.                         sb.deleteCharAt(0);
  86.                 }. 1point3acres.com/bbs
  87.                
  88.                 if (j - 1 >= 0 && Math.abs(grid[i][j - 1] - grid[i][j]) == 1) {. From 1point 3acres bbs
  89.                         sb.insert(0, grid[i][j - 1]);
  90.                         findSnakeSequence(i, j - 1, grid, length, sb, result);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  91.                         sb.deleteCharAt(0);
  92.                 }
  93.         }
  94. }
复制代码
回复 支持 1 反对 0

使用道具 举报

mrno5zzz 发表于 2015-3-30 02:03:47 | 显示全部楼层
关注一亩三分地微博:
Warald
用一个List或者Set来存结果, 设置一个max的值代表length。如果走完某一条路发现length大于max,那清空List, 再把这条路加进去。然后继续就好了
回复 支持 反对

使用道具 举报

 楼主| 基德不爱吃鱼 发表于 2015-3-30 02:19:55 | 显示全部楼层
mrno5zzz 发表于 2015-3-30 02:03
用一个List或者Set来存结果, 设置一个max的值代表length。如果走完某一条路发现length大于max,那清空List ...

但是如果用DP做的话 我们一直找最优解  假如在某一点发现往右和往下都是最有(长度相同) 那么路径在这里就分叉了  一个list应该不够吧?
回复 支持 反对

使用道具 举报

mrno5zzz 发表于 2015-3-30 02:49:52 | 显示全部楼层
基德不爱吃鱼 发表于 2015-3-30 02:19
但是如果用DP做的话 我们一直找最优解  假如在某一点发现往右和往下都是最有(长度相同) 那么路径在这里 ...
. more info on 1point3acres.com
哦,我是用DFS 做的, 一个List<List<String>> 去存总结果, 一个List<String>去存当前路径, max更新的话就清空List<List<String>>. 你用DP是怎么做的?
回复 支持 反对

使用道具 举报

 楼主| 基德不爱吃鱼 发表于 2015-3-30 02:55:20 | 显示全部楼层
mrno5zzz 发表于 2015-3-30 02:49
哦,我是用DFS 做的, 一个List 去存总结果, 一个List去存当前路径, max更新的话就清空List. 你用DP是 ...

这方法挺好的!能不能share下你的代码
我用DP只能找longest sequence 输出他的length 但是不能打印 所以很纠结。。
回复 支持 反对

使用道具 举报

mrno5zzz 发表于 2015-3-30 03:05:15 | 显示全部楼层
你DP是从右下角往上弄得吧?其实可以做完DP从最大点做DFS, 不满足就返回。

这个是我DFS代码

import java.util.*;
public class snakeseq {
        public static List<String> snake(int[][] mat){
                List<String> res = new ArrayList<String>();
                int max=0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                int count=0;
                StringBuffer path = new StringBuffer(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                for(int ii=0;ii<mat.length;ii++){.1point3acres缃
                        for(int jj=0;jj<mat[0].length;jj++){
                                path.delete(0, path.length());
                                max=helper(mat, res,path,ii, jj,1,count,max);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                path.delete(0, path.length());
                                max=helper(mat,res,path,ii,jj,2,count, max);
                        }
                }
                return res;
        }
       
        public static int helper(int[][] mat, List<String> res, StringBuffer path, int r, int c, int type, int count, int max){
                int rows = mat.length;
                int cols = mat[0].length;
                path.append(mat[r][c]);
                path.append(',');
                if(r==rows-1&&type==1||c==cols-1&&type==2){
                        if(count==max){. more info on 1point3acres.com
                                path.deleteCharAt(path.length()-1);
                                res.add(path.toString());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }else if(count>max){
                                max=count;
                                res.clear();
                                path.deleteCharAt(path.length()-1);
                                res.add(path.toString());
                        }
                        return max;
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(type==1){
                        if(Math.abs(mat[r][c]-mat[r+1][c])!=1) return max;
                        else{
                                max=helper(mat, res, new StringBuffer(path), r+1, c, 1, count+1, max);
                                max=helper(mat, res, new StringBuffer(path), r+1, c, 2, count+1, max);
                        }.1point3acres缃
                }else if(type==2){
                        if(Math.abs(mat[r][c]-mat[r][c+1])!=1) return max;
                        else{
                                max=helper(mat, res, new StringBuffer(path), r, c+1, 1, count+1, max);
                                max=helper(mat, res, new StringBuffer(path), r, c+1, 2, count+1, max);
                        }
                }
                return max;
        }
       
        public static void main(String[] args){
                int[][] mat = new int[][]{{4,3,2,6,8},{-9,7,1,-1,2},{1,5,0,1,9}};. Waral 鍗氬鏈夋洿澶氭枃绔,
                List<String> res = snake(mat);
                Iterator it = res.iterator();
                while(it.hasNext()){. 1point 3acres 璁哄潧
                        System.out.println(it.next());
                }
                System.out.println(res.size());
        }
}
回复 支持 反对

使用道具 举报

 楼主| 基德不爱吃鱼 发表于 2015-3-30 03:20:22 | 显示全部楼层
mrno5zzz 发表于 2015-3-30 03:05. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你DP是从右下角往上弄得吧?其实可以做完DP从最大点做DFS, 不满足就返回。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个是我DFS代码

我是从左上往右下做的   就是不知道怎么打印多条。。。 先好好研究下你的代码!
回复 支持 反对

使用道具 举报

halfbloon 发表于 2015-3-30 07:32:39 | 显示全部楼层
这难道不是leetcode原题么
回复 支持 反对

使用道具 举报

 楼主| 基德不爱吃鱼 发表于 2015-3-30 09:45:47 | 显示全部楼层
halfbloon 发表于 2015-3-30 07:32. Waral 鍗氬鏈夋洿澶氭枃绔,
这难道不是leetcode原题么
. 1point 3acres 璁哄潧
啊? leetcode哪道题啊  求指点!
回复 支持 反对

使用道具 举报

halfbloon 发表于 2015-3-30 14:19:57 | 显示全部楼层
基德不爱吃鱼 发表于 2015-3-30 09:45. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
啊? leetcode哪道题啊  求指点!
. 1point3acres.com/bbs
哎呀 搞错了... 这道题应该就是DFS,我把代码发给你吧? 你把邮箱发我。
回复 支持 反对

使用道具 举报

 楼主| 基德不爱吃鱼 发表于 2015-3-30 14:34:52 | 显示全部楼层
halfbloon 发表于 2015-3-30 14:19. more info on 1point3acres.com
哎呀 搞错了... 这道题应该就是DFS,我把代码发给你吧? 你把邮箱发我。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给你发消息啦  多谢啦!! 感觉这道题有点复杂啊。。。。也因为我太水了。。
回复 支持 反对

使用道具 举报

悲伤网管 发表于 2015-4-17 12:41:34 | 显示全部楼层
peace 发表于 2015-4-16 09:57
这题我也是先dp得到以每个点为蛇尾所能达到的最长的长度,然后从最长长度那个点开始找snake,类似word sear ...

我也是这么做的,不知道还有没有更快的方法
回复 支持 反对

使用道具 举报

ldpraymond 发表于 2015-6-11 02:42:58 | 显示全部楼层
DFS应该是正解
回复 支持 反对

使用道具 举报

ldpraymond 发表于 2015-6-11 02:49:26 | 显示全部楼层
看过Berkeley 61B DFS部分,如果自己构建GraphNode,会不会更简洁一些?
回复 支持 反对

使用道具 举报

kanone 发表于 2015-11-19 13:48:39 | 显示全部楼层
如果从左上往右下遍历的话相当于隐性实现了Dynamic Programming,曾经栽在这道题上,如今十倍奉还!
. more info on 1point3acres.com
  1. """
  2. Analysis:

  3. must traverse all elements so that no one is missed,
  4. calculate paths ending with each element,. From 1point 3acres bbs
  5. store both maximum length and paths in two matrices.1point3acres缃
  6. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. """

  8. import copy

  9. Grid1 = [[1,3,2,6,8],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.         [-9,7,1,-1,2],
  11.         [1,5,0,1,9]]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.         
  13. Grid2 = [[1,3,2,6,8],
  14.         [-9,7,1,0,2],
  15.         [1,5,0,1,9]]
  16.         


  17. def getLongestSnakes(G):

  18.     row = len(G)
  19.     column = len(G[0])   
  20.    
  21.     #must use deepcopy !
  22.     lengths = [copy.deepcopy([0]*column) for i in range(row)] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.     paths = [copy.deepcopy([[]]*column) for i in range(row)]
  24.         
  25.     maxlength = 0
  26.    
  27.     #iterate through each element from left to right, top to bottom
  28.     for i in range(len(G)):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.         for j in range(len(G[0])):
  30.             getSnakes(G, (i,j), paths, lengths)
  31.             if lengths[i][j] > maxlength:
  32.                 maxlength = lengths[i][j]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.     for i in range(len(G)):
  34.         for j in range(len(G[0])):
  35.             if lengths[i][j] == maxlength:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                 print(paths[i][j]). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  37.                 .1point3acres缃
  38.                 for p in paths[i][j]:
  39.                     l = []
  40.                     for e in p:
  41.                         l += [G[e[0]][e[1]]]
  42.                     print(l)
  43.    
  44.     print("Length Grid:")
  45.     print(lengths).鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.     #print("Path Grid:")
  47.     #print(paths)-google 1point3acres

  48. . from: 1point3acres.com/bbs
  49. #get paths of snakes ending with element "end",
  50. #which is a tuple consists of row number and column number
  51. #this function could be used seperately, which means you can use
  52. #it to calculate any snakes ends with this element "end", and it
  53. #has dynamic programming feature, before doing that you need to initiate P and L
  54. def getSnakes(G, end, P, L):
  55.     x, y = end
  56.     鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  57.     #if already calculated, return previous result
  58.     if L[x][y] != 0:
  59.         return copy.deepcopy(P[x][y])
  60.    
  61.     result = []   
  62.    
  63.     if x-1 >= 0 and abs(G[x-1][y] - G[x][y]) == 1:
  64.         pathList = getSnakes(G, (x-1, y), P, L)
  65.         
  66.         if L[x][y] <= L[x-1][y] + 1:
  67.             L[x][y] = L[x-1][y] + 1
  68.             
  69.             for p in pathList:
  70.                 p += [(x,y)]
  71.         
  72.             result += pathList
  73.             
  74.     if y-1 >= 0 and abs(G[x][y-1] - G[x][y]) == 1:
  75.         pathList = getSnakes(G, (x, y-1), P, L)
  76.         if L[x][y] <= L[x][y-1] + 1:
  77.             L[x][y] = L[x][y-1] + 1
  78.             
  79.             for p in pathList:
  80.                 p += [(x,y)]
  81.         
  82.             result += pathList
  83.     if len(result) == 0:
  84.         L[x][y] = 1
  85.         P[x][y] = [[(x,y)]]
  86.     else:
  87.         P[x][y] = result
  88.     return copy.deepcopy(P[x][y])
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-30 11:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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