gpt4 book ai didi

数组和字符串破解编码面试第 6 版解决方案 1.1

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:14:19 25 4
gpt4 key购买 nike

我在业余时间练习破解代码面试。问题指出:是唯一的:实现一种算法以确定字符串是否具有所有唯一字符。如果您不能使用额外的数据结构怎么办?

我找到的解决方案是:https://github.com/careercup/CtCI-6th-Edition-cpp/blob/master/Ch%201.Arrays%20And%20Strings/1.Is%20Unique/1.%20Is_unique.cpp

我的实现是:

bool UniqueCharsHash(string word) {

map<char, bool> uniqueChar; //keyType, valueType

for (int i = 0; i < word.length(); i++) {
char letter = tolower(word[i]);
if (!uniqueChar[letter]) {
uniqueChar[letter] = true;
} else {
return false;
}
}
return true;
}

//O(n^2) run time using a two loops (1 outer and 1 inner)
bool UniqueCharNoDS(string word) {
for (int i = 0; i < word.length() - 1; i++) {
for (int j = i + 1; j < word.length(); j++) {
if (word[i] == word[j]) {
return false;
}
}
}
return true;
}

但是在书的提示部分它指出:

  1. 尝试哈希表
  2. 位向量有用吗
  3. 你能在 O(Nlogn) 时间内解决吗

我想知道在所示的 3 种方法中,是否有 NlogN 时间?

最佳答案

正如经常指出的那样,这个问题可以在 O(1) 中解决,因为由唯一字符组成的最长字符串的长度为 256 个字符。

因此当/如果您的算法命中第 257 个字符时,它可以停止并报告“否”。

即使您使用朴素的算法搜索前缀中的每个字符直到该点,在达到限制之前最多也有 255*128 次比较。 (不需要对算法进行任何调整,如果有的话,它必须在第257个字符上报告“否”。)

关于数组和字符串破解编码面试第 6 版解决方案 1.1,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43429415/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com