s*****l
发帖数: 45 | 1 实在没想出啥好的解法，来请假大侠们一下。。
Three allowed operations: delete a character, insert a character, replace a
character.
Now given two words - word1 and word2 - find
the minimum number of steps required to convert word1 to word2 |
|
k****r
发帖数: 807 | 2 目测的话，我想用recursive＋backtrack
分情况的, 我简单写了下，请指正
bool matchwords(char* word1, char* word2, int index1, int index2) {
if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
else {
if (word2[index2] == '*') {
if (matchwords(word1, word2, index1+1, index2+1)) return true;
else if (matchwords(word1, word2, index1+1, index2)) return true;
else if (word2[index2] == '?') {
return matchwords(word1, word2, index1+1, index2+1);
else {
... 阅读全帖 |
|
l*****o
发帖数: 214 | 3 一点想法，不知到对不对：
用doubly linked list
step 1. scan text, if in the target word set, add to doubly linked list,
until the doubly linked list has all the target words: you get [word1, word1
, word2, word1, word1, word3]
step 2. from the end of the linked list, go backwards, until find all the
words in target word set, remove the words before, and the result is a
probably shorter list with first element A: you get [word2, word1, word1,
word3], and record the span
step 3. keep scanning the text, push wor... 阅读全帖 |
|
t****a
发帖数: 1212 | 4 楼主说的这题实际上是第127题
刚做了个clojure的解法，比java要短小很多。
可惜不能在leetcode上测试大数据，真心希望leetcode支持C/C++/Java以外的语言。
(defn word-map [dict]
(let [g (group-by first (for [word1 dict
word2 dict
:let [wd (word-dist word1 word2)]
:when (== wd 1)]
[word1 word2]))
ks (keys g)
vs (map (partial mapv second) (vals g))]
(zipmap ks vs)))
(defn word-dist [word1 word2]
(reduce + (map (f... 阅读全帖 |
|
b***p
发帖数: 700 | 5 这个是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... 阅读全帖 |
|
f**********t
发帖数: 1001 | 6 // Find the minimum distance between two words in a list. The words can
repeat.
int EditDistance(string &word1, string &word2) {
if (word1.empty()) {
return word2.size();
} else if (word2.empty()) {
return word1.size();
}
vector vi(word1.size() + 1);
int n(0);
generate(vi.begin(), vi.end(), [&] { return n++; });
for (int i = 0; i < word2.size(); ++i) {
int pre = vi[0];
vi[0] = i + 1;
for (size_t k = 0; k < word1.size(); ++k) {
int temp = vi[k + 1];
... 阅读全帖 |
|
l*********s
发帖数: 5409 | 7 I am having some very weird bug while trying to write a macro that can
expend the short hand notion like var1--var11 used in SAS.
The "shorthand" macro works fine on its own, but fails to work when called
by the "formula" macro. The error message seems to say that "the set
statement in the data step is not valid or not in proper order", what's
going on?
Many thanks!
////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////... 阅读全帖 |
|
o****o
发帖数: 8077 | 8 dude, you put two %% in this line:
%let word2 = %scan(%bquote(%substr(%bquote(&covars.),%EVAL(&i.+1))),1);
---> %%put word2 = &word2.;
%let pos2 = %EVAL(%index(%bquote(&covars.), &word2.)+%length(&word2.) );
remove one % and you are all set |
|
j***u
发帖数: 16 | 9 如果按inverted index方法
DocID_1 = { word1,word2,word3}
DocID_2 = { word2,word3}
DocID_3 = { word1,word3,word4}
那么,Hash链表
H(word1)-->DocID_1-->DocID_3
H(word2)-->DocID_1-->DocID_2
H(word3)-->DocID_1-->DocID_2-->DocID_3
如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1}
就变成求所有查询word的hash链的交集.
如果是这样的话，问题可以先简化找2个链表的重复数据，
然后根据得到的重复数据集合，和下一个链表比较 找交集 |
|
w******g
发帖数: 189 | 10 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word... 阅读全帖 |
|
w******g
发帖数: 189 | 11 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word... 阅读全帖 |
|
y**********a
发帖数: 824 | 12 class MinDist{
Map dist;
String separator;
int minDist(String s1, String s2, Map>map) {
dist=new HashMap<>();
Listl1,l2;
if ((l1=map.get(s1))==null||(l2=map.get(s2))==null) return -1;
int rel=Integer.MAX_VALUE;
for(int i1=0,i2=0;i1
int v1=l1.get(i1),v2=l2.get(i2),dif=v1-v2;
rel=Math.min(rel,Math.abs(dif));
if (rel==1) return 0;
el... 阅读全帖 |
|
r*******y
发帖数: 290 | 13 std::ifstream ifs;
ifs.open("file_name");
char line[256];
std::string word1, word2;
while(ifs.getline(line, 256, ',') {
word1 = line;
ifs.getline(line, 256);
word2 = line;
std::cout << "word1 is" << word1 << "\t"
<< "word2 is" << word2 <
} |
|
j***u
发帖数: 16 | 14 就是
i.e. m = 3 = word1 + word2 + word3,
1>先求 union(m) = H(word1) + H(word2) + H(word3) 链表里所以doc_id 数目（有重
复)
这个union 包括 同时有3个word的doc_id, 也有只有1个或2个 的doc_id,
2>求交集 intersect(p = m) = H(word1) 交 H(word2) 交 H(word3), 得到的 集合就是
同时含有3个word的doc_id 数目,
3>结果 sum (p < m) = union(m) - 3 * intersect( p = m) (去掉所有 同时含3个
word的doc_id) |
|
T*****u
发帖数: 7103 | 15 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
|
T*****u
发帖数: 7103 | 16 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
|
f**********t
发帖数: 1001 | 17 #include "common.h"
class WordsDistance {
vector _array;
public:
WordsDistance(initializer_list l) : _array(l) {}
int dist(string word1, string word2) {
int res = INT_MAX;
size_t left = 0;
while (left < _array.size() && _array[left] != word1 && _array[left] !=
word2) {
++left;
}
if (left == _array.size()) {
return res;
}
size_t right = left + 1;
while (right < _array.size()) {
if (_array[right] == _array[left]) {
l... 阅读全帖 |
|
l*******b
发帖数: 2586 | 18 C++写了个。。。大伙看吧，这里用的ruby的语法挺好懂呀
#include
#include
#include |
|
r*****n
发帖数: 2 | 19 onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
是fresh master.
两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
解题意。
有一种新型存储设备，特点是：
1. 价格贵，稳定性高
2. 可读写，但写入的内容不能修改
如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
呢。
4轮Onsite 3个印度人一个欧洲人。都是从简单的题开始，不停改改改。都讨论了项目
经验，还问得很细。写完代码都是要照相的，我有个题是开始写得挺干净，后来条件加
加加就改花了，然后interviewer掏出手机拍了一张。。我觉得是不是可以在写完第一
版之后就请他拍一张先。。。
1.一个binary search变体。 写完之后开始抠代码，说如果把终止条件从low<=high 改
成low阅读全帖 |
|
h**o
发帖数: 548 | 20 两题有什么本质区别使得你们会想到一题用DP, 另一题用BFS?
1. Edit Distance：
-----------------
Given two words word1 and word2, find the minimum number of steps required
to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
2. Word Ladder
-----------------
Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, such that:
O... 阅读全帖 |
|
J**9
发帖数: 835 | 21 Problem at
http://discuss.leetcode.com/questions/765/word-break
This does not seem to be a DP problem, just do it in a straightforward way.
Here's my implementation in C. Any issue?
Thanks.
//===========================================================
#include
#include
#include
#include
#include
/**
* Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more
* dictionary w... 阅读全帖 |
|
l****1
发帖数: 33 | 22 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
并且满足word1和word2没有common letter. |
|
h****2
发帖数: 46 | 23 昨天电面，两道题 不算难，求好运~~
1. Given a sorted array of floats, find the index of the number closest to x:
Example: {1.2, 2.5, 9.3} x = 5, return 1
2. Of the pairs of words in the dictionary that have no letters in common,
find one that maximizes the product of the words' lengths.
cat
dog
feed
pull
space
pair = word1, word2
length = word1.size() * word2.size() |
|
F********g
发帖数: 475 | 24 unsigned int calculate_1X_LO_period(unsigned int input_freq_khz, unsigned
int if_freq_khz)
{
unsigned int
remainder;
unsigned int temp_result;
unsigned int divisor;
DISABLE_TMR1_INT;
DISABLE_TMR4_INT;
DISABLE_SPI1_INT;
dividend.all=32000;
divisor=input_freq_khz+if_freq_khz;
if (0==divisor)
... 阅读全帖 |
|
R*****n
发帖数: 8658 | 25 \begin{center}
\epsfysize = 0.5 in
\epsfxsize = 1.2 in
\epsfbox{word2.eps}
\end{center}
or try
\begin{figure}
\centerline{\psfig{figure=word2.eps,height=1.0cm}}
\caption{``Peer'' relationship.................}
\label{fig:1}
\end{figure} |
|
x********v
发帖数: 2535 | 26 http://www.1518.com/s?st=2&word1=%C5%ED&word2=%D3%C0%C4%EA
彭永年姓名测吉凶
彭永年的姓名三才配置为:火金木（凶）
它具有如下数理诱导力，据此会对人生产生一定的影响。
命运被压抑,不易成功,易招失败,易损害呼吸器官而生疾病。
1、总论:不但工作及事业上无法顺利成功,且内外不和,心情苦闷,生活不能安定,易招失
意,失败、家庭失和等情事,应谨慎为人处事,若天运五行属土,一生尚能小成功。
2、性格:虽有坚忍的个性,不怕失败或打击,性急而口齿灵利,容易得罪人而引起反感,应
注意成长时期流于问题少年,卷入朋友是非或法律纠纷,人生的考验较多。
3、意志:意志不够坚定,思想变化万千,但尚能忍受艰苦与突来的打击,痛苦度一生。
4、事业:所谋所做之事表面平稳,其实内面隐藏著随时发生的祸害,应选择人事问题单纯
的小本生意。
5、家庭:家内难和睦,应多忍让免造成婚姻危机,子女亦容易反感,早为独立打算。
6、婚姻:男娶懦弱固执之妻,婚后感情难和睦;女嫁好胜好强之夫,婚后常有争吵。
7、子女:女孩多于男孩,聪明但有反叛性质。
8、社交:个性顽强固执,争勇... 阅读全帖 |
|
b******g
发帖数: 1721 | 27 来自主题: JobHunting版 - 请教一道题 collect letters to set1 from word1
collect letters to set2 from word2
if set1==set2, then anagram ; otherwise not. |
|
z*******y
发帖数: 578 | 28 这个是Dynamic Programming
自己想还是挺难想的
搜一下 Dynamic Programming Edit Distance |
|
d*******8
发帖数: 785 | 29 在Converting的过程中要不要保持这个word还是个词典中的单词？
如果是那样的话，好像只有对相差一个Char的单词网络中做BFS
如果要求Operations最少的话，比如insertion, replacement, deletion都有各自
的Penalty的话，就是sequence alignment，DP就可以了吧。
a |
|
|
g*******y
发帖数: 1930 | 31 这个是算法课动态规划那部分比较简单的作业题吧
replace a |
|
j*****s
发帖数: 189 | 32 用DP好一些
for(int i = 1 ; i< n1 + 1; ++i){
for (int j = 1; j < n2 + 1; ++j){
if (word1[i - 1] == word2[j - 1])
{
dist[i][j] = dist[i - 1][j - 1];
}
else{
dist[i][j] = min(dist[i - 1][j - 1], dist[i - 1][j],
dist[i][j - 1]) + 1;
}
}
} |
|
h********g
发帖数: 496 | 33 面经就发在同一个thread吧
这是个back to back两小时的面试，两轮的流程都是先问了些简历的东西，然后对方介
绍下自己的项目，然后coding。
1. coding题很简单，可能是半research职位，所以coding要求不高？
1) 给一堆document, d1, d2, d3...dn，要求给出 reverse-index: <{word1,
frequence1}, {word2, frequence2} ...>
---document很多，reverse index没法都放在内存里头，所以讨论了下如何partition
---还讨论了下不同document的类型，word之间的delimter可能不同，document预处理等
2) find lowest common parent for two nodes in the tree.
follow question: what's your test cases?
3) print tree nodes in level order
2. machine learning 的题目： 你有很多customer... 阅读全帖 |
|
P****d
发帖数: 137 | 34 这个题是C特有的吗？strlen是求字符串长度吗？如果是java是不是直接遍历所有的元
素用word1.length()*word2.length()看最后哪个乘机大就行了是么？有没有共同元素
对求string长度有什么影响吗？ |
|
J*****n
发帖数: 137 | 35 应该是pull * space吧？
最直观的话应该两层loop，然后问题转换成找 common letter of two words. 记录max
length, word1, word2.
至于找common，应该好多方法，可以new int[] 来记录字符出现次数，或者hashSet 判
断contains char.
复杂度这样看应该是O(n^3).
我这样对不对？有没有好的方法呢？ |
|
h****2
发帖数: 46 | 36 喔喔，哈哈
word1 word2 仅仅是指代两个单词，没有序号的意思哈
表达不清，不好意思 |
|
m*****k
发帖数: 731 | 37 1. compute each word's binary representation in 26 bits and save as an int,
for example, "a" becomes 10000...., which is 1*2^25
"abc" becomes 1110000.... , which is 7 * 2^23
2. construct a Hashmap by
scan the words in the dictionary, if key already exists, update the word if
it is longer.
result=[maximum,"",""];
3. with all the keys in the map,
for (key1 in map.keys):
for (key2 in map.keys):
if (key1 & key2 ==0):
x = word1.length()*words.length()
i... 阅读全帖 |
|
Z**********4
发帖数: 528 | 38 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
|
c*******r
发帖数: 610 | 39 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MIN;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？ |
|
Z**********4
发帖数: 528 | 40 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。 |
|
|
Z**********4
发帖数: 528 | 42 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
|
c*******r
发帖数: 610 | 43 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MAX;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？ |
|
Z**********4
发帖数: 528 | 44 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。 |
|
|
s*******m
发帖数: 228 | 46 怎么写这么长
int index1 = -1;
int index2 = -1;
int min_dist = INT_MAX;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
应该很简单的 |
|
|
f*****r
发帖数: 229 | 48 I think about how to use cache line. For example, if the L1 cache line is 4
words (16 bytes), we move word1 to register a, then move word2 to reg b, then
move word3 to reg c, then move word4 to reg d; after those operations, move
rega to dest1, regb to dest2, etc. Is it faster?
Another possible way is using MMX mode. In each operation you can operate 16
bytes (or more). maybe MMX2 can give you better choice. But I guess that this
may be only good for bulk data copy, since mode switch has some ov |
|
r***e
发帖数: 31 | 49 Maybe I did not describe the problem clearly, the attribute A1 is a string,
how can I find all the records that have the value in A1 has the format "word1
word2 word3".
the |
|
b***k
发帖数: 39 | 50 打开一个word文件时,出了这么句话
This file needs to be opened by the word2.x for windows text converter,
which may pose a secruity risk if the file you are opening is a malicious
files, choose yes to open this file only if you are sure it is from a
trusted source.
我点yes后,word就是sent erro report然后就关掉了,哪位知道这是怎么回事,多谢. |
|
