一亩三分地论坛

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

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

snapchat电面gg

[复制链接] |试试Instant~ |关注本帖
304671127 发表于 2016-8-6 07:45:40 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
随便聊聊简历,然后一道题,有墙找路的变形 1 是路 0 是墙, 让你从左边col的任意点走到右边col的任意点的最小step。走不到就返回-1
注意起始点是任意左col的点 而不是左上 , 也不是走到右下。 要考虑到中间如果有一个col全部都是0(墙)的case
没做出来,哪个大神写下分享我看看吧。

评分

1

查看全部评分

waikai 发表于 2016-8-6 13:32:53 | 显示全部楼层
csushin1992 发表于 2016-8-6 13:18
Java version of the above post:
敬请斧正!

好像有问题,第二个“//mark them as visited grids.”那里,可能标记慢了。你col = 0的时候是放进Queue的同时标记的, 之后也应该是从放入Queue的时候标记,不该是从Queue中取出才标记。
回复 支持 1 反对 0

使用道具 举报

Believers 发表于 2016-8-6 08:48:19 | 显示全部楼层
LZ这个走到方向是四个方向都可以走吗?
回复 支持 反对

使用道具 举报

Believers 发表于 2016-8-6 09:28:33 | 显示全部楼层
我觉得应该就是用Dijkstra找图上两点的最短路径
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-8-6 10:51:39 | 显示全部楼层
不就是最基本的BFS的嘛,你可以认为从一个虚拟节点开始搜索,这个节点的邻居就是第一列的所有点
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-6 11:23:19 | 显示全部楼层
从左边每一个 1 开始, dfs , 4 个方向都要找, 记录 visit[i,j], 要剪枝 记录 possible[i,j]
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-8-6 12:09:22 | 显示全部楼层
好像是写出来了, 但总感觉很乱, 望指点!
另外大家程序刚开始的corner case检查怎么写才比较优雅?
. more info on 1point3acres.com
int ltr(vector<vector<int>> &v){. 鍥磋鎴戜滑@1point 3 acres
        vector<int> dir={0,1,0,-1,0};. Waral 鍗氬鏈夋洿澶氭枃绔,
        int n=v.size();
        if(!n) return 0;
        int m=v[0].size();
        if(!m) return 0;
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++)
                if(v[i][0]==1){
                        v[i][0]=2; //先默认设为2
                        q.push(make_pair(i,0));
                }
        int dis=2; //2,3,4....
        while(q.size()){
                dis++;
                int size=q.size();
                for(int k=0;k<size;k++){
                        int i=q.front().first, j=q.front().second;
                        q.pop();
                        for(int p=0;p<4;p++){
                                int ii=i+dir[p], jj=j+dir[p+1];
                                if(ii<0||jj<0||ii>=n||jj>=m||v[ii][jj]!=1) continue;
                                v[ii][jj]=dis;
                                q.push(make_pair(ii,jj));
                                if(jj==m-1) return dis-1;
                        }
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        return -1;
}

int main() {
        vector<vector<int>> v={{0,0,1,0},{0,1,1,0},{1,1,1,1},{0,1,1,0}};
        cout<<ltr(v)<<endl;
        return 0;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴}
回复 支持 反对

使用道具 举报

waikai 发表于 2016-8-6 13:06:28 | 显示全部楼层
  1. class Solution {
  2.         int[][] matrix;
  3.         int[][] dp;
  4.         public int getMinLen(int[][] matrix) {
  5.                 this.matrix = matrix;
  6.                 dp = new int[matrix.length][matrix[0].length];
  7.                 //init col == 0;
  8.                 for (int i = 0; i < matrix.length; i++) {
  9.                         dp[i][0] = matrix[i][0];
  10.                 }
  11.                 //normal case
  12.                 for (int prvCol = 0; prvCol < matrix[0].length-1; prvCol++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.                         for (int i = 0; i < matrix.length; i++) {
  14.                                 if (dp[i][prvCol] == 0 || matrix[i][prvCol+1] == 0) continue;
  15.                                 if (dp[i][prvCol+1] == 0 || dp[i][prvCol+1] > dp[i][prvCol]+1) {
  16.                                         dp[i][prvCol+1] = dp[i][prvCol]+1;
  17.                                         dfsInCol(i+1, prvCol+1, dp[i][prvCol]+2, 1); // go down
    . visit 1point3acres.com for more.
  18.                                         dfsInCol(i-1, prvCol+1, dp[i][prvCol]+2, -1);// go up
  19.                                 }
  20.                         }
  21.                 }
  22.                 // last col
  23.                 int res = Integer.MAX_VALUE;
  24.                 for (int i = 0; i < matrix.length; i++) {
  25.                         if (dp[i][matrix[0].length-1] != 0) res = Math.min(res, dp[i][matrix[0].length-1]);
  26.                 }
  27.                 if (res == Integer.MAX_VALUE) return -1;
    . 鍥磋鎴戜滑@1point 3 acres
  28.                 return res;
  29.         }
  30.         private void dfsInCol(int row, int col, int k, int d) {
  31.                 if (row < 0 || row >= matrix.length || matrix[row][col] == 0 ) return;
  32.                 if (dp[row][col] == 0 || dp[row][col] > k) {
  33.                         dp[row][col] = k;
  34.                         dfsInCol(row+d, col, k+1, d);
  35.                 }
  36.         }
  37. }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 13:10:47 | 显示全部楼层
lvvvvv 发表于 2016-8-6 11:23. more info on 1point3acres.com
从左边每一个 1 开始, dfs , 4 个方向都要找, 记录 visit, 要剪枝 记录 possible
. From 1point 3acres bbs
既然题目说了是从最左边的任何一点到最右边的任何一点,我想只需要搜索上、下、右三个方向了吧?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 13:11:10 | 显示全部楼层
ryancooper 发表于 2016-8-6 10:51
. 1point 3acres 璁哄潧不就是最基本的BFS的嘛,你可以认为从一个虚拟节点开始搜索,这个节点的邻居就是第一列的所有点
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果使用BFS的话,那还需要加另外一个二维数组记录是否访问过么?
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 13:18:09 | 显示全部楼层
Java version of the above post:
敬请斧正!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

                               
登录/注册后可看大图

. visit 1point3acres.com for more.

                               
登录/注册后可看大图


public class Pair{
        int x, y;
        public Pair(int x, int y){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                this.x = x;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                this.y = y;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}

. 鍥磋鎴戜滑@1point 3 acresint main(int[][] board){
        Queue<Pair> que = new Queue<Pair>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        for(int i=0; i<board.length; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(board[0] == 1) {
                        que.offer(new Pair(i, 0));
                        board[0] = 2;//mark them as visited grids.. 1point 3acres 璁哄潧
                }. 1point 3acres 璁哄潧
        }
        int dis = 0;
        while(!que.isEmpty()){
                int size = que.size();
                dis++;
                for(int i=0; i<size; i++){
                        Pair cur = que.poll();
                        if(cur.y==board[0].length-1 && board[cur.x][cur.y] == 1) return dis;
                        if(cur.x > 0 && board[cur.x-1][cur.y] == 1) que.offer(new Pair(cur.x-1, cur.y));
                        if(cur.y > 0 && board[cur.x][cur.y-1] == 1) que.offer(new Pair(cur.x, cur.y-1));
                        if(cur.x < board.length-1 && board[cur.x+1][cur.y] == 1) que.offer(new Pair(cur.x+1, cur.y));
                        if(cur.y < board[0].length-1 && board[cur.x][cur.y+1] == 1) que.offer(new Pair(cur.x, cur.y+1));. visit 1point3acres.com for more.
                        board[cur.x][cur.y] = 2;//mark them as visited grids.. visit 1point3acres.com for more.
                }
. From 1point 3acres bbs        }
        return -1;
}


                               
登录/注册后可看大图


                               
登录/注册后可看大图

. From 1point 3acres bbs



. visit 1point3acres.com for more.
补充内容 (2016-8-6 13:42):. from: 1point3acres.com/bbs
应该吧board[cur.x+/-1][cur+/-1]=2放在之前的四个if statements里。
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 13:37:46 | 显示全部楼层
我的DP解法。。感觉肯定有逻辑的问题,求斧正:

int main(int[][] board){
        int[][] dp = new int[board.length][board[0].length];
        for(int i=0; i<board.length; i++){//set initial states
                dp[i][0] = board[i][0];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
        for(int i=0; i<board.length; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                for(int j=1; j<board[0].length; j++){
                        if(board[i][j] == 1){
                                int minStep = Integer.MAX_VALUE;
                                if(i>0 && dp[i-1][j]>0) minStep = Math.min(minStep, dp[i-1][j]+1);
                                if(j>0 && dp[i][j-1]>0) minStep = Math.min(minStep, dp[i][j-1]+1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                if(i<board.length-1 && dp[i+1][j]>0) minStep = Math.min(minStep, dp[i+1][j]+1);
                                if(j<board.length-1 && dp[i][j+1]>0) minStep = Math.min(minStep, dp[i][j+1]+1);. from: 1point3acres.com/bbs
                                dp[i][j] = minStep==Integer.MAX_VALUE?0:minStep;. 1point 3acres 璁哄潧
                        }
                }
        }
        int min = Integer.MAX_VALUE;
        for(int i=0; i<board.length; i++){//set initial states. From 1point 3acres bbs
                min = Math.min(min, dp[i][board[0].length-1]);
        }. 1point3acres.com/bbs
        return min==Integer.MAX_VALUE?-1:min;
}. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-6 13:41:10 | 显示全部楼层
waikai 发表于 2016-8-6 13:32
好像有问题,第二个“//mark them as visited grids.”那里,可能标记慢了。你col = 0的时候是放进Queue ...
. visit 1point3acres.com for more.
对的~!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
8字符8字符。
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-8-6 13:50:55 | 显示全部楼层
最基本的bfs, 时间效率和dp一样。
回复 支持 反对

使用道具 举报

waikai 发表于 2016-8-6 14:02:46 | 显示全部楼层
csushin1992 发表于 2016-8-6 13:37
我的DP解法。。感觉肯定有逻辑的问题,求斧正:

int main(int[][] board){

不对吧,你考虑比如col[0] = {1,0,0,0,0,0,1} col[1] = {1,1,1,1,1,1,1}。你由上而下dp, col[1][4] 就变 6 了
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-6 22:40:57 | 显示全部楼层
csushin1992 发表于 2016-8-6 13:10
既然题目说了是从最左边的任何一点到最右边的任何一点,我想只需要搜索上、下、右三个方向了吧?

完全有可能 Z 字型才能走到啊
回复 支持 反对

使用道具 举报

 楼主| 304671127 发表于 2016-8-6 23:55:40 | 显示全部楼层
到底哪个是靠谱的答案啊。。
{{0,1,1,1,1,0},
                         {1,1,0,0,1,0},
                         {1,1,0,1,1,0},
                         {0,1,0,1,0,0},
                         {0,1,0,1,1,1}};

补充内容 (2016-8-6 23:56):
按错了  下面哪个 我只是贴了 task case
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-7 03:51:19 | 显示全部楼层
感谢楼主分享~ 写了一个求大家指正~
  1. import java.util.*;. more info on 1point3acres.com

  2. class Solution {
  3.         //1 是路 0 是墙
  4.         int res = Integer.MAX_VALUE;
  5.         public int minStep(int[][] matrix){
  6.                 if(matrix == null || matrix.length == 0) return 0;-google 1point3acres
  7.                 int row = matrix.length, col = matrix[0].length;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.                
  9.                 for(int i = 0; i < row; i++){
  10.                         dfs(i, 0, matrix);
  11.                 }
  12.                 if(res == Integer.MAX_VALUE) return -1;
  13.                 else return res;
  14.         }
  15.        
  16.         private void dfs(int x, int y, int[][] matrix){
  17.                 int row = matrix.length, col = matrix[0].length;. visit 1point3acres.com for more.
  18.                 int[][] dp = new int[row][col];
  19.                 for(int i = 0; i < row; i++){
  20.                         Arrays.fill(dp[i], Integer.MAX_VALUE);
  21.                 }
  22.                
  23.                 boolean[][] visited = new boolean[row][col];
  24.                 helper(x, y, matrix, dp, visited, 0);
  25.         }
  26.        
  27.         private void helper(int x, int y, int[][] matrix, int[][] dp, boolean[][] visited, int step){
  28.                 int row = matrix.length, col = matrix[0].length;
  29.                 if(x < 0 || x >= row || y < 0 || y >= col || matrix[x][y] == 0 || visited[x][y]) return;. 鍥磋鎴戜滑@1point 3 acres
  30.                 if(step >= dp[x][y]) return;
  31.                 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.                 dp[x][y] = step;
  33.                 visited[x][y] = true;
  34.                
  35.                 if(y == col - 1){
  36.                         res = Math.min(res, dp[x][y]);
  37.                         visited[x][y] = false;
  38.                         return;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.                 }
  40.                
  41.                 int[] surroundX = {-1, 1, 0, 0};
  42.                 int[] surroundY = {0, 0, -1, 1};
  43.                 for(int i = 0; i < 4; i++){
  44.                         int nx = x + surroundX[i];
  45.                         int ny = y + surroundY[i];
  46.                         helper(nx, ny, matrix, dp, visited, dp[x][y] + 1);-google 1point3acres
  47.                 }
  48.                 visited[x][y] = false;
  49.         }
  50.        
  51.        
  52.         public static void main(String[] args) {
  53.                 Solution r = new Solution();. 1point 3acres 璁哄潧
  54.                 int[][] matrix =
  55.                 {{0,1,1,1,1,0},
  56.                  {1,1,0,0,1,0},
  57.                  {1,1,0,1,1,0},
  58.                  {0,1,0,1,0,0},.鐣欏璁哄潧-涓浜-涓夊垎鍦
  59.                  {0,1,0,1,1,1}};
  60.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  61.                 int res = r.minStep(matrix);
  62.                 System.out.println(res);
  63.         }. from: 1point3acres.com/bbs
  64. }
复制代码
回复 支持 反对

使用道具 举报

importcoder 发表于 2016-9-13 02:32:09 | 显示全部楼层
感谢楼主分享,用bfs撸了一遍,函数的参数分别是棋盘,起点的坐标,终点的坐标
  1. public class ShortestStep { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.     . 1point 3acres 璁哄潧
  3.     public int shortestPath(int[][] board, int i, int j, int p, int q) {
  4.         
  5.         if (board[i][j] == 0 || board[p][q] == 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.             return -1;
  7.         }
  8.         
  9.         int m = board.length;
  10.         int n = board[0].length;. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         Queue<Integer> queue = new LinkedList<>();
  12.         Map<Integer, Integer> map = new HashMap<>();
  13.         queue.offer(i * n + j);
  14.         map.put(i * n + j, 0);
  15.         while (!queue.isEmpty()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.             int cur = queue.poll();
  17.             int step = map.get(cur);
  18.             int x = cur / n;. 1point 3acres 璁哄潧
  19.             int y = cur % n;
  20.             if (x == p && y == q) {
  21.                 return step;
  22.             }
  23.             
  24.             if (x > 0 && board[x - 1][y] == 1 && !map.containsKey((x - 1) * n + y)) {
  25.                 map.put((x - 1) * n + y, step + 1);
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.                 queue.offer((x - 1) * n + y);
  27.             }
  28.             if (x < m - 1 && board[x + 1][y] == 1 && !map.containsKey((x + 1) * n + y)) {
  29.                 map.put((x + 1) * n + y, step + 1);
  30.                 queue.offer((x + 1) * n + y);
  31.             }
  32.             if (y > 0 && board[x][y - 1] == 1 && !map.containsKey(x * n + y - 1)) {
  33.                 map.put(x * n + y - 1, step + 1);
  34.                 queue.offer(x * n + y - 1);. more info on 1point3acres.com
  35.             }
  36.             if (y < n - 1 && board[x][y + 1] == 1 && !map.containsKey(x * n + y + 1)) {.1point3acres缃
  37.                 map.put(x * n + y + 1, step + 1);
  38.                 queue.offer(x * n + y + 1);
  39.             }
  40.         }
  41.         return -1;
  42.     }
  43.     . 鍥磋鎴戜滑@1point 3 acres
  44.     public static void main(String[] args) {
  45.         ShortestStep solution = new ShortestStep();
  46.         int[][] board = {
  47.                 {1, 0, 1, 1, 1}, .鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.                 {1, 0, 1, 1, 1},
  49.                 {1, 1, 1, 1, 1}, . from: 1point3acres.com/bbs
  50.                 {0, 1, 0, 0, 1},
  51.                 {1, 1, 1, 0, 1}};
  52.         System.out.println(solution.shortestPath(board, 0, 0, 4, 0));
  53.         
  54.         int[][] board0 = {. more info on 1point3acres.com
  55.                 {1, 0, 1, 1, 1},
  56.                 {1, 0, 1, 0, 1},
  57.                 {1, 1, 1, 0, 1}, . more info on 1point3acres.com
  58.                 {0, 1, 0, 0, 1},
  59.                 {1, 1, 1, 0, 1}};
  60.         System.out.println(solution.shortestPath(board0, 0, 0, 4, 4));
  61.         
  62.         int[][] board2 = {
  63.                 {1, 0, 1, 1, 1}, . 鍥磋鎴戜滑@1point 3 acres
  64.                 {1, 0, 1, 1, 1},
  65.                 {1, 1, 1, 0, 1},
  66.                 {0, 1, 0, 0, 1},
  67.                 {1, 1, 1, 0, 1}};
  68.         System.out.println(solution.shortestPath(board2, 0, 0, 4, 4));
  69.         
  70.         int[][] board3 = {
  71.                 {1, 0, 1, 1, 1},
  72.                 {1, 0, 1, 0, 1},
  73.                 {1, 1, 0, 1, 0},
  74.                 {0, 1, 0, 0, 1},
  75.                 {1, 1, 1, 0, 1}};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  76.         System.out.println(solution.shortestPath(board3, 0, 0, 2, 3));
  77.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  78. }
复制代码
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-13 09:18:45 | 显示全部楼层
何打发123 发表于 2016-8-6 14:51
感谢楼主分享~ 写了一个求大家指正~

        int[][] matrix2 = . more info on 1point3acres.com
            {{0,1,1,1,1,0},
             {1,1,0,0,1,0},
             {1,1,0,1,1,0},
             {0,1,0,1,0,0},
             {0,1,0,1,0,1}}; // 期待-1
结果= 12
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 02:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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