传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1788|回复: 6
收起左侧

ebay 面试 NP问题请教

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

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

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

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

x
Hello,

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

  给 1 输出 1-google 1point3acres
  给 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 | 显示全部楼层
这个应该是用dfs可以就可以吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

YY大帝 发表于 2015-1-19 16:42:37 | 显示全部楼层
        public static void helper(String s, int n){
                if(s.length()==n){
                        System.out.println(s);
                        return;
                }
                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);.1point3acres缃
  4.         } else {
  5.             for (int i = 1; i <= n; i++) {
    . more info on 1point3acres.com
  6.                 addPrefix(prefix + i, n);. from: 1point3acres.com/bbs
  7.             }
  8.         }
  9.     }
复制代码
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-1-20 09:21:29 | 显示全部楼层
是 NP problem.
给定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.     }
  6.     for(int i=1; i<=n; i++){
  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;. 1point 3acres 璁哄潧
  16.     dfs(results, n, sol);
  17.     return results;
  18. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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