ARTS(35)

1 Algorithm

设计一个数据结构,在下面的操作时间复杂度都是 $O(1)$

- insert(val): 当元素 val 不存在,向集合中插入该项。

- remove(val): 当元素 val 存在,从集合中删除该项。

- getRandom: 随机返回集合中一项,每个元素都有相同的概率返回。

对于 insert 和 remove 操作,使用 map 数据结构可以很容易实现;但是 getRandom 操作不能在 $O(1)$ 时间复杂度完成,因此要借助数组才能满足条件。

56

ARTS(34)

1 Algorithm

一个数独的解法需遵循如下规则:

1:数字 1-9 在每一行只能出现一次。

2:数字 1-9 在每一列只能出现一次。

3:数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

对于一个数独表格,总共有 $81(9 \times 9)$ 个表格,索引为 0-80,所以对于每一个索引位置对应的行、列和块索引分别为:

row = i / 9

col = i % 9

......

112

ARTS(33)

1 Algorithm

输入一个字符串,包含了 +, -, *, / 和非负整数,请输出该计算表达式的值。

例如: 1 + 12 - 4 * 2,输出的结果就是 5。

算法要求我们编写一个类似计算器的函数,输入为表达式计算,输出为表达式的值。如果写过编译器,这个问题不难,只要构建出一个抽象语法树(AST, Abstract Syntax Tree) 即可。

69

ARTS(32)

1 Algorithm

给定一个数组,有两个元素只出现了一次,而其余的出现了两次,找出两个只出现一次的元素,要求时间复杂度为 $O(n)$,空间复杂度为 $O(1)$。

对于位运算异或(^),有如下性质

a ^ a = 0

0 ^ a = a

a ^ b ^ c = a ^ (b ^ c)

如果数组中的元素都出现两次,那么对其所有元素进行异或操作最终结果必然为 0,如果元素中只有一个元素只出现了一次,那么所有元素异或的结果就是只出现一次的元素。那么两个元素只出现一次,那么该如何解决呢?

通过上述性质我们可以得知,最终的异或结果肯定不等于 0,也就是说肯定至少一......

75

ARTS(31)

1 Algorithm

给定一个 IPv4 地址的字符串,将其转换为 int 表示的整数,需要考虑不合法的字符串,只能使用常数空间。比如字符串 127.0.0.1 表示一个 IPv4地址,每一段都是 byte 表示的整数,四个 byte 可以表示 32 位的整数 2130706433。

首先对字符串按字符 . 划分为四个部分,在将其转换为整数,然后依次左移 24, 16, 8 和 0 位,将这些左移后的结果按照或(|)操作完整整数转换。那么不合法的情况有哪些呢?

合法的 IPv4 地址每一段的范围只能是 $[0, 255]$;

按照 . 划分只能划分为四个部分;

字符串......

68