l*e
2 楼
说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
写三个function，
第一个，给定号码，检查是否被占用
第二个，给定号码，标注其已经被占用
第三个，返回一个没有被占用的号码
要求复杂度
估计挂了
后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
后222, 然后3333
这样直接跳过
可惜当时没想到用skip list
写三个function，
第一个，给定号码，检查是否被占用
第二个，给定号码，标注其已经被占用
第三个，返回一个没有被占用的号码
要求复杂度
估计挂了
后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
后222, 然后3333
这样直接跳过
可惜当时没想到用skip list
a*h
3 楼
还是不要玩中概股了
s*i
4 楼
大个的杂质基本能被过滤掉. 总是有很细小的杂质, 对着光线看很明显, 如同空气中的
雾霾.
鱼缸里有一株不知名的植物.
是不是过滤器不够高端？
有什么解决方案呢? 多谢指导
雾霾.
鱼缸里有一株不知名的植物.
是不是过滤器不够高端？
有什么解决方案呢? 多谢指导
m*n
5 楼
50未必卖不卖？我只有50了
s*x
6 楼
感谢分享。
a*h
7 楼
这里不是有很多人喜欢这只股票的马。怎么都不出声了。
【在 a*****h 的大作中提到】
: 还是不要玩中概股了
【在 a*****h 的大作中提到】
: 还是不要玩中概股了
m*i
8 楼
基本上是因为水还没养好，再过段时间看看。
n*e
9 楼
没有,你可用的只有49
【在 m***n 的大作中提到】
: 50未必卖不卖？我只有50了
【在 m***n 的大作中提到】
: 50未必卖不卖？我只有50了
c*n
10 楼
你这个用 hash 里面每个值除了号码， 再记前后两个邻居， 就是把双链表跟hashmap
合起来
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
合起来
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
D*9
11 楼
just loaded 1000 at 6
s*i
12 楼
请问这个养水的原理是什么? 为什么水养好之后杂质会消失呢? 是被某种细菌吃掉了?
【在 m****i 的大作中提到】
: 基本上是因为水还没养好，再过段时间看看。
【在 m****i 的大作中提到】
: 基本上是因为水还没养好，再过段时间看看。
z*y
13 楼
只有17的飘过
【在 n*******e 的大作中提到】
: 没有,你可用的只有49
【在 n*******e 的大作中提到】
: 没有,你可用的只有49
s*e
14 楼
谢谢分享
a*h
15 楼
太早了。等它跌倒4多在买吧。
【在 D******9 的大作中提到】
: just loaded 1000 at 6
【在 D******9 的大作中提到】
: just loaded 1000 at 6
z*y
16 楼
你可以看看前面的帖子，就是培养硝化细菌分解水中有害的氮化物
【在 s****i 的大作中提到】
: 请问这个养水的原理是什么? 为什么水养好之后杂质会消失呢? 是被某种细菌吃掉了?
d*t
17 楼
转了
【在 b***y 的大作中提到】
: 100伪币一个
【在 b***y 的大作中提到】
: 100伪币一个
S*w
18 楼
这个好复杂
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
m*a
19 楼
前几天烧了，昨晚没睡好，今早出水cover了。
m*n
20 楼
哈哈。。
【在 n*******e 的大作中提到】
: 没有,你可用的只有49
【在 n*******e 的大作中提到】
: 没有,你可用的只有49
S*w
21 楼
你是不是想的太复杂了
N 是什么
N 是什么
r*l
22 楼
转了
【在 b***y 的大作中提到】
: 100伪币一个
【在 b***y 的大作中提到】
: 100伪币一个
S*w
23 楼
用hasmap + [可用区间]
假设号码有1， 2， 3，4
开始
hashmap []
可用区间: [1-4]
mark 2
hashmap: [2]
可用区间: [1-1, 3-4]
mark 1
hashmap: [1, 2]
可用区间: [3-4]
1.check, check hashmap O(1)
2. mark, insert hashmap O(1) + 更新 可用区间, < O(N)
3. search, 访问可用区间, O(1)
假设号码有1， 2， 3，4
开始
hashmap []
可用区间: [1-4]
mark 2
hashmap: [2]
可用区间: [1-1, 3-4]
mark 1
hashmap: [1, 2]
可用区间: [3-4]
1.check, check hashmap O(1)
2. mark, insert hashmap O(1) + 更新 可用区间, < O(N)
3. search, 访问可用区间, O(1)
W*t
24 楼
俺要非厚着脸皮找你要一个
你给不给
【在 b***y 的大作中提到】
: 100伪币一个
你给不给
【在 b***y 的大作中提到】
: 100伪币一个
P*r
25 楼
可以用trie吗？
插入和查找都快;
对于找空格，每个节点记录自己下面有多少个已经用过了，来快速找到空格
插入和查找都快;
对于找空格，每个节点记录自己下面有多少个已经用过了，来快速找到空格
r*7
26 楼
电话号码的话，都是数字，用count sort的思路，binary search干这些事，最后复杂
度 > lgn 小于 n
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
度 > lgn 小于 n
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
l*e
27 楼
这道题考我这样的new grad 是不是有点难了
y*z
28 楼
你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
所以这三个functions都是O(1) 空间O(N)
我想了一下 用trie最好
Class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
插入的时候把该节点标记为visited
顺便记录父节点 然后扫描父节点下的所有子节点 如果都是visited就把父节点也标记
为visited
查找不说了
第三个方法的话就变成寻找一个visited=false的叶子就好了(假设号码10位数)
如果一个节点的visited=false 那么必然存在available的子节点
static class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
private static TrieNode root;
private static int length;
public static void init(){
length=10;
root=new TrieNode();
}
public static void insert(String input){
char[] array=input.toCharArray();
TrieNode current=root;
TrieNode parent=null;
for(int i=0;i
if(current.children[index]==null){
current.children[index]=new TrieNode();
}
parent=current;
current=current.children[index];
}
current.visited=true;
for(int i=0;i<10;i++){
if(parent.children[i]==null||parent.children[i].visited==false){
return;
}
}
parent.visited=true;
}
public static boolean search(String input){
char[] array=input.toCharArray();
TrieNode current=root;
for(int i=0;i
if(current.children[index]==null){
return false;
}
current=current.children[index];
}
return current.visited;
}
public static String getOne(){
TrieNode current=root;
StringBuilder sb=new StringBuilder();
for(int i=0;i
for(int j=0;j
sb.append(j);
currentChildren[j]=new TrieNode();
current=currentChildren[j];
break;
}else if(currentChildren[j].visited==false){
sb.append(j);
current=currentChildren[j];
break;
}
}
}
// insert(sb.toString());
return sb.toString();
}
public static void main(String []args){
//System.out.println("Hello World");
init();
insert("1234567890");
insert("0987654321");
insert("0000000002");
System.out.println(search("1234567890"));
String newNum=getOne();
System.out.println(newNum);
insert(newNum);
System.out.println();
System.out.println(getOne());
insert(getOne());
System.out.println(getOne());
}
插入查找和第三个函数的复杂度为O(k) k为号码长度 接近于常数级别。
【在 S***w 的大作中提到】
: 用hasmap + [可用区间]
: 假设号码有1， 2， 3，4
: 开始
: hashmap []
: 可用区间: [1-4]
: mark 2
: hashmap: [2]
: 可用区间: [1-1, 3-4]
: mark 1
: hashmap: [1, 2]
所以这三个functions都是O(1) 空间O(N)
我想了一下 用trie最好
Class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
插入的时候把该节点标记为visited
顺便记录父节点 然后扫描父节点下的所有子节点 如果都是visited就把父节点也标记
为visited
查找不说了
第三个方法的话就变成寻找一个visited=false的叶子就好了(假设号码10位数)
如果一个节点的visited=false 那么必然存在available的子节点
static class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
private static TrieNode root;
private static int length;
public static void init(){
length=10;
root=new TrieNode();
}
public static void insert(String input){
char[] array=input.toCharArray();
TrieNode current=root;
TrieNode parent=null;
for(int i=0;i
if(current.children[index]==null){
current.children[index]=new TrieNode();
}
parent=current;
current=current.children[index];
}
current.visited=true;
for(int i=0;i<10;i++){
if(parent.children[i]==null||parent.children[i].visited==false){
return;
}
}
parent.visited=true;
}
public static boolean search(String input){
char[] array=input.toCharArray();
TrieNode current=root;
for(int i=0;i
if(current.children[index]==null){
return false;
}
current=current.children[index];
}
return current.visited;
}
public static String getOne(){
TrieNode current=root;
StringBuilder sb=new StringBuilder();
for(int i=0;i
for(int j=0;j
sb.append(j);
currentChildren[j]=new TrieNode();
current=currentChildren[j];
break;
}else if(currentChildren[j].visited==false){
sb.append(j);
current=currentChildren[j];
break;
}
}
}
// insert(sb.toString());
return sb.toString();
}
public static void main(String []args){
//System.out.println("Hello World");
init();
insert("1234567890");
insert("0987654321");
insert("0000000002");
System.out.println(search("1234567890"));
String newNum=getOne();
System.out.println(newNum);
insert(newNum);
System.out.println();
System.out.println(getOne());
insert(getOne());
System.out.println(getOne());
}
插入查找和第三个函数的复杂度为O(k) k为号码长度 接近于常数级别。
【在 S***w 的大作中提到】
: 用hasmap + [可用区间]
: 假设号码有1， 2， 3，4
: 开始
: hashmap []
: 可用区间: [1-4]
: mark 2
: hashmap: [2]
: 可用区间: [1-1, 3-4]
: mark 1
: hashmap: [1, 2]
w*n
29 楼
可以用两个hashtable么。一个存已经占用的一个存还没占用的。
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
v*y
30 楼
电话号码位数是固定的10位？
O(n)的n指的是数据库里的号码数量？
O(n)的n指的是数据库里的号码数量？
z*o
31 楼
haha, all O(1)
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
g*d
32 楼
靠，有那么复杂吗？
< O(N) 有 O(lgN)
有没有插入删除，直接就来一个sorted array 就可以了
binary search
< O(N) 有 O(lgN)
有没有插入删除，直接就来一个sorted array 就可以了
binary search
x*n
33 楼
讲讲记录没有占用的hashtable怎么设计，不懂。。。
我想到的比较浪费的做法是用bloom filter检查某个号码用了没。
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
我想到的比较浪费的做法是用bloom filter检查某个号码用了没。
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
x*n
34 楼
这个不能保证寻找一个未使用号码的效率小于O（N）吧？沿着链表扫描的效率是O（N）
啊。
hashmap
【在 c******n 的大作中提到】
: 你这个用 hash 里面每个值除了号码， 再记前后两个邻居， 就是把双链表跟hashmap
: 合起来
啊。
hashmap
【在 c******n 的大作中提到】
: 你这个用 hash 里面每个值除了号码， 再记前后两个邻居， 就是把双链表跟hashmap
: 合起来
n*n
35 楼
代码狂人。我要是面试的，印象肯定不好。太长了。
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
g*c
36 楼
第三个函数的复杂度worst case是10^k吧？要把所有的都试一遍。
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
w*1
37 楼
不知道LZ所谓的O(n)里面的n到底指什么
n=10的话，我感觉好难啊，不像是电面的题
n=所有电话号码个数的话
下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
-------------------------------------
unordered_map phone_book;
int result;
for (auto x : phone_book) {
if (x.second == false) { // number have not used
result = x.first;
break;
}
}
cout << result << endl;
n=10的话，我感觉好难啊，不像是电面的题
n=所有电话号码个数的话
下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
-------------------------------------
unordered_map
int result;
for (auto x : phone_book) {
if (x.second == false) { // number have not used
result = x.first;
break;
}
}
cout << result << endl;
l*e
38 楼
要求小于O(n)
【在 w*****1 的大作中提到】
: 不知道LZ所谓的O(n)里面的n到底指什么
: n=10的话，我感觉好难啊，不像是电面的题
: n=所有电话号码个数的话
: 下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
: -------------------------------------
: unordered_map phone_book;
: int result;
: for (auto x : phone_book) {
: if (x.second == false) { // number have not used
: result = x.first;
【在 w*****1 的大作中提到】
: 不知道LZ所谓的O(n)里面的n到底指什么
: n=10的话，我感觉好难啊，不像是电面的题
: n=所有电话号码个数的话
: 下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
: -------------------------------------
: unordered_map
: int result;
: for (auto x : phone_book) {
: if (x.second == false) { // number have not used
: result = x.first;
w*1
39 楼
那还真挺难的，估计是要求log(n)的复杂度
放狗搜了下，好像真的要用trie什么的来贮存电话本，这也太难了。。。
麻烦楼主知道答案的话，把代码写写呗，解释的那些看不太懂
【在 l******e 的大作中提到】
: 要求小于O(n)
放狗搜了下，好像真的要用trie什么的来贮存电话本，这也太难了。。。
麻烦楼主知道答案的话，把代码写写呗，解释的那些看不太懂
【在 l******e 的大作中提到】
: 要求小于O(n)
y*z
40 楼
晕 Trie其实写起来不复杂
要简单那就用两个hashmap咯
简单容易理解
【在 n******n 的大作中提到】
: 代码狂人。我要是面试的，印象肯定不好。太长了。
要简单那就用两个hashmap咯
简单容易理解
【在 n******n 的大作中提到】
: 代码狂人。我要是面试的，印象肯定不好。太长了。
y*z
41 楼
同学 你的复杂度没学好吧
两个for循环嵌套 如果k＝10
复杂度是O（10*10）
哪来的指数级别??
【在 g*****c 的大作中提到】
: 第三个函数的复杂度worst case是10^k吧？要把所有的都试一遍。
两个for循环嵌套 如果k＝10
复杂度是O（10*10）
哪来的指数级别??
【在 g*****c 的大作中提到】
: 第三个函数的复杂度worst case是10^k吧？要把所有的都试一遍。
J*o
42 楼
这题真的适合电面吗？。。。
g*c
43 楼
不好意思先看错了 以为是dfs那种 每一步有10个选择 一共需要k步
【在 y****z 的大作中提到】
: 同学 你的复杂度没学好吧
: 两个for循环嵌套 如果k＝10
: 复杂度是O（10*10）
: 哪来的指数级别??
【在 y****z 的大作中提到】
: 同学 你的复杂度没学好吧
: 两个for循环嵌套 如果k＝10
: 复杂度是O（10*10）
: 哪来的指数级别??
s*l
44 楼
你这个O(n)只 电话长度 还是电话本长度啊？
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
相关阅读