10

这个问题是在谷歌面试时问我的。我可以做到 O(n*n) ... 我可以在更好的时间做到这一点。字符串只能由 1 和 0 组成。

定义：

X & Y 是由 0 或 1 组成的字符串

D(X,Y)= 从 X 和 Y 中删除开头共同的东西。然后从两个字符串中添加剩余的长度。

例如

D(1111, 1000)= 只有第一个字母是常见的。所以剩下的字符串是111& 000。因此结果length("111")& length("000")= 3 + 3 = 6

D(101, 1100)= 只有前两个字母是常见的。所以剩下的字符串是01& 100。因此结果length("01")& length("100")= 2 + 3 = 5

很明显，确实发现如此疯狂的距离将是线性的。（米）。

现在的问题是

给定 n 个输入，比如说

1111
1000
101
1100

找出可能的最大疯狂距离。

n 是输入字符串的数量。m 是任何输入字符串的最大长度。

O(n 2 * m) 的解决方案非常简单。可以以更好的方式完成吗？假设 m 是固定的。我们能比 O(n^2) 做得更好吗？

4

6 回答 6

22

将字符串放入树中，其中 0 表示向左，1 表示向右。所以例如

1111
1000
101
1100

会产生一棵树

        Root
             1
          0     1
         0 1*  0  1
        0*    0*    1*

其中 * 表示一个元素在那里结束。建造这棵树显然需要O(n m).

现在我们必须找到树的直径（两个节点之间的最长路径，这与“疯狂距离”相同）。那里提出的优化算法会命中树中的每个节点一次。最多有min(n m, 2^m)这样的节点。

所以如果n m < 2^m，那么算法就是O(n m)。

如果n m > 2^m（并且我们必须有重复的输入），那么算法仍然是O(n m)从第一步开始的。

这也适用于具有通用字母的字符串；对于带有字母的字母表，k构建一棵k-ary 树，在这种情况下，运行时间仍然是 O(nm)，出于同样的原因，尽管它需要k多倍的内存。

于 2013-02-25T08:14:03.383 回答
4

我认为这可以通过创建一个二叉树在 O(nm) 时间内实现，其中字符串中的每个位都对路径进行编码（0 左，1 右）。然后找到可以在 O(n) 时间内完成的树节点之间的最大距离。

于 2013-02-25T08:14:13.787 回答
1

这是我的解决方案，我认为它有效：

  1. 从所有字符串创建二叉树。树将以这种方式构建：在每一轮中，选择一个字符串并将其添加到树中。因此，对于您的示例，树将是：

                      <root>
          <1>            <empty>
 <1>            <0>

    <1> <0> <1> <0> <1> <0> <0>

因此，从根到叶的每条路径都将代表一个字符串。

  1. 现在每两片叶子之间的距离就是两根弦之间的距离。要找到疯狂的距离，您必须找到该图的直径，您可以通过 dfs 或 bfs 轻松完成。

该算法的总复杂度为：O(n*m) + O(n*m) = O(n*m)。

于 2013-02-25T08:21:25.727 回答
0

要在 O(nm) 中得到答案，只需遍历所有字符串的字符（这是一个 O(n) 操作）。我们将最多比较 m 个字符，所以这将完成 O(m)。这给出了总共 O(nm)。这是一个 C++ 解决方案：

int max_distance(char** strings, int numstrings, int &distance) {
    distance = 0;
    // loop O(n) for initialization
    for (int i=0; i<numstrings; i++) 
        distance += strlen(strings[i]);

    int max_prefix = 0;
    bool done = false;
    // loop max O(m)
    while (!done) {
        int c = -1;
        // loop O(n)
        for (int i=0; i<numstrings; i++) {
            if (strings[i][max_prefix] == 0) {
                done = true; // it is enough to reach the end of one string to be done
                break;  
            }

            int new_element = strings[i][max_prefix] - '0';
            if (-1 == c)
                c = new_element;
            else {
                if (c != new_element) {
                    done = true;    // mismatch
                     break;
                }
            }
        }
        if (!done) {
            max_prefix++;
            distance -= numstrings;
        }
    }

    return max_prefix;
}


void test_misc() {
    char* strings[] = { 
        "10100",
        "10101110",
        "101011",
        "101"
    };

    std::cout << std::endl;
    int distance = 0;
    std::cout << "max_prefix = " << max_distance(strings, sizeof(strings)/sizeof(strings[0]), distance) << std::endl;
}
于 2014-05-05T07:16:12.863 回答
0

我认为这个问题类似于“查找两个字符串的前缀”，您可以使用 trie( http://en.wikipedia.org/wiki/Trie ) 来加速搜索

三天前我有一个谷歌电话面试，但也许我失败了......

祝你好运

于 2014-05-05T07:40:53.097 回答
0

不知道为什么在迭代时使用树给你同样大的 O 计算复杂度而没有代码复杂度。无论如何，这是我在 javascript O(mn) 中的版本

var len = process.argv.length -2; // in node first 2 arguments are node and program file
var input = process.argv.splice(2);
var current;
var currentCount = 0;
var currentCharLoc = 0;
var totalCount = 0;
var totalComplete = 0;
var same = true;
while ( totalComplete < len ) {
        current = null;
        currentCount = 0;
        for ( var loc = 0 ; loc < len ; loc++) {
                if ( input[loc].length === currentCharLoc) {
                        totalComplete++;
                        same = false;
                } else if (input[loc].length > currentCharLoc) {
                        currentCount++;
                        if (same) {
                                if ( current === null ) {
                                        current = input[loc][currentCharLoc];
                                } else {
                                        if (current !== input[loc][currentCharLoc]) {
                                                same = false;
                                        }
                                }
                        }
                }
        }
        if (!same) {
                totalCount += currentCount;
        }
        currentCharLoc++;
}

console.log(totalCount);
于 2015-03-19T05:38:40.443 回答