给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法,从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。 优化你的算法,使它最小化调用语言 内置 随机函数的次数。
时间: 2023-05-15 07:05:00 浏览: 66
可以使用哈希表来存储黑名单中的数字,然后遍历 [0, n - 1] 范围内的数字,如果该数字不在黑名单中,则直接返回该数字。如果该数字在黑名单中,则将其映射到 [n - len(blacklist), n - 1] 范围内的一个数字,其中 len(blacklist) 是黑名单中数字的个数。这样可以保证返回的数字不在黑名单中,并且所有不在黑名单中的数字都有同等的可能性被返回。这个算法的时间复杂度为 O(len(blacklist)),空间复杂度为 O(len(blacklist))。
为了优化算法,可以使用一个映射表来记录黑名单中的数字和它们映射到的数字。具体来说,可以将黑名单中的数字映射到 [n - len(blacklist), n - 1] 范围内的数字,然后将这些数字和它们映射到的数字存储到一个映射表中。当需要返回一个未加入黑名单的数字时,可以先生成一个随机数,然后判断该随机数是否在映射表中。如果在映射表中,则返回映射表中对应的数字;否则直接返回该随机数。这个算法的时间复杂度为 O(1),空间复杂度为 O(len(blacklist))。
相关问题
用Python写一个黑名单插件
好的,以下是一个简单的Python黑名单插件的代码:
```python
blacklist = ['spam', 'scam', 'phishing']
def check_message(message):
for word in blacklist:
if word in message:
return True
return False
```
这个插件会检查一条消息是否包含黑名单中的任何一个词语,如果包含则返回True,否则返回False。你可以在你的应用程序中使用这个插件来过滤不良内容。
完成一个python hamlet词频统计程序并增加一个单词黑名单列表定义,在列表中的单词不在统计
以下是一个简单的 Python 代码,用于对哈姆雷特文本进行词频统计。同时,我们增加了一个单词黑名单列表,如果单词出现在该列表中,则不进行统计。
```python
# -*- coding: utf-8 -*-
from collections import Counter
blacklist = ["the", "and", "of", "to"] # 单词黑名单列表
with open("hamlet.txt", "r") as f:
text = f.read().lower()
# 将文本中的标点符号和换行符替换为空格
text = text.replace('\n', ' ').replace(',', ' ').replace('.', ' ').replace(';', ' ').replace(':', ' ').replace('!', ' ').replace('?', ' ')
# 将文本分割成单词列表
words = text.split()
# 过滤掉黑名单中的单词
filtered_words = [word for word in words if word not in blacklist]
# 统计单词频率
word_counts = Counter(filtered_words)
# 输出前20个出现频率最高的单词
for word, count in word_counts.most_common(20):
print(f"{word}: {count}")
```
在上面的代码中,我们首先定义了一个单词黑名单列表 `blacklist`,其中包含不希望被统计的单词。然后,我们打开并读取哈姆雷特文本文件 `hamlet.txt`,将其转换为小写,并将文本中的标点符号和换行符替换为空格。接下来,我们将文本分割成单词列表,在这之前我们先过滤掉黑名单中的单词。最后,我们使用 `collections.Counter` 对单词列表进行统计,并输出出现频率最高的前20个单词及其出现次数。