b****g
发帖数: 192 | 1 Leetcode的Word Ladder那道题，
code很简单，但是有个地方我不明白：
if(dict.find(s_new) != dict.end() && visited[s_new] != true)
这一行，如果把 && 左右互换，就超时。大家可以去试试，是Leetcode的127题。
我试了一小时才发现这里超时，于是改过来了。
我猜测是因为先判断了一个耗时少的条件为false，于是另一个耗时长的就不用判断了？
所以调换以后才超时。
C++的if语句先判断哪一个？&&前的还是后的？
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict)
{
// Start typing your C/C++ solution below
// DO NOT write int main() function
queue q;
queue level;
q.push(start);
level.push(1);
map visited;
visited[start] = true;
while(!q.empty())
{
string s = q.front();
q.pop();
int lev = level.front();
level.pop();
if(lev>1 && s==end)
return lev;
for(int i=0; i
{
string s_new(s);
for(int j=0; j<26; j++)
{
char c = 'a'+j;
if(c!=s.at(i))
{
s_new[i] = c;
//Time Limit Exceeded
/*if(visited[s_new] != true
&& dict.find(s_new) != dict.end())*/
if(dict.find(s_new) != dict.end()
&& visited[s_new] != true)
{
q.push(s_new);
level.push(lev+1);
visited[s_new] = true;
}
}
}
}
}
return 0;
}
}; |
b****g
发帖数: 192 | 2 或者把那一块判断语句分开，变成下面的样子，也超时。
if(visited[s_new] == true)
{
continue;
}
else
{
visited[s_new] = true;
}
if(dict.find(s_new) == dict.end())
{
continue;
}
else
{
q.push(s_new);
level.push(lev+1);
}
了？
【在 b****g 的大作中提到】
: Leetcode的Word Ladder那道题，
: code很简单，但是有个地方我不明白：
: if(dict.find(s_new) != dict.end() && visited[s_new] != true)
: 这一行，如果把 && 左右互换，就超时。大家可以去试试，是Leetcode的127题。
: 我试了一小时才发现这里超时，于是改过来了。
: 我猜测是因为先判断了一个耗时少的条件为false，于是另一个耗时长的就不用判断了？
: 所以调换以后才超时。
: C++的if语句先判断哪一个？&&前的还是后的？
: class Solution {
: public:
|
A*********l
发帖数: 2005 | 3 visited[s_new]:
如果 visited.find[s_new] 不存在的话，它会在map里加入这个值。
所以如果你先判断这个的话，很有可能会多出很多map insersion。
了？
【在 b****g 的大作中提到】
: Leetcode的Word Ladder那道题，
: code很简单，但是有个地方我不明白：
: if(dict.find(s_new) != dict.end() && visited[s_new] != true)
: 这一行，如果把 && 左右互换，就超时。大家可以去试试，是Leetcode的127题。
: 我试了一小时才发现这里超时，于是改过来了。
: 我猜测是因为先判断了一个耗时少的条件为false，于是另一个耗时长的就不用判断了？
: 所以调换以后才超时。
: C++的if语句先判断哪一个？&&前的还是后的？
: class Solution {
: public:
|
a***n
发帖数: 538 | |
b****g
发帖数: 192 | 5 你是说if里面的那个visited[s_new] != true 会导致很多insertion吗？还是说下面的
visited[s_new] = true 会导致很多insertion？
【在 A*********l 的大作中提到】
: visited[s_new]:
: 如果 visited.find[s_new] 不存在的话，它会在map里加入这个值。
: 所以如果你先判断这个的话，很有可能会多出很多map insersion。
:
: 了？
|
b****g
发帖数: 192 | 6 我怎么感觉dict比visited更耗时间呢？因为我看leetcode的一个test case里在dict放
了3000个词，而visited顶多就几百个词而已。
【在 a***n 的大作中提到】
: c++先左边的。
|
t****t
发帖数: 387 | 7 []operator will insert if not existed
【在 b****g 的大作中提到】
: 你是说if里面的那个visited[s_new] != true 会导致很多insertion吗？还是说下面的
: visited[s_new] = true 会导致很多insertion？
|
b****g
发帖数: 192 | 8 多谢，我刚才自己写了map的 [ ] 操作然后debug，终于明白你的意思了。多谢！
【在 t****t 的大作中提到】
: []operator will insert if not existed
|
A*********l
发帖数: 2005 | 9 是说if里面的那个visited[s_new] != true
【在 b****g 的大作中提到】
: 你是说if里面的那个visited[s_new] != true 会导致很多insertion吗？还是说下面的
: visited[s_new] = true 会导致很多insertion？
|
h**6
发帖数: 4160 | |
l***i
发帖数: 1309 | 11 好像map是count，不是at。另外lz是不是没上过编程课？ |
