1

我必须在已经排序的字符串列表中插入一个字符串，实现这一点的最佳方法是找到要插入的确切位置，而不必对所有列表进行排序并且不预先添加字符串。我只需要找到要插入的位置。

我确实有一个比较 2 个字符串的函数 compare(first-string , second-string) 如果第一个字符串必须放在第二个字符串之前，这个函数给我 true 以其他方式。预计会使用此功能。

我的场景中使用的 List 不是 c++ std::list 而是一个处理列表某些功能的自定义类。

4

2 回答 2

0

如果您到达一个停车位，每个停车位都以从 A 到 Z 的字母顺序命名。

然后我告诉你，你可以在字母 P 停车。

你怎么找到那个地方？

于 2021-01-12T11:05:16.533 回答
-1

您不应该能够遍历您的列表，并对每个项目进行比较，您可以在其中对每个字符串进行评分，以确定它们彼此之间的接近程度。假设你有一个这样的字符串列表：["aa", "ab", "bc", "cc"] 并且你想插入 "bb"。“bb”与“aa”有多相似，答案是 0。下一次迭代。"bb" 与 "ab" 的相似程度： 1. 现在我们增加了 1。标记位置并继续循环。“bb”与“bc”有多相似： 1. 下一个循环。"bb" 与 cc: 0 的相似程度。所以当我们得到一个减少时，我们现在知道应该放置 "bb" 的位置已经过去了。这意味着我们可以回去更彻底地搜索。

这是一个完整的工作功能：

    void InsertAZ(list<string>& strings, string&& str) {
        std::list<string>::iterator it;
        it = strings.begin();
        for (auto s : strings) {
            if ((s > str) == 1) {
                strings.insert(it, str);
                break;
            }
            ++it;
        }
    }

    int main()
    {
        list<string> strings = { "aaa", "aab", "aac", "aba", "abb", "abc", "aca", "acb", "acc", "baa", "bab", "bac", "bba", "bbb", "bbc", "bca", "bcb", "bcc", "caa", "cab", "cac", "cba", "cbb", "cbc", "cca", "ccb", "ccc" };

        InsertAZ(strings, "bab");

        cin.get();
    }
于 2021-01-12T11:30:07.273 回答