d******e
发帖数: 164 | 1 贴个第一题，
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < w... 阅读全帖 |
|
f*******t
发帖数: 7549 | 2 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue<... 阅读全帖 |
|
w****x
发帖数: 2483 | 3 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 | 4 写了一个能过大数据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 | 5 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()) {
... 阅读全帖 |
|
d******e
发帖数: 164 | 6 贴个第一题，
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < w... 阅读全帖 |
|
f*******t
发帖数: 7549 | 7 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue<... 阅读全帖 |
|
l**b
发帖数: 457 | 8 来自主题: JobHunting版 - A家面试题 我当时和你一样，也讨论了100！的方法，说不行，太慢了。还是从string那里入手比
较好。
这个是我当时写的。DP那个方法刚刚写的，实在是很弱，所以如果错了，请轻拍。其他
的基本应该和面试的时候一样。反正写完他就让我把原来for loop是用string的length
做end point的，改成了用symbol最长的length。然后就说没问题了。
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
public class SymbolWord {
// Here is the max length of any symbol
public static final int MAX_SYMBOL_LENGTH = 2;
public String findLongestSymbolWord(List dict, Set
s... 阅读全帖 |
|
c********p
发帖数: 1969 | 9 我的跑不过的。。。
import java.util.*;
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
if(dict.isEmpty()){
return ret;
}
int len = 1;
int len2 = 0;
Queue q = new LinkedList();
... 阅读全帖 |
|
m**********e
发帖数: 22 | 10 DP:
public bool WordBreak(string str, Dictionary dict)
{
// f[i] is true when str[0,...,i] is word break;
// f[i] = true when f[k]==true and str[k+1,...,i] is a word
// or str[0,...,i] is a word
int n = str.Length;
bool[] allWords = new bool[n];
int i, j;
for (i = 0; i < n; ++i)
{
if (!allWords[i] && dict.ContainsKey(str.Substring(0, i + 1)
)... 阅读全帖 |
|
y***n
发帖数: 1594 | 11 Is this a DP problem, I tried a recursive solution which exceeds time limit
bool wordBreak(string s, unordered_set &dict) {
if(s.length()==0) return true;
bool foundBreak=false;
for(const string& current: dict){
if(s.compare(0, current.size(),current)==0){//find current
foundBreak= wordBreak(s.substr(current.size()), dict);
if(foundBreak)
break;
}
}
return foundBreak;
... 阅读全帖 |
|
b**m
发帖数: 1466 | 12 其实是前几天有人问那个(10)的简化版：
public class Solution {
public boolean wordBreak(String s, Set dict) {
if(s.length()==0){
return dict.contains(s);
}
boolean[] reachable = new boolean[s.length()+1];
reachable[0] = true;
for(int i=0;i
if(!reachable[i]){
continue;
}
for(int j=i+1;j<=s.length();j++){
String e = s.substring(i,j);
if(dict.con... 阅读全帖 |
|
z*********8
发帖数: 2070 | 13 这个case老是fail在这个test case：
Submission Result: Runtime Error
Last executed input: "aaaaaaa", ["aaaa","aa"]
谁能帮我看看？
public class Solution {
public boolean wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
boolean[] result = new boolean[s.length()+1];
result[0] = true;
int size = s.length();
for(int i=1; i <= size; ++i)
{
if(result[i] == false && di... 阅读全帖 |
|
s********u
发帖数: 1109 | 14 写了一下，觉得难点主要在回溯写这个path，如果维护不好，很容易出bug。
52ms通过。
class Solution {
public:
void backtracking( int end,const vector >&prev,const string
&s, vector &paths, string &path ){
if(end == -1){
paths.push_back(path);
return;
}
int prev_end;
string word;
const string local = path;
for(int i = 0; i < prev[end].size(); i++){
prev_end = prev[end][i];
... 阅读全帖 |
|
s*****n
发帖数: 994 | 15 dp + backtracking。 之前用了hashtable能过break word I，但是过不了II，可能是
string constructor太耗时了吧
class Solution {
public:
void backTracking (const string& s, vector >&prev, int index
, vector& output){
for (int i=0; i
int prev_index = prev[index][i];
vector prev_output(0);
if (prev_index != 0)
backTracking (s, prev, prev_index, prev_output);
else
prev_output = vector (1, "");
f... 阅读全帖 |
|
b***p
发帖数: 700 | 16 这个是python solution, worst case 是O(n^2). 比普通的Greedy Solution, 有两个
改进
1. 计算bit map of word, and AND operation to check if there is common char
2. 遍历是从最长的word开始
还有一个可以改进的地方是，利用元音字母，用word_len+vowel 作key，减少不必要
的compare
class DiffWordsMaxLenProduct:
def __init__(self):
# dict: word -> word char bit map
self.dict_word_bit = {}
# dict: word_len -> [word1, word2, word3...]
self.dict_word_len = {}
#
# compute the bit map of word char
#
def bit_word(self... 阅读全帖 |
|
a***e
发帖数: 413 | 17 再请问为啥下面这个程序就没有 Memory Limit Exceeded呢?我怎么觉得做法差不多，
只不过这个程序是从后往前做的？
vector wordBreak(string s, unordered_set &dict) {
int len = s.length();
vector dp(len + 1,false);
vector > dp2(len + 1,vector());
dp2[len].push_back("");
dp[len] = true;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
string str = s.substr(i,j - i + 1);
if (dict.... 阅读全帖 |
|
c******3
发帖数: 5 | 18 来自主题: JobHunting版 - M的面试题 def y(l, r):
if(l>r):
return 1
if(a[l]>-1):
return a[l]
i=l
while i<=r:
if(s[l:i+1] in dict):
a[i]=y(i+1, r)
if(a[i]==1):
return 1
i+=1
return 0
f=open('termDict.txt')
dict=set()
for line in f:
dict.add(line.strip())
s='ilovethisgame'
a=len(s)*[-1]
y(0, len(s)-1)
k=0
c=[]
for i in range(len(a)):
if(a[i]==1):
c.append(s[k:i+1])
k=i+1
print c |
|
h****n
发帖数: 1093 | 19 bool wordBreak(string s, unordered_set &dict) {
int N = s.size();
vector dp(N+1, false);
dp[0] = true;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= i; j++) {
if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
dp[i] = true;
break;
}
}
return dp[N];
} |
|
s******d
发帖数: 424 | 20 bool wordBreak(string s, unordered_set &dict) {
vector f(s.size() + 1, false);
f[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
} |
|
f****8
发帖数: 33 | 21 Thanks sharing!
The key point for this problem is that how to discover the neighbor nodes:
Find the neighbor nodes by constructing and searching them in the dict (for
each found node in last round, need 25 x strlen times string comparing),
rather than enumerating all the remain nodes in the dict (for each found
node in last round, need dict.size() comparing). |
|
t********n
发帖数: 611 | 22 还是不够快的问题，自己机器上测试结果正确，用了BFS and DFS，不知道还能怎样改
进，请牛牛们指教！
Python code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
for p in parents[end]:
... 阅读全帖 |
|
t********n
发帖数: 611 | 23 过了， 参考了某位高人的代码，每次找下级词汇前，把这一级从字典里删除，立刻快
了很多。
Code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
# print
# print "path at beginning:", path
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
... 阅读全帖 |
|
a*****u
发帖数: 1712 | 24 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 请转JobHunting: Uber面试分享
发信站: BBS 未名空间站 (Fri Oct 24 02:30:37 2014, 美东)
回报JobHunting版 分享一下Uber面试经历
朋友帮投简历。一星期后recruiter联系。Schedule和hiring manager电话聊。
和hiring manager电话聊得很好，项目背景很匹配。然后hm说本来要做一个小Project
然后再onsite，但是觉得我的背景可以不用做project了。于是直接给报销机票和酒店
让我onsite了。
onsite:
1. team的核心非manager人员(感觉要升成一个lead): 很简单的Fibonacci数列问题的
变体。A编码成1,B编码成2,Z编码成26。然后给一串数字问有多少种方法解码。比如32
只能解成CB, 26可以解成Z或者BF
2. team资深人员问，社交网络里，计算陌生人中共有朋友最多的一个人的办法。设计
存储，和计算流程。
3.... 阅读全帖 |
|
c*****e
发帖数: 3226 | 25 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.len... 阅读全帖 |
|
o******h
发帖数: 1142 | 26 public class Solution {
List> results;
List list;
Map> map;
public List> findLadders(String start, String end, Set<
String> dict) {
results= new ArrayList>();
if (dict.size() == 0)
return results;
int curr=1,next=0;
boolean found=false;
list = new LinkedList();
map = new HashMap阅读全帖 |
|
A**u
发帖数: 2458 | 27 谢谢你回复
我在string number_to_string(int x, const map& dict);
只用了 dict[index]方法，
看来dict[index]不是const 方法啊 |
|
d********g
发帖数: 10550 | 28 要生成一个给ORM用的arguments dict，需要从Excel raw data里判断对应position属
于哪个header并且要map给数据库里的field。dict comprehension加之前定义的两个
dict，只要一行就搞定了：
entry_dict = {ELEMENT_MAPPING[element_mapping[cell_count]]: cell.internal_
value for cell_count, cell in enumerate(row) if cell_count in element_
mapping} |
|
d********g
发帖数: 10550 | 29 要生成一个给ORM用的arguments dict，需要从Excel raw data里判断对应position属
于哪个header并且要map给数据库里的field。dict comprehension加之前定义的两个
dict，只要一行就搞定了：
entry_dict = {ELEMENT_MAPPING[element_mapping[cell_count]]: cell.internal_
value for cell_count, cell in enumerate(row) if cell_count in element_
mapping} |
|
y****e
发帖数: 1012 | 30 set term postscript eps color blacktext "Helvetica" 24
set output 'p1.eps'
set autoscale # scale axes automaticallyun
set label # remove any previous labels
set xtic auto # set xtics automatically
set ytic auto # set ytics automatically
set title "I/O Traffic"
set xlabel "Interval(5s)"
set ylabel "Data(KB)"
set key 0.01,10000
set xr [0:100]
set yr [0:10000]
plot "p1.tmp" using 1:2 title 'r0' ... 阅读全帖 |
|
h****h
发帖数: 123 | 31 MikTeX2.9+winedt 6
在winedt中更改Execution modes中ps2pdf的纸型会产生如下错误：
Command Line: ps2pdf.exe -sPAPERSIZE=letter "filename.ps"
Startup Folder: C:\Users\usr
Unknown paper size: ().
Error: /undefinedfilename in (letter)
Operand stack:
Execution stack:
%interp_exit .runexec2 --nostringval-- --nostringval-- --
nostringval-- 2 %stopped_push --nostringval-- --nostringval-- --
nostringval-- false 1 %stopped_push
Dictionary stack:
--dict:1157/1684(ro)(G)-- --dict:0/20(G)-- ... 阅读全帖 |
|
l*l
发帖数: 225 | 32 看到前面有不少讲cxterm的说明, 很好用, 但对于新手很难, 如下方法可以很快搞定:
其实cxterm运行只需要三个文件:
1) cxterm 可执行文件
2) ~/.Xdefaults 输入法定位文件
3) path/to/dict/gb 输入法table文件
因此你只需要从朋友或者XX那里考备这三个文件(第三个是目录)然后对~/.Xdefaults
稍微修改就OK了.
cxterm 只要是同一种UNIX/Linux就可以了, 例如hp-10.2 可以兼容hpux.
将之放在自己的 ~/bin/里, 别忘记 chmod a+x cxterm !!!
~/.Xdefaults当然在自己目录里了, 修改这个地方:
cxterm*hanziInputDir: /home/people/llu/dict/gb
上面是我的例子
path/to/dict/gb 里应该放table 文件, 应该有如下文件:
CCDOSPY.cit English.cit PY.cit QianMa.cit TeleCode.cit
CTLau.cit HIRAGANA.cit P |
|
m*******t
发帖数: 482 | 33 方韩演义第一回
韩寒走进方坑
世上最有趣的莫过于看人掐架。要不马路边出点儿事，总会有一大群人围观。不是有句
话吗？看人掐，爽；看名人掐，更爽；看大名人掐，爽之又爽。这不，大过年的，两位
当世中国的绝顶武林高手：天才少年韩寒和打假斗士方舟子，顶着满天飞舞的雪花，在
网络之颠拳脚相交。
本来，这是一亩“麦田”引发的血案。估计方舟子最初和我等芸芸众生一样，也就一路
旁看热闹，间或打上两记太平拳的脚色。所以说话也没那么严谨。最明显的失误就是：
“惊讶地发现韩寒把从2006年12月13日到2007年9月18日长达9个多月的博客文章全删了
。所以就在微博上感叹了一句“一边重金悬赏，一边销毁证据，更让人觉得悬赏没诚意
。”
另外就是追究韩寒的两千万悬赏告示。直到现在，我都认为这是老方吹毛求疵。韩寒的
文风就是要给人一种天花乱坠的感觉，不可能过份严谨。他的本意还是应该正面理解：
只要抓住有谁代笔，自己甘愿认罚。
不过，老方没料到自己裤带上记着块名人腰牌，一说话就会被大家伙盯着。果然，就在
韩寒三拳两脚把麦田打爬下后，他小人家得意洋洋，开始单挑方舟子：“这次正好方舟
子老师也加入了进来，我正好一起做个总... 阅读全帖 |
|
|
m*******t
发帖数: 482 | 35 方韩演义第一回
韩寒走进方坑
世上最有趣的莫过于看人掐架。要不马路边出点儿事，总会有一大群人围观。不是有句
话吗？看人掐，爽；看名人掐，更爽；看大名人掐，爽之又爽。这不，大过年的，两位
当世中国的绝顶武林高手：天才少年韩寒和打假斗士方舟子，顶着满天飞舞的雪花，在
网络之颠拳脚相交。
本来，这是一亩“麦田”引发的血案。估计方舟子最初和我等芸芸众生一样，也就一路
旁看热闹，间或打上两记太平拳的脚色。所以说话也没那么严谨。最明显的失误就是：
“惊讶地发现韩寒把从2006年12月13日到2007年9月18日长达9个多月的博客文章全删了
。所以就在微博上感叹了一句“一边重金悬赏，一边销毁证据，更让人觉得悬赏没诚意
。”
另外就是追究韩寒的两千万悬赏告示。直到现在，我都认为这是老方吹毛求疵。韩寒的
文风就是要给人一种天花乱坠的感觉，不可能过份严谨。他的本意还是应该正面理解：
只要抓住有谁代笔，自己甘愿认罚。
不过，老方没料到自己裤带上记着块名人腰牌，一说话就会被大家伙盯着。果然，就在
韩寒三拳两脚把麦田打爬下后，他小人家得意洋洋，开始单挑方舟子：“这次正好方舟
子老师也加入了进来，我正好一起做个总... 阅读全帖 |
|
w****y
发帖数: 2952 | 36 方对这点实际已经认错了。
“然后有读者以及新浪博客的编辑纠正说，这些博客文章是在结集成《杂的文》时删掉
的。现在韩寒也是这么解释的。这个解释虽然与《杂的文》序言所说的矛盾（“书是必
须要出版的。里面的文章，大多数我都发表过在我的博客里。不想花20元买书的读者可
以上网花20元的电费和上网费把文章全部浏览了。”），但也说得过去。我由于不熟悉
韩寒的文章和事迹的想当然感叹，澄清或借此批我一顿，都无不可。”
看看韩寒怎么对肘子泼脏水的。
方舟子先生说，我有一篇回应郑钧的文章在郑钧发表文章之前就发表了。这个有问
题。。。。
肘子什么时候说过这句话？
还有这个：
“有一个网友发了一条微博，内容是：用DICT和SPSS测试了韩寒和路金波在2008到
2011年间的新浪微博文章，结论是，不能证明二人文章有显著不同。不过，这一结论除
了说明软件需要改进之外，不能说明任何别的。抛砖引玉，博君一笑，望有志做文本分
析的同志再接再励。
方舟子先生转发了这个微博，说，这个研究有意思，如果能对比一些人，就更有说
服力了。方舟子先生的意思很明显：一个软件证明，我和路金波的文章差不多，所以暗
示其实我的枪手... 阅读全帖 |
|
l****u
发帖数: 3130 | 37 文坛骂战成就广告植入!韩寒在博客中的一句“方舟子先生，昨天晚上的巴萨对皇马的
比赛你是对着你家的微波炉看的吗”，竟然给格兰仕一款可以看电视的微波炉带来了意
想不到的商机。近日，一些淘宝卖家修改了这款微波炉的介绍，特别标明是“方舟子用
来看电视球赛的微波炉”。对此，很多网友戏称格兰仕是此次文坛骂战的“最佳广告植
入”。
此前，方舟子转发了一条微博，大意是有网友用DICT这个文本分析软件测试了韩寒
和路金波在2008年到2011年间的新浪博客文章，结论是“不能证明二人文章有显著不同
”。韩寒则于19日在博客中称“Dict是一个英文文本分析软件，方舟子身为一个科普人
士，居然很认可用英文文本软件来分析中文，方舟子先生，昨天晚上的巴萨对皇马的比
赛你是对着你家的微波炉看的吗?”
没想到韩寒的一句戏言竟引出了较真的网友，有网友向韩寒爆料，格兰仕有款微波
炉确实可以看电视。20日，韩寒在新的博客中称：“这件事情给了我一个惨痛的教训：
话不能说得太满太绝对，写文章的时候还是要更加的严谨。因为根据网友提供的资料，
我查实——真的有微波炉是可以看电视的，型号是格兰仕G80WMSPP-N5”。随后，韩寒
... 阅读全帖 |
|
|
c*******a
发帖数: 1879 | 39 dict = {"country": ["Brazil", "Russia", "India", "China", "South Africa"],
"capital": ["Brasilia", "Moscow", "New Dehli", "Beijing", "Pretoria"],
"area": [8.516, 17.10, 3.286, 9.597, 1.221],
"population": [200.4, 143.5, 1252, 1357, 52.98] }
import pandas as pd
brics = pd.DataFrame(dict)
print(brics) |
|
i*****8
发帖数: 3942 | 40 可以下载n多字典
推荐google dict在线用
Oxford dict 离线用 200+mb |
|
i******s
发帖数: 301 | 41 就是有一个字典dict，里面有若干字符串。现在输入一个字符串str, 将str分成若干个
子串，要求每个子串都在dict中，问这样的切分方法有几种？ |
|
U*********y
发帖数: 54 | 42 题目: transform one word into another, 1 letter at a time, each step must
be
in the dictionary.
CareerCup的BFS解看起来很麻烦, 既然没要求最短距离转换或得出所有可能转换, 就写
了个DFS+backtracking的解, 请指教!
[code]
unordered_set dict; //dictionary
bool validTran(string &a, string &b, int d, unordered_map
string> &path) {
if(a == b) {
return 1;
}
if(d == b.size()) return 0;
if(a[d] == b[d]) { //no change at this position is needed
return validTran(a, b, d+1, path);
}
for(char ... 阅读全帖 |
|
q*****n
发帖数: 311 | 43 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
的句子中插入空格，使它变成合法的句子。
他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
你的想法写代码吧，上来就没头没尾写了个
int len = strs.lenth
for (int i=0; i
for (int j=0;j<..;j++) {
}
}
... 阅读全帖 |
|
q*****n
发帖数: 311 | 44 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
的句子中插入空格，使它变成合法的句子。
他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
你的想法写代码吧，上来就没头没尾写了个
int len = strs.lenth
for (int i=0; i
for (int j=0;j<..;j++) {
}
}
... 阅读全帖 |
|
e****e
发帖数: 418 | 45 I'm with you. I don't think prefix tree(trie) is needed. Here is my code.
String[] pad = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs
", "tuv", "wxyz"};
List words = new ArrayList();
Set dict = // Preloaded.
public void determineWord(String word, String remaining) {
if ( "".equals( remaining ) ) {
if(dict.contains( word )
words.add( word );
return;
}
int digit = remaining.... 阅读全帖 |
|
p*****2
发帖数: 21240 | 46 终于写完了，大牛们见笑了。
require 'set'
$dict=Set.new ['fox','fog','dog']
def indict?(word)
$dict.include? word
end
def transfer(first,last)
queue=[first]
hash={first=>0}
until queue.empty?
word=queue.shift
step=hash[word]
(0...word.length).each do |i|
curr=word[i]
('a'..'z').each do |c|
word[i]=c
if(word==last)
return step+1
elsif indict?(word) && !hash[word]
hash[word]=step+1
queue<<(String::new word)
end
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 47 require 'set'
$dict=Set.new ['check','out','checkout']
def indict?(word)
$dict.include? word
end
def min_words(str)
n=str.length
dp=[-1]*(n+1)
dp[n]=0
(n-1).downto(0).each do |i|
min=-1
(1..n-i).each do |j|
if indict?(str[i,j]) && dp[i+j]>=0 && (min==-1 || dp[i+j]+1
min=dp[i+j]+1
end
end
dp[i]=min
end
dp[0]
end
p min_words('checkout') |
|
p*****2
发帖数: 21240 | 48 def segmentString(s:String, dict:Set[String]):String={
val len=s.length()
val dp=Array.ofDim[Int](len+1,2)
(0 until len).reverse.foreach{i=>
(i+1 to len).foreach{j=>
if(dict.contains(s.substring(i,j)) &&
(j==len || dp(j)(0)>0) && (dp(i)(0)==0 || dp(j)(0)+1
{
dp(i)(0)=dp(j)(0)+1
dp(i)(1)=j
}
}
}
var ab=ArrayBuffer[String]()
if(dp(0)(0)>0)
{
var i=0
while(i!=len)
{
... 阅读全帖 |
|
