y****z
发帖数: 52 | 1 你这个方法就是用两个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=fal... 阅读全帖 |
|
a****r
发帖数: 87 | 2 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){... 阅读全帖 |
|
a****r
发帖数: 87 | 3 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){... 阅读全帖 |
|
b******i
发帖数: 914 | 4 贴个code，不过只test了几种case
/*
给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
个*代表一个任意字符。
*/
#include
#include
#include
using namespace std;
struct TrieNode {
TrieNode():is_word(false),children(26,nullptr) {}
bool is_word;
vector children;
};
class Solution {
public:
bool string_in_list(vector strings, string s) {
if(s.length() == 0 || strings.size() == 0)
return false;
// construct trie
... 阅读全帖 |
|
|
|
l******s
发帖数: 3045 | 7 有笔误，应该是创建SortedSet时指定一个排序方法。比如下面：
SortedSet ss = new SortedSet(Comparer.Create((
a, b) => a.CallTimes == b.CallTimes ? a.PhoneName.CompareTo(b.PhoneName) : b.
CallTimes.CompareTo(a.CallTimes)));
我用的是C#，Java也有类似的创建自定义的排序的Compare的方法。 |
|
g***9
发帖数: 159 | 8 第二题公共前缀并不是leetcode原题吧...
请教大牛 rolling hash 的解法 .. ?
自己写了一个Trie的python版本:
import sys
CHAR_COUNT = 26
class Entry(object):
def __init__(self, count=0, next=None):
self.cnt = count
self.nxt = next
#def
#class
class TrieNode(object):
def __init__(self):
self.entrylist = []
for i in xrange(CHAR_COUNT):
self.entrylist.append(Entry())
#for
#def
#class
root = TrieNode()
def InsertTrieNodes(root, curstr):
n = len(curstr)
prefix = []
curnode = root
valid = Tru... 阅读全帖 |
|
l******s
发帖数: 3045 | 9 TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以
，创建TrieNode时指定一个排序的方法，按照call times排即可。时间复杂度O(nlgn)
，n是Trie搜索的结果长度。 |
|
I******k
发帖数: 378 | 10 这两个可以用同样的数据结构实现吧， 感觉suffix tree就是trie的一种特殊情况，从
不同的位置开始到字符串末尾得到的substr建起来的trie. 最简单的实现下面这种就可
以了吧：
struct trieNode
{
trieNode *child[26]; // suppose only contain a-z
char *str; // characters in this node
}；
各位有什么看法？ |
|
b******7
发帖数: 92 | 11 4）
设两人概率分别为p1,1-p1
则p1 = 1/6 + 5/6 * (1-p1) ==> p1 = 6/11, 1-p1 = 5/11
5)
判断顺子：将7张牌按数字排序，然后遍历找是否有连续的5个数字
判断同花：将7张牌按花色排序，然后找是否有连续的5个花色
判断同花顺：将同花中的最多连续的花色按数字排序，找连续5个数字
6)
构建trie，trie节点中加一个计数变量，统计多少个url包含该trie节点，然后按层遍
历+减枝找到最长的prefix
struct TrieNode{
char c;
vector childs;
int count;
}; |
|
s********u
发帖数: 1109 | 12 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
s********u
发帖数: 1109 | 13 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
e********3
发帖数: 229 | 14
不懂.
比如你输入a, 那你要搜索a下面所有trienode,然后再把搜索结果进行排序吧?
"创建TrieNode时指定一个排序的方法，按照call times排即可"
这是什么意思 |
|
l******0
发帖数: 244 | 15 public List listAllWordsinTrie(){
List words = new ArrayList();
if(root == null){
return words;
}
StringBuilder prefix = new StringBuilder();
allWordsHelper(root.children,prefix,words);
return words;
}
// depth first search
private void allWordsHelper(List children, StringBuilder
prefix, List words){
for(int i= 0; i
... 阅读全帖 |
|
A*****i
发帖数: 3587 | 16 知道一种数据结构，算法你自己完成吧
typedef struct node{
node * next;
int word[26];
}trieNode; |
|
y*****e
发帖数: 712 | 17 lz, 我刚才写了写trie这题，感觉代码量不小啊，得写trienode再写trie class里的
match words， 你这轮2题，难道15分钟这题就得写出来？无bug? 这要求也太高了吧 |
|
发帖数: 1 | 18 如果用trie的结构的话，如果trie太大，cache放不下，要怎样放到disk里呢？
是否要用key value store database，每个trienode设置一个ID当做key，然后child
nodes的ID存在value里？ |
|
