不会,是因为不知道

算法写到最后,比拼的都是数学。

这是若干年前,我的编程启蒙老师说的。有点像武林前辈的教诲。以后每每想起,都默默赞同,唏嘘不已。

学习数学的方法论,就是四个字,玩命刷题。所以算法好不好,全看题刷的够不够。高中学算法,刷题都是拿着本书,一章一章过。高级些的,家里装了宽带,会去大学的Online Judge在线刷题。但题目多是英文,艰深难懂。

去年底,偶然接触了LeetCode刷题网站,整个体验非常棒,而且有中文版网站”力扣“。做了几道题,不禁感慨。过去的这十几年,互联网迅猛发展,学习和资源越来越多,学习的途径越来越丰富。以前晦涩的刷题网站,如今清秀的如丝般润滑。回头看当年,不亚于拿着iPhone看大哥大的感觉。

几个星期前,机缘巧合收到邀请,在线参加了一个Google的Foobar编程挑战。具体细节择日再谈。今天主要来说说其中的一道题目。

题目很长,大概意思就是有很多人有编号的人,排成队。现在需要算法根据他们的编号算出一个校验值(checksum)。例如:

0 1 2 /
3 4 / 5
6 / 7 8

这个例子里,是一个3×3的队列。第一行取所有数字,第二行以后依次少取一个数字,最后一行只取一个数字。要求计算出所有取出数字的异或值(XOR (^))。比如在上面这个例子里,返回值为0^1^2^3^4^6 == 2

异或运算中,相同为0,不同为1。1^0=0^1=1, 1^1=0^0=0。

同时,第一个开始的编号也是给定的。例如,当开始编号为17,每列4个人的时候:

17 18 19 20 /
21 22 23 / 24
25 26 / 27 28
29 / 30 31 32

算出来的值就是17^18^19^20^21^22^23^25^26^29 == 14

程序最终接收两个参数(开始编号s,队列长度l),输出校验值。

Input: solution(0, 3)
Output: 2

Input: solution(17, 4)
Output: 14

这种题的描述本身,已经给出了计算过程。根据直观的描述,写出第一版答案并不难:

a = 0                   # 初始化
for i in range(l):      # 对于第i行:
  sn = s + i * l        # 计算出第一个数字
  for j in range(l-i):  # 计算连续 len - i 个数字的异或
    a ^= sn + j
return a                # 输出

把测试数据代入,没有问题。边界值测了测,也没有问题。

提交代码,等待AC……一阵等待后,提交失败了……

Foobar挑战的特点之一,就是不会告诉你为什么测试不通过。大部分情况,测试数据不通过,要么边界值没考虑好,要么复杂度没达到要求。鉴于总体测试运行时间很长,我猜测主因是时间复杂度。

分析程序,两个循环嵌套,所以不难得出,该算法的时间复杂度是O(n2)。再回去仔细读题,才发现题目说编号的范围是0到2000000000(10e9),不超时才怪。。。

显然,这里需要一个快速计算连续数字异或值的公式

这让我想起上学考试的经历。从一道题的描述,分析好了,也抽象出了数学模型,但就因为想不起来对应的公式,题目解不出来。待考完试,翻开课本,找到公式。一瞬间,恍然大悟。

好在做题不是考试,搜索一下也没问题。最终找到这么几条定律:

交换律:p ^ q = q ^ p
结合律:(p ^ q) ^ r = p ^ (q ^ r)
恒等律:p ^ 0 = p
归零律:p ^ p = 0
自反:p ^ q ^ q = p ^ 0 = p

原本期望可以找到一个类似高斯公式的东西,直接计算出连续异或值,但是这几条规律似乎并没有什么帮助。

不过马上我就搜索到了一个求1到n连续异或的算法。连续分析一些自然数,可以很容易得出求任意1~n连续异或的算法:

def getXor(n):
    a = n % 4
    if a == 0:
        return n
    if a == 1:
        return 1
    if a == 2:
        return n + 1
    return 0

那么如何求从a~b连续异或的值呢?这里只需要在结合异或的基本定律就好了:

 a^(a+1)^(a+2)^...^b
=1^1 ^ 2^2 ^ ... ^ (a-1)^(a-1) ^ (a ^ (a+1) ^ ... ^ b)
=1^2^3^...^a ^ 1^2^3^...^b
=getXor(a-1) ^ getXor(b)

结合着两条,我们在计算每一行的连续异或值时,就可以把原本O(n)得复杂度降为O(1)。总体的时间复杂度也降为O(n)。

最终的代码为:

def solution(start, length):
    def xor(n):
        return [n, 1, n+1, 0][n % 4]
    ans = 0
    i = length
    while i > 0:
        end = start + i - 1
        ans ^= xor(end) ^ xor(start-1)
        start = start + length
        i -= 1
    return ans

总结这道题,关键的解题点有两个。一个是异或运算的几个基本定律,另一个便是从1~n异或和的运算公式。只有之前做过类似题,知道异或特性的人,才能从容解开这道题。而对于绝大多数人来说,日常不会接触到那么多异或运算,这道题就显得略为不公平。不过好在这种题目并不限制使用搜索引擎,其实在现代,借助搜索引擎完成任务,也是一种能力。而且这种能力,也是很重要的解决问题的能力。

You Might Also Like
发表评论