c*****a
发帖数: 808 | 1 写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new H... 阅读全帖 |
|
j********g
发帖数: 80 | 2 第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector<... 阅读全帖 |
|
t********6
发帖数: 348 | 3 第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map
string> >& prev, vector& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_ba... 阅读全帖 |
|
p****e
发帖数: 3548 | 4 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
c*****a
发帖数: 808 | 5 写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new H... 阅读全帖 |
|
j********g
发帖数: 80 | 6 第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector<... 阅读全帖 |
|
t********6
发帖数: 348 | 7 第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map
string> >& prev, vector& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_ba... 阅读全帖 |
|
p****e
发帖数: 3548 | 8 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
G****A
发帖数: 4160 | 9 手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
void sentence(string input, int left, int right, string output, map
bool> dict)
{
if (left > right)
cout<
else{
for (int i=left; i<=right; i++){
std::string sub = input.substr(left, i-left+1);
if (dict.find(sub) != dict.end())
sentence(input, i+1, right, output + sub + " ", dict);
}
}
} |
|
z****e
发帖数: 54598 | 10 这题也够坑爹的
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap> routs = new HashMap
>();
this.generateRouts(dict, routs);
ArrayList> result = new ArrayList阅读全帖 |
|
z*******3
发帖数: 13709 | 11 这是新的代码
建 route 的时候，不从字典里面找，而是挨个替换字符串的char，换成其他char，组
建成新字符串，然后再去看字典里有没有，有的话，放到set里去，再把set放到map里
，每个pair表示从key string出发，能够转换的点的集合
然后从start开始找，用linkedlist，不用queue，queue是二叉树，效率低，用
linkedlist快，bfs都用linkedlist，先进先出，linkedlist的pollfirst效率高
然后建立一个类，node，这个node记录当前的string，以及上一个string，还有当前
路径长度
然后方法主体，每次把当前string对应的点取出来，然后看能走到那些点，挨个对比这
些点，看是不是end string，如果是，则表示找到，那就记录当前长度，因为还有可能
有相同长度的解，然后继续，如果不是end string，则查找visitedmap，看是否访问过
，如果访问过，比较当前路径长度跟上次访问的长度，如果上次访问的长度更短，则把
set里面这个node给移除，要不然会产生死循环，这里还要避开并发修改的问题，... 阅读全帖 |
|
z****e
发帖数: 54598 | 12 public
class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap> routs = new HashMap
>();
this.generateRouts(dict, routs);
ArrayList> result = new ArrayList
>>();
LinkedList阅读全帖 |
|
j********r
发帖数: 25 | 13 没有时间看你的是什么问题， 你参考一下如下程序吧：
int ladderLength(string start, string end, unordered_set &dict) {
int remaining = 1;
queue qou;
qou.push(start);
dict.erase(start);
int depth = 0;
while(qou.size() > 0) {
depth++;
int nextLevel = 0;
while(remaining >0) {
string s = qou.front();
qou.pop();
if (s == end) { return depth;}
... 阅读全帖 |
|
c*****n
发帖数: 83 | 14 用二维 DP 做:
Define f_k(i) the number of skipped characters with string s[i,i+k).
Starting from k = 1 initializing f_1(i) = 0 if s[i] is in dict, f_1(i) = 1
otherwise; then calculate f_{k}(i) recursively by
f_{k+1}(i) = min_{h=1}^{k} {f_h(i) + f_{k+1-h}(i+h)} if s[i,i+k+1) is NOT in
dict; otherwise f_{k+1}(i) = 0;
up to k = len(s)
如何判断 s[i,i+k) is in Dict? One-pass preprocessing
Sol(1): the signatures of all words in Dict: the frequencies of letters in
that word, 然后按这个 signature 排序。
Sol(2): Hash ta... 阅读全帖 |
|
T*******e
发帖数: 4928 | 15 哈，咱们思路差不多。
bool wordBreak(string s, unordered_set &dict) { //Time: O(n^2)
int sSize=s.size();
if(sSize<=0||dict.empty()) return false;
vector isWord(sSize+1, false);
isWord[0]=true;
for(int i=1; i<=sSize; ++i) {
for(int j=i-1; j>=0; --j) {
if(dict.find(s.substr(j, i-j))!=dict.end() &&isWord[j]) {
isWord[i]=true;
break;
}
}
}
return isWord[sSize];
}
reused |
|
r*******n
发帖数: 3020 | 16 vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
//DP
for(int i=0; i
for(int j=i;j阅读全帖 |
|
B*****7
发帖数: 137 | 17 这是问题的链接：
http://oj.leetcode.com/problems/word-break/
我的solution是：
public class Solution {
private HashMap cache = new HashMap(
);
public boolean wordBreak(String s, Set dict) {
if( s.length() == 0 ) return false;
if( cache.containsKey( s ) ) return cache.get( s );
Boolean result = false;
for( int i = 0; i < s.length(); i++ ) {
String head = s.substring( 0, i+1 );
String rest = (i < s.length... 阅读全帖 |
|
A****L
发帖数: 138 | 18 public class WordLadderII {
public class Ladder { //Define Ladder class it's important
public Ladder parent;
public String word;
public Ladder(Ladder prev,String w) {parent=prev;word=w;}
}
public ArrayList> findLadders(String start, String end
, HashSet dict) {
ArrayList> ladders = new ArrayList
String>>();
Ladder ladder = new Ladder(null,end); //Here we look from end to
start ... 阅读全帖 |
|
A****L
发帖数: 138 | 19 谢谢你的意见。 我也肯定是同意效率要高才行的。我的意思是在保证效率的前提下，
越简单越好。 具体到这题，基本前提就是能pass OJ。另外要是代码让人容易理解就更
好了。 我的code 的思路就是 一层一层 推进， 如果在到达某层找到了 path 那么到
这层 所有可行的path 都是最短的，然后就直接返回结果了。具体就是下面这个语句。
if(ladders.size()>0) return ladders;
//if found then they are the shortest distance return
虽然 while 终止条件是 empty 但是某一层找到了就返回结果了。
每个ladder 只记录它是从哪个ladder 下来的。 如果一个ladder 下来有很多
children ladder， 那么这个ladder 可能出现在很多path 里，但是这里不会重新产生
ladder object， 只有一个ladder object。 因为所有的children 都指向了它（同一
个object）。
空间存储上，如果clone 记录visited 那么一直是会存在两... 阅读全帖 |
|
p***e
发帖数: 111 | 20 代码很难看，晚上有时间再修改。 同样单向bfs需要1200ms左右ac。
class Solution:
def ladderLength(self, start, end, dict):
dict.add(end)
current, distance, visited = [start], 1, {start:0}
bcurrent, bdistance, bvisited = [end], 1, {end:0}
while current and bcurrent:
pre, bpre,next, bnext = [], [], [], []
for word in current:
for i in xrange(len(word)):
left, right = word[:i], word[i + 1:]
for j in ... 阅读全帖 |
|
R*****i
发帖数: 2126 | 21 这个是C#版本
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace TwoSum
{
class Program
{
static void Main(string[] args)
{
int[] numbers = new int[] { 1, 2, 10, 11, 3, 7, 11, 15 };
int[] li = twoSum(numbers, 9);
if (li != null && li.Length > 1)
{
Console.WriteLine("index1 = {0}, index2 = {1}", li[0], li[1]
);
}
}
static int[] twoSum(i... 阅读全帖 |
|
b****z
发帖数: 176 | 22 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
A****L
发帖数: 138 | 23 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String sta... 阅读全帖 |
|
b****z
发帖数: 176 | 24 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
A****L
发帖数: 138 | 25 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String sta... 阅读全帖 |
|
a***e
发帖数: 413 | 26 写了很久都过不了，15分钟哪里能写完啊？能把思路说清楚就不错了。不知道什么样的
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
vector> res;
vector> empty;
queue curLevel;
queue nextLevel;
vector path;
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bo... 阅读全帖 |
|
a***e
发帖数: 413 | 27 写了很久都过不了，15分钟哪里能写完啊？能把思路说清楚就不错了。不知道什么样的
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
vector> res;
vector> empty;
queue curLevel;
queue nextLevel;
vector path;
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bo... 阅读全帖 |
|
b******i
发帖数: 914 | 28 Hi，
你好，贴一下你的code。有几个问题：
1. Graph g(26)是什么，这个Graph的类是哪儿来的？
2. 中间
for(auto i = 0; i < len; ++i) {
if(w1[i] < w2[i]) {
g.add_edge(w1[i] - 'a', w2[i] - 'a');
} else if(w1[i] > w2[i]) {
g.add_edge(w2[i] - 'a', w1[i] - 'a');
}
}
我觉得有问题，首先并不知道w1[i]和w2[i]哪个大啊，只知道w1
从小到大来排序的)。所以我觉得正缺的应该是:
for(auto i = 0; i < len; ++i) {
if(w1[i] != w2[i])
g.add_edge(w1[i]-'a', w2[i]-'a');
}
最后再... 阅读全帖 |
|
r*****e
发帖数: 30 | 29 int schedule(string str,int cd){
int ts = 0;
map dict;
for(int i = 0; i < str.length(); i++){
if(dict.count(str[i]) == 0 || ts-dict[str[i]] >= cd+1){
dict[str[i]] = ts;
}
else i--; ts++;
}
return ts;
} |
|
r*****e
发帖数: 30 | 30 int schedule(string str,int cd){
int ts = 0;
map dict;
for(int i = 0; i < str.length(); i++){
if(dict.count(str[i]) == 0 || ts-dict[str[i]] >= cd+1){
dict[str[i]] = ts;
}
else i--; ts++;
}
return ts;
} |
|
a***e
发帖数: 413 | 31 https://leetcode.com/problems/word-ladder/
如果也不用其他的如map一类来标记是否已经访问过某个词，有人只用一个queue搞定吗？
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
int ns=start.size(), ne=end.size();
if (ns==0&&ne==0) return 0;
queue q;
string mid;
q.push(start);
int c=1, find=0;
while(q.empty()!=true)
{
start=q.front();
q.pop();
if ( start==end)
... 阅读全帖 |
|
b******n
发帖数: 1629 | 32 版上看了些面经，至少把airbnb的电话面试题都给看到了，虽然最后把airbnb的onsite
推掉了，但电面直接碰上原题的感觉真的好tmd有成就感。最后回馈一下版面。
整体感觉，国人面试官真的都非常的nice，老外大部分也都很nice，甚至碰到的三哥三
妹都很nice，没有感觉恶的。个人感觉面试的时候还是要多说话，不要让面试官说话，
更加不要让面试冷场，这个还是挺重要的，否则面试官一尴尬，直接就觉得没有
chemistry，反馈不可能很好。
我自己由于刷题刷得太烂，根本不想刷，看着就烦，只是把ccr和leetcode答案给看了
几遍，一遍都没写过，别的网站看都没看。所以可能不适用刷题刷的nb的同志们。基本
每家公司每道题都有时间复杂度分析，建议注意。
airbnb电面两轮，一个是house robber，一个是csv parser。
fb电面也是两轮，一个maximum continuous sum for an array, career cup面经原题
，一个是简单的trie，还有一个是n个元素中求包含k个元素的组合，dfs做，follow up
提高performance，被国... 阅读全帖 |
|
w*****1
发帖数: 6807 | 33 刚自己做了下，想法：字典肯定不能动，只能在给出的word上下功夫
1.把给出的word的所有anagrams存一个vector anagrams，用next_
permutation
2.再找每个anagrams里的词是不是在dict里面
时间复杂度应该是factorial(n)，因为所有permutations有factorial(n)个，这里n
是给出word的长度。
代码如下，已测试，板上大牛有更好想法还希望指出，我好改正
-------------------------------------------------------
vector allPermutations(string &s) {
vector result;
if (s.empty()) return result;
sort(s.begin(), s.end());
result.push_back(s);
while (next_permutation(s.begin(), s.end())) {
... 阅读全帖 |
|
u*******n
发帖数: 119 | 34 I install "cxterm5.0.p3" in my machine, which is "SunOS 5.7".
However, complie is not successful. The "Install.log" is as
below :
Building cxterm Version 5.0
Thu Jan 4 17:06:35 PST 2001
xmkmf
imake -DUseInstalled -I/usr/openwin/lib/X11/config
make xrelease
You are using X11R6
make Makefiles
making Makefiles in cxterm...
making Makefiles in utils...
making Makefiles in dict...
making Makefiles in dict/gb...
making Makefiles in dict/big5...
making Makefiles in dict/jis...
making Makefiles in di |
|
l*********o
发帖数: 3091 | 35 #include
#include
#include |
|
u*h
发帖数: 397 | 36 1. 做一个dict, key 是 User ID,value 是一个 Queue
2. Queue 里的每一个node, 包含 一个timestamp 和一个activity count.
3. 每次读取一行数据， 根据user ID, 找到dict中的队列 （如果是新ID,
那么就创建新队列）。 把当前的timeStamp 和activity count加入队列。
根据当前的timeStamp， 将10分钟以前的node踢出队列。 队列计数， 如果
大于500就汇报“机器人”。
4. 每隔n分钟， 对dict进行一次清理： 根据当前的timeStamp, 要求所有
dict中的队列都清理掉10分钟以前的node.
讨论： n 可以取值1-无穷大，如果内存小， n需要取比较小的值，如果内存
大， n可以取比较大的值。 |
|
|
|
b*********n
发帖数: 1258 | 39 build prefix tree on dict. O(nlogn)
search on prefix tree for input string prefix, O(k^2)
k is the length of input string.
OR
hash dict prefix, O(h*n), h is word size in dict.
search input word prefix from hash table, O(k).
k is the length of input string. |
|
j*****u
发帖数: 1133 | 40 俺也不是砖家
先回答3，怎么存储一般改变不了，log的format已经固定好了，通常就是txt file。如
果数据量小了可以in memory hash，方法等同map reduce
1, 2：
mapper：emit >，以customer_id为key hash
local reducer和global reducer 相同的code：
可以sort也可以hash，以date和page其中之一为key，比如date
Dictionary> dict;
while (reducing a customer)
{
dict[date].Add(page);
if (dict.Count > 1 && (any_page_set.Count > 1 || any_two_page_set[0]_are_
different)))
emit customer_id and terminate reducing;
} |
|
d*******8
发帖数: 3182 | 41 如果没人懂的话，老衲到愿意一试
第一个map 是将变量加入到一个hash/array/dict 里面。具体地讲，就是读取一个文件
，然后将文件的每一行先sort 一遍，然后uc 后添加到hash/array/dict 里面。
第二个map 其实就是将hash/array/dict 的每一个元素打印出来 |
|
l*******b
发帖数: 2586 | 42 C++写了个。。。大伙看吧，这里用的ruby的语法挺好懂呀
#include
#include
#include |
|
e***s
发帖数: 799 | 43 下面是我想到的，不知道对不对。
public static String segmentStringDP(String s, Set dict){
if(dict.contains(s)) return s;
int len = s.length();
int[] dp = new int[len];
for(int i = 0; i < len; i++)
{
for(int j = i; j < len; j++)
{
if(dict.contains(s.substring(i, j + 1)))
{
if(i == 0 || dp[i - 1] > 0)
dp[j] = Math.max(dp[j], j - i + 1);
... 阅读全帖 |
|
w****x
发帖数: 2483 | 44 class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::itera... 阅读全帖 |
|
g***9
发帖数: 159 | 45 写了一个能过大数据test的C++版本，回馈版友了
大家见笑了。。
单纯的建立图，再暴力BFS确实过不了大数据的，平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector & v) {
v.clear();
int n = s.s... 阅读全帖 |
|
i**********e
发帖数: 1145 | 46 word ladder II 有人过了 large tests 吗？
我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
整个程序不到50行。
基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多，所以性能上也没什么影响。
typedef unordered_multimap Map;
typedef pair PairIter;
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
Map map, map2;
queue q, q2;
q.push(start);
bool goal = false;
while (!q.empty()) {
... 阅读全帖 |
|
