12

背景：我是一名 CS n00b，正在努力完成“破解编码面试”。第一个问题要求“实现一个算法来确定一个字符串是否具有所有唯一字符。” 我的（可能是幼稚的）实现如下：

def isUniqueChars2(string):
  uchars = []
  for c in string:
    if c in uchars:
      return False
    else:
      uchars.append(c)
  return True

作者建议如下实现：

def isUniqueChars(string):
  checker = 0
  for c in string:
    val = ord(c) - ord('a')
    if (checker & (1 << val) > 0):
      return False
    else:
      checker |= (1 << val)
  return True

是什么让作者的实现比我的更好（FWIW，作者的解决方案是用 Java 编写的，我将其转换为 Python ——我的解决方案是无法用 Java 实现的）？或者，更一般地说，解决这个问题需要什么？我采取的方法有什么问题？我假设有一些基本的 CS 概念（我不熟悉）很重要，有助于告知选择哪种方法来解决这个问题。

4

8 回答 8

45

这是我将如何写这个：

def unique(s):
    return len(set(s)) == len(s)

字符串是可迭代的，因此您可以将参数直接传递给以set()从字符串中获取一组字符（根据定义，字符串不会包含任何重复项）。如果该集合的长度与原始字符串的长度相同，那么您将拥有完全唯一的字符。

您当前的方法很好，我认为它比作者提出的版本更具 Pythonic 和可读性，但是您应该更改uchars为集合而不是列表。集合具有 O(1) 成员资格测试，因此如果是集合而不是列表，则c in uchars平均速度会快得多。uchars所以你的代码可以写成如下：

def unique(s):
    uchars = set()
    for c in s:
        if c in uchars:
            return False
        uchars.add(c)
    return True

如果字符串很大并且早期有重复，这实际上会比我的版本更有效，因为它会短路（一旦找到第一个重复就退出）。

于 2013-06-28T04:54:24.303 回答
5

美丽总比丑陋好。

你的方法非常好。这就是 python，当有无数种方法可以做某事时。（你的也更漂亮:)）。但是，如果您真的希望它更具 Python 风格和/或让它运行得更快，您可以使用一套，正如 FJ 的回答所描述的那样。

第二种解决方案看起来真的很难理解和理解。

（PS，dict是一个内置类型。不要覆盖它：p。并且string是标准库中的一个模块。）

于 2013-06-28T04:54:07.563 回答
2 
str = raw_input("Enter string: ")


def isUnique():
    test_dict = dict()
    is_unique = True
    for c in str:
        if(not test_dict.get(c, False)):
            test_dict[c] = c
        else:
            is_unique = False
            break
    if is_unique:
        return "String is unique"
    else:
        return "String is not unique"

print(isUnique())
于 2016-09-22T10:19:28.183 回答
1

您的解决方案并不正确，但您的变量 dict 实际上不是字典，这意味着它必须进行线性搜索来检查字符。书中的解决方案在恒定时间内进行检查。我会说另一种解决方案非常不可读，因为它使用设置数字中的位来检查 char 是否唯一

于 2013-06-28T04:54:18.767 回答
1

您从 Java 翻译成 Python 的解决方案是所谓的“位旋转”算法。这个想法是整数可以以多种方式处理：一种，作为数字。二，作为位的集合（32 个关闭/打开，或 64 个，或者你有什么）。该算法通过说每个位表示特定字符​​的存在或不存在来进行位旋转 - 如果第 n 位为 0，则设置它。如果为1，则该位对应的字符已经存在，所以我们知道没有唯一字符。

但是，除非您需要效率，否则请避免使用比特旋转算法，因为它们在工作方式上并不像非比特旋转那样不言而喻。

于 2013-06-28T04:56:50.680 回答
0

你的实现需要 O(n2)，作者需要 O(n)。在您的实现中， " if c in uchars:" ，当它检查 c 是否在这个数组中时，它必须遍历整个数组，这需要时间。所以你的并不比作者的好......

于 2013-08-06T16:04:30.170 回答
0

解决方案1：

def is_unique(string):
  if len(string) > 128:
    return False

  unique_tracker = [False] * 128
  for char in string:
    if unique_tracker[ord(char)] == False:
      unique_tracker[ord(char)] = True
    else:
      return False
  return True

解决方案2：

def is_unique_bit(string):
  if len(string) > 128:
  return False

  unique_tracker = 0
  for char in string:
    ascii_val = ord(char)
    if (unique_tracker & (1 << ascii_val)) > 0:
      return False
    unique_tracker |= (1 << ascii_val)
  return True
于 2016-12-18T00:51:33.787 回答
0

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

关注第二句话，它说我们不能使用额外的数据结构，即你需要考虑你的解决方案的空间复杂度。您的解决方案使用数组，因此不符合问题标准。

于 2017-10-07T19:06:09.600 回答