9

这是Gayle Laakmann McDowell在《 Cracking the Coding Interview》一书中的问题之一：

实现一个算法来确定一个字符串是否具有所有唯一字符。如果你不能使用额外的数据结构怎么办？

作者写道：

我们可以通过使用位向量来减少空间使用量。我们将假设，在下面的代码中，字符串只是小'a'写到'z'. 这将允许我们只使用一个 int。

作者有这个实现：

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0)
            return false;
        checker |= (1 << val);
    }
    return true;
}

假设我们摆脱了“字符串只是小写'a'通过'z'”的假设。相反，字符串可以包含任何类型的字符，如 ASCII 字符或 Unicode 字符。

是否有与作者的解决方案一样有效的解决方案（或接近与作者的解决方案一样有效的解决方案）？

相关问题：

4

7 回答 7

6

for the asccii character set you can represent the 256bits in 4 longs: you basically hand code an array.

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

You can use the following code to generate the body of a similar method for unicode characters:

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}
于 2014-01-11T02:54:01.033 回答
3

你只需要一行......实际上不到一行：

if (str.matches("((.)(?!.*\\1))*"))

这使用否定的前瞻性来断言每个字符在字符串的后面不会重复。

这种方法的时间复杂度为 O(n^2)，因为对于输入中的所有 n 个字符，后面的所有字符（其中有 n 个）都会进行比较是否相等。

于 2014-01-11T03:27:20.223 回答
2

我认为我们需要对“附加数据结构”有一个通用且实用的定义。直观地说，我们不想将每个标量整数或指针称为“数据结构”，因为这使得任何禁止“附加数据结构”变得毫无意义。

我建议我们从大 O 表示法中借用一个概念：“附加数据结构”是随着数据集的大小而增长的。

在本例中，OP 引用的代码似乎需要 O(1) 的空间，因为位向量恰好适合整数类型。但正如 OP 所暗示的，问题的一般形式实际上是 O(N)。

解决一般情况的一个示例是使用两个指针和一个嵌套循环来简单地比较每个字符。空间要求是 O(1)，但时间要求是 O(N^2)。

于 2014-01-11T06:23:18.927 回答
0

下面的算法怎么样？

脚步：

将字符串转换为小写。

循环遍历字符串中的每个字符

设置变量数据 = 0

计算偏移量 = 字符串中第一个字符的 ascii 值 - 97

使用 mask = 1 << offset 设置该位置的标志

如果按位 AND 返回 true，则表示字符重复（掩码和数据），因此请在此处中断。

否则，如果我们还没有看到字符重复，请通过执行按位或执行 data = data | 来设置该字符的位。面具

继续直到字符结束。

于 2014-01-11T10:58:36.867 回答
0

我将此答案作为想法或建议发布。我不确定这个解决方案的运行时间复杂度是否真实（但我确实认为有效时间复杂度不应该超过O(n)，但我很高兴知道你们中是否有人想解释。

所以，这个想法是这样的。我们使用两个指针（我认为它们不属于数据结构的范畴，否则事情就会太难了）。一个叫一个fast叫slow。正如他们的名字一样，快速指针的遍历速度比慢速指针（一次 2 个索引）要快。我们将继续检查这些位置的角色，直到发生以下两种情况之一：

  1. 快速和慢速指向相同的索引（现在比较它们的字符没有意义，因为它们将相等）
  2. s[slow] == s[fast]（因为现在不同索引处的 2 个字符相等，我们可以返回 false）

现在我们只需重置快速指针并使其沿着字符串遍历（一个接一个，不再那么快了吧？）直到它变得等于慢，检查是否为s[fast] == s[slow]真，以防它返回假。

所以，C++ 中的代码是这样的：

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  int slow = 0, fast = 1;
  bool flag = false;
  //   cout << "Running..." << endl;
  while (slow != fast) {
    if (s[slow] == s[fast]) {
      flag = true;
      break;
    }
    // cout << "slow: " << s[slow] << " fast: " << s[fast] << endl;
    slow = (slow + 1) % n;
    fast = (fast + 2) % n;
  }
  fast = 0;
  while (!flag && fast != slow) {
    if (s[slow] == s[fast]) {
      flag = true;
      break;
    }
    fast = (fast + 1) % n;
  }
  if (flag) {
    cout << "Duplicates present." << endl;
  } else {
    cout << "No duplicates present." << endl;
  }
  return 0;
}
于 2021-01-16T14:46:05.493 回答
0

没有任何额外数据结构的单线解决方案： 

str.chars().distinct().count() == (int)str.length();
于 2020-04-21T11:50:39.930 回答
0 
import math
def uniqueCharacters(str):
     
    # Assuming string can have characters
    # a-z this has 32 bits set to 0
    checker = 0
     
    for i in range(len(str)):
        
        bitAtIndex = ord(str[i]) - ord('a')
        
        # If that bit is already set in
        # checker, return False
        if ((bitAtIndex) >= 0):
            
            if ((checker & ((1 << bitAtIndex))) > 0):
                print('duplicate character: '+str[i])
                return False
                 
            # Otherwise update and continue by
            # setting that bit in the checker
            checker = checker | (1 << bitAtIndex)
            
 
    # No duplicates encountered, return True
    return True
 
# Driver Code
if __name__ == '__main__':
     
    input_word = input('Enter string: ')
    input_word = input_word.lower()
    if (uniqueCharacters(input_word)):
        print("The String " + input_word +
              " has all unique characters")
    else:
        print("The String " + input_word +
于 2021-04-15T00:24:52.607 回答