一亩三分地论坛

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

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

ebay 面试 NP问题请教

[复制链接] |试试Instant~ |关注本帖
lee2009jian 发表于 2015-1-19 12:34:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@eBay - 内推 - Onsite |Other

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

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

x
Hello,

  本人**一位,前几天面了ebay,请教一个题
. visit 1point3acres.com for more.
  给 1 输出 1
  给 2 输出 11,12,21,22(4个数)
  给 3 输出 111,112,113,121,122,123,132,133,211,212,213,221,222,223,231,232,233,311,312,313,321,322,323,331,332,333 (27个数).鐣欏璁哄潧-涓浜-涓夊垎鍦
-google 1point3acres
如果给N 输出所有由小于等于这个数的合集. more info on 1point3acres.com
. 1point 3acres 璁哄潧
请问是NP问题么?应该怎么做
dalei 发表于 2015-1-19 13:36:52 | 显示全部楼层
这个应该是用dfs可以就可以吧
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-1-19 16:02:47 | 显示全部楼层
27个数字里似乎少了一个的样子...
从第一个位置开始,从小到大枚举这个位置的可能数字,然后递归到下一位...
求下面的筒子们指正...
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-1-19 16:42:37 | 显示全部楼层
        public static void helper(String s, int n){
                if(s.length()==n){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        System.out.println(s);
                        return;. more info on 1point3acres.com
                }
                for(int i =1;i<=n;i++){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                helper(s+Integer.toString(i),n);
                }
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        这样可以不
回复 支持 反对

使用道具 举报

zj45499 发表于 2015-1-19 18:01:34 | 显示全部楼层
楼上Integer.toString多余了  直接 s+i 就可以了
  1.     public static void addPrefix(String prefix, int n) {
  2.         if (prefix.length() == n) {
  3.             System.out.println(prefix);
  4.         } else {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.             for (int i = 1; i <= n; i++) {
  6.                 addPrefix(prefix + i, n);
  7.             }
  8.         }
  9.     }
复制代码
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-1-20 09:21:29 | 显示全部楼层
是 NP problem. . From 1point 3acres bbs
给定N,总共有 N^N个组合要输出

这题目是permutations的变体.区别是,在递归处理下一位之前,不需要再检查当前位是否已经组合过了.
  1. void dfs(vector<vector<int> > &results, int n, vector<int> & sol){
  2.     if(sol.size() == n){
  3.         results.push_back(sol);
  4.         return ;
  5.     }-google 1point3acres
  6.     for(int i=1; i<=n; i++){
  7.             sol.push_back(i);
  8.             dfs(results, n, sol);
  9.             sol.pop_back();-google 1point3acres
  10.     }
  11. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12. . visit 1point3acres.com for more.
  13. vector<vector<int> > getSets(int n) {-google 1point3acres
  14.     vector<vector<int> > results;
  15.     if(n==0) return results;
  16.     vector<int> sol;
  17.     dfs(results, n, sol);
  18.     return results;
  19. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| lee2009jian 发表于 2015-1-20 14:55:34 | 显示全部楼层
感谢各位,自己调试通过了。。。. more info on 1point3acres.com
自己真是水平低啊
需要继续努力
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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