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


一亩三分地论坛

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

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

Google电面 已跪

[复制链接] |试试Instant~ |关注本帖
qqrcde 发表于 2016-11-30 22:38:34 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 本科 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
Unique Paths的变种,要求X只能往下走,Y的话可以+1, -1或者不动。比如4*4的格子
有4中解法。1000
1000
1000. Waral 鍗氬鏈夋洿澶氭枃绔,
1000
. 鍥磋鎴戜滑@1point 3 acres
1000
0100
1000
1000. 1point3acres.com/bbs

1000
1000
0100.1point3acres缃
1000

1000
0100. more info on 1point3acres.com
0100
1000


我也知道是DP,可以满脑子空白懵逼,跪了,求大神调教。. 1point 3acres 璁哄潧


补充内容 (2016-11-30 22:41):
忘了说最大懵逼点是:这类问题都是总左上走到右下,这个是从左上走到左下。

评分

1

查看全部评分

kunge12345 发表于 2016-11-30 23:11:39 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
状态转移方程:
dp[j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j + 1]
判断一下边界,最后返回左下角就好

补充内容 (2016-11-30 23:14):
滚动数组优化到一维
回复 支持 1 反对 0

使用道具 举报

kunge12345 发表于 2016-12-1 00:34:35 | 显示全部楼层
关注一亩三分地微博:
Warald

public static int numPath(int row, int col){
    // Assume the input is valide
    int[][] dp = new int[2][col]; //int[][] dp = new int[row][col];

    // Initialize
    dp[0][0] = 1;

    // Transition
    for(int i = 1; i < row; i++){. 鍥磋鎴戜滑@1point 3 acres
        for(int j = 0; j < col; j++){
            if(j == 0){
                dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[(i - 1) % 2][j + 1];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            }
            else if(j == col - 1){
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + dp[(i - 1) % 2][j];
            }
            else{
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + dp[(i - 1) % 2][j] + dp[(i - 1) % 2][j + 1];
            }
        }
    }

    // Result. 1point3acres.com/bbs
    return dp[(row - 1) % 2][0];-google 1point3acres
}

.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-12-1 00:38):. 1point 3acres 璁哄潧
我是说space一维啊,不是time...
回复 支持 1 反对 0

使用道具 举报

 楼主| qqrcde 发表于 2016-11-30 23:14:41 | 显示全部楼层
kunge12345 发表于 2016-11-30 23:11. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
状态转移方程:
dp[j] = dp[j] + dp[j - 1] + dp[j + 1]
判断一下边界,最后返回左下角就好

谢谢 你和面试官的回复一样啊!我还是题做的太少,遇到变种马上懵逼
回复 支持 反对

使用道具 举报

2008 发表于 2016-11-30 23:38:01 | 显示全部楼层
递归,
  1. #include <iostream>
  2. #include <vector>. from: 1point3acres.com/bbs
  3. using namespace std; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  5. void init(vector<vector<int> > & input, int size) {
  6.   for(int i=0; i<size; i++) {
  7.     vector<int> vec(size, 0); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.     input.push_back(vec);
  9.   }
  10. }

  11. void show(vector<vector<int> > & input) {
  12.   for(int i=0; i<input.size(); i++) {
  13.     for(int j=0; j<input[0].size(); j++) {
  14.      cout<<input[i][j]<<" ";
  15.     }
  16.     cout<<endl;
  17.   }
  18.   cout<<endl<<endl;
  19. }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  20. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  21. void run(vector<vector<int> > &input, int x, int y, int & count) {
  22.   if(x==input.size()-1) {
  23.     if(y==0) {
  24.       count++;
  25.       input[x][y]=1;
  26.       show(input);. from: 1point3acres.com/bbs
  27.       input[x][y]=0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.       return;. 1point3acres.com/bbs
  29.     } else {
  30.       return;. visit 1point3acres.com for more.
  31.     }
  32.   }
  33.   if(y>0) {
  34.     input[x][y]=1;
  35.     run(input, x+1, y-1, count);
  36.     input[x][y]=0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  37.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.   if(y<input.size()-1) {
  39.     input[x][y]=1;
  40.     run(input, x+1, y+1, count);
  41.     input[x][y]=0;
  42.   }
  43.   input[x][y]=1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.   run(input, x+1, y, count);
  45.   input[x][y]=0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  46. }

  47. int main() {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.   vector<vector<int> > input;
  49.   init(input, 6);
  50.   int count;
  51.   run(input, 0, 0, count);
  52.   cout<<"We found "<<count<< " ways!"<<endl;
  53. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
回复 支持 反对

使用道具 举报

2008 发表于 2016-12-1 00:03:26 | 显示全部楼层
kunge12345 发表于 2016-11-30 23:11. from: 1point3acres.com/bbs
状态转移方程:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
dp[j] = dp[j] + dp[j - 1] + dp[j + 1]. 1point3acres.com/bbs
判断一下边界,最后返回左下角就好

没错,求方法数应该用DP,学习了。
  1. int run(int len) {
  2.   if(len<=2)  return 1;;

  3.   vector<int> result(len, 0);
  4.   result[0]=1;
  5.   for(int i=1; i<len; i++) {
  6.     vector<int> tmp(len, 0);
  7.     tmp[0]=result[0]+result[1];. visit 1point3acres.com for more.
  8.     tmp[len-2]=result[len-2]+result[len-1];
  9.     for(int j=1; j<len-1; j++)
  10.       tmp[j]=result[j-1]+result[j]+result[j+1];
  11.     result=tmp;
  12.   }
  13.   return result[0];
  14. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
复制代码
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-12-1 00:14:54 | 显示全部楼层
kunge12345 发表于 2016-11-30 23:11
.1point3acres缃状态转移方程:
dp[j] = dp[j] + dp[j - 1] + dp[j + 1]
判断一下边界,最后返回左下角就好

求一维代码。。
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-2 14:04:31 | 显示全部楼层
qqrcde 发表于 2016-11-30 23:14
谢谢 你和面试官的回复一样啊!我还是题做的太少,遇到变种马上懵逼
. 1point 3acres 璁哄潧
这个解法是错的。。。4*4的输出结果5。用2维dp会简单很多。
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-2 14:20:26 | 显示全部楼层
```public int uniquePaths(int m, int n) {
        if(m == 0 || n == 0) return 0;
        int[] dp = new int[n];
        int[] preDp = new int[n];
        preDp[0] = dp[0] = 1;
        for(int i=1;i<m;i++){
            for(int j=0;j<Math.min(n, i+1);j++){. Waral 鍗氬鏈夋洿澶氭枃绔,
                if(j-1 >= 0) dp[j] += preDp[j-1]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if(j+1 < Math.min(n, i+1)) dp[j] += preDp[j+1];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            }
            preDp = dp.clone();
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
        return dp[0];. more info on 1point3acres.com
    }

```
这个是我刚写的1维dp,已经测试是正确的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 13:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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