b***i
发帖数: 3043 | 1 在VS2015花40多秒，如果wordList有2455个4个字母构成的字符串。但是在leetcode上
只要半秒。为啥呢？
size_t distance(string a, string b) {
size_t c = 0;
for (size_t i = 0;i
if (a[i] != b[i])
if (c++==1)
return c;
return c;
}
size_t size = wordList.size();
size_t from = SIZE_MAX;
size_t dest = SIZE_MAX;
vector> closest; // stores the list of list of shortest
nodes
closest.reserve(size);
for (size_t i = 0;i
vector tmpv;
tmpv.reserve(size);
for (size_t j = 0;j
size_t tmp = distance(wordList[i], wordList[j]);
if (tmp == 1)
tmpv.push_back(j);
}
closest.push_back(tmpv);
if (distance(wordList[i], beginWord) == 0)
from = i;
else if (distance(wordList[i], endWord) == 0)
dest = i;
}
vector> result;
if (dest == SIZE_MAX || from < size - 1)
return result; |
C*****n
发帖数: 1872 | 2 在vs里面是debug mode？
感觉debug mode也没这么慢啊
你是不是有啥循环打印之类的code没贴？
【在 b***i 的大作中提到】
: 在VS2015花40多秒，如果wordList有2455个4个字母构成的字符串。但是在leetcode上
: 只要半秒。为啥呢？
: size_t distance(string a, string b) {
: size_t c = 0;
: for (size_t i = 0;i: if (a[i] != b[i])
: if (c++==1)
: return c;
: return c;
: }
|
s******u
发帖数: 501 | 3 size_t distance(string a, string b)
传const &，不要直接传值 |
b**a
发帖数: 1118 | 4 Run it on another machine and see what happens. |
c******3
发帖数: 6509 | 5 我只是进来赞代码效率的
多级if嵌套，可以有效废掉现代CPU的Piepline，获得较好的stall性能
而且怕速度太快，wordList中任何一对字符串都要反复求distance，把计算强度从O(N)
提升到O(N^2）才是王道
怕stack用不完，所以传值而不是传引用(指针） |
b***i
发帖数: 3043 | 6 改了之后，果然快了，到7.5秒了。
看来g++自动优化了。然后，把O2加上，50毫秒了。这么说leetcode还慢了
【在 s******u 的大作中提到】
: size_t distance(string a, string b)
: 传const &，不要直接传值
|
b***i
发帖数: 3043 | 7 什么叫N^2?
N)
【在 c******3 的大作中提到】
: 我只是进来赞代码效率的
: 多级if嵌套，可以有效废掉现代CPU的Piepline，获得较好的stall性能
: 而且怕速度太快，wordList中任何一对字符串都要反复求distance，把计算强度从O(N)
: 提升到O(N^2）才是王道
: 怕stack用不完，所以传值而不是传引用(指针）
|
c******3
发帖数: 6509 | 8 N^2 = N*N
【在 b***i 的大作中提到】
: 什么叫N^2?
:
: N)
|
b***i
发帖数: 3043 | 9 N个字符串要对每个字符串做一个vector,记录里它最近的字符串。比如
1: 3, 4, 8, 10, 11
2: 3, 5, 7
3: 2, ....
那还能做N次就出来？
【在 c******3 的大作中提到】
: N^2 = N*N
|
A*******e
发帖数: 2419 | 10 机器不一样，怎么能比？
【在 b***i 的大作中提到】
: 改了之后，果然快了，到7.5秒了。
: 看来g++自动优化了。然后，把O2加上，50毫秒了。这么说leetcode还慢了
|
|
|
A*******e
发帖数: 2419 | 11 你做的是这道？
https://leetcode.com/problems/word-ladder/
【在 b***i 的大作中提到】
: N个字符串要对每个字符串做一个vector,记录里它最近的字符串。比如
: 1: 3, 4, 8, 10, 11
: 2: 3, 5, 7
: 3: 2, ....
: 那还能做N次就出来？
|
b***i
发帖数: 3043 | |
A*******e
发帖数: 2419 | 13 看不懂你的代码。加点注释？ 计算distance意义何在？你只需要找相邻关系啊。
另外题目也没描述清楚。是假定所有单词等长？
【在 b***i 的大作中提到】
: 对
|
b***i
发帖数: 3043 | 14 相邻关系怎么找呢？
【在 A*******e 的大作中提到】
: 看不懂你的代码。加点注释？ 计算distance意义何在？你只需要找相邻关系啊。
: 另外题目也没描述清楚。是假定所有单词等长？
|
A*******e
发帖数: 2419 | 15 假定字典里都是等长单词。两两比较，只有恰好一个字母不同的两个单词相邻。
建立相邻关系后BFS就行了。
【在 b***i 的大作中提到】
: 相邻关系怎么找呢？
|
b***i
发帖数: 3043 | 16 怎么建立相邻关系？
【在 A*******e 的大作中提到】
: 假定字典里都是等长单词。两两比较，只有恰好一个字母不同的两个单词相邻。
: 建立相邻关系后BFS就行了。
|
g****t
发帖数: 31659 | 17 Sort就可以了吧，当作26进制数。
: 怎么建立相邻关系？
【在 b***i 的大作中提到】
: 怎么建立相邻关系？
|
b***i
发帖数: 3043 | 18 题目指的是，两个单词如果只有一个字母不一样叫相邻
【在 g****t 的大作中提到】
: Sort就可以了吧，当作26进制数。
:
:
: 怎么建立相邻关系？
:
|
g****t
发帖数: 31659 | 19 Hamming distance找最小路径？是travail sales man类似的吧。
应该容易查到经典算法。自己开发算法没多大意义。
: 题目指的是，两个单词如果只有一个字母不一样叫相邻
【在 b***i 的大作中提到】
: 题目指的是，两个单词如果只有一个字母不一样叫相邻
|
b***i
发帖数: 3043 | 20 原题很简单，还没有到最小路径的地步。就是一堆字符串，先要算出哪些字符串只有一
个字母的差别。所以我数任意两个字符串有几个字母有差别。但是有人问为什么要数啊
，难道不是先建立一个相邻关系的矩阵就行了吗？问题是怎么建立相邻关系呢？
【在 g****t 的大作中提到】
: Hamming distance找最小路径？是travail sales man类似的吧。
: 应该容易查到经典算法。自己开发算法没多大意义。
:
:
: 题目指的是，两个单词如果只有一个字母不一样叫相邻
:
|
