推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

ebay 面试 NP问题请教

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

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

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

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

x
Hello,

  本人**一位,前几天面了ebay,请教一个题

  给 1 输出 1. From 1point 3acres bbs
  给 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个数). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

如果给N 输出所有由小于等于这个数的合集

请问是NP问题么?应该怎么做
dalei 发表于 2015-1-19 13:36:52 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这个应该是用dfs可以就可以吧
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-1-19 16:02:47 | 显示全部楼层
关注一亩三分地微博:
Warald
27个数字里似乎少了一个的样子... 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
从第一个位置开始,从小到大枚举这个位置的可能数字,然后递归到下一位...
求下面的筒子们指正...
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-1-19 16:42:37 | 显示全部楼层
        public static void helper(String s, int n){.1point3acres缃
                if(s.length()==n){
                        System.out.println(s);
                        return;
                }
. From 1point 3acres bbs                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++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.                 addPrefix(prefix + i, n);
  7.             }
  8.         }
  9.     }
复制代码
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-1-20 09:21:29 | 显示全部楼层
是 NP problem.
给定N,总共有 N^N个组合要输出
. Waral 鍗氬鏈夋洿澶氭枃绔,
这题目是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.     }
  6.     for(int i=1; i<=n; i++){. more info on 1point3acres.com
  7.             sol.push_back(i);
  8.             dfs(results, n, sol);
  9.             sol.pop_back();
  10.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11. }

  12. vector<vector<int> > getSets(int n) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.     vector<vector<int> > results;
  14.     if(n==0) return results;
  15.     vector<int> sol;
  16.     dfs(results, n, sol);
  17.     return results;.1point3acres缃
  18. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-24 08:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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