0

以下函数采用三个单词对象，并相互检查每个单词的字母坐标（在表格中）。这个想法是从没有相交字母坐标的列表中获取三个单词的组合。但是，当您有超过 600000 种可能的组合时，这将变得非常耗时。

bool lettersIntersect(word one, word two, word three)
{
    for(int i = 0; i < one.getLength(); i++)
        for(int j = 0; j < two.getLength(); j++)
            if(one.getLetterPosition(i).x == two.getLetterPosition(j).x && one.getLetterPosition(i).y == two.getLetterPosition(j).y)
                return true;
    for(int i = 0; i < two.getLength(); i++)
        for(int j = 0; j < three.getLength(); j++)
            if(two.getLetterPosition(i).x == three.getLetterPosition(j).x && two.getLetterPosition(i).y == three.getLetterPosition(j).y)
                return true;
    for(int i = 0; i < three.getLength(); i++)
        for(int j = 0; j < one.getLength(); j++)
            if(three.getLetterPosition(i).x == one.getLetterPosition(j).x && three.getLetterPosition(i).y == one.getLetterPosition(j).y)
                return true;
    return false;
}

有没有更有效的方法来做到这一点？

4

3 回答 3

1

我可以给你一个让我立即印象深刻的提示。如果它具有误导性，请不要怪我。您可以在最后尝试一次并查看性能。

为每个单词对象创建映射（使用 stl），即map_one,map_two和map_three

将坐标值作为给定单词对象的每个字母的键添加到其各自的映射中。

然后使用这些地图检查是否有交叉路口。 检查 C++ 中的地图是否包含来自另一个地图的所有键

于 2013-04-04T13:39:55.933 回答
0

我认为唯一可以优化的是避免双重检查：

    for(int i = 0; i < one.getLength(); i++)
        for(int j = i+1; j < two.getLength(); j++)
            if(one.getLetterPosition(i).x == two.getLetterPosition(j).x && one.getLetterPosition(i).y == two.getLetterPosition(j).y)
            return true;

第二个 for 循环从 j = 0 更改为 j = i+1，这使您可以用一半的时间进行检查。

在两个坐标点之间进行检查是一个 ^2（n 平方）问题，这意味着进行检查所需的时间与您可以检查的元素数量的平方成正比。我认为除了避免双重检查之外，没有其他方法可以优化这一点，就像我解释的那样。

当然，除了通过引用传递之外，已经向您建议了like。

于 2013-04-04T13:13:16.920 回答
0

在这个家庭作业问题或其他学习练习中，您打算使用以前教过的方法重新排列数据以加快搜索速度。重新排列数据后，您应该能够找到一种有效扫描数据以查找重复数据的方法。

于 2013-04-04T13:27:19.860 回答