ARTS(35)

1 Algorithm

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

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

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

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

对于 insert 和 remove 操作,使用 map 数据结构可以很容易......

ARTS(34)

1 Algorithm

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

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

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

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

......

ARTS(33)

1 Algorithm

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

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

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

ARTS(32)

1 Algorithm

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

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

a ^ a = 0

0 ^ a = a

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

如果数组中的元素都出现两次,那么对其所有元素进行异或操作最终结果必然为 0,......

ARTS(31)

1 Algorithm

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

首先对字符串按字符 . 划分为四个部分,在将其转换为整数,然后依次左移 24, 16, 8 和 0 ......