leetcode 题解(1)

准备明年暑假投的实习,也是练练算法能力,最近一直在刷leetcode。虽然感觉leetcode这玩意跟之前做的OI题目差挺多,不过做做也挺有意思,毕竟都是基础题。

今天做到一道很有意思的题,有意思不是说它很难,而是说这题的逻辑很清晰很简单,但是就是写起来特别麻烦,链接在此

这道题其实转述过来很简单,就是给一个数独,判断这个数独是不是一个合法的数独,逻辑真的非常简单,就是根据数独合法性的判断一步一步去验证就行。但是要写对就很麻烦很不容易。

但是,光这样写是不是太没有意思了呢。其实看到这条题目我第一个反应就是:如果能够在scala或者haskell里写这道题,会是多么惬意的事情啊。

为什么说在haskell或者scala这种函数式语言里面写这样的题目是一种非常容易甚至是说比较擅长的事呢?

  1. 函数式编程最擅长的事情就是抽象出一个函数来处理一系列过程,而这个抽象出来的函数,是可以接收一系列参数的。这里的参数可以是一个数组,也可以是一个函数。这样的好处在于,将需要 重复运行 的复杂过程的 控制逻辑 进行抽象,每次运行只要传入不同的参数就行。当然,在这道题目中没办法将这个特性体现的比较好。

  2. 在许多函数式语言中, immutable data 是一个非常重要的概念。这里指的是,没有 变量 这样的概念。既然没有变量,我们如何去抽象数据呢?可以简单的奖指向数据的符号(Symbol) 理解为,这个符号就代表了这个数据,是无法改变的。想要改变数据内部的结构或者值,那就重新创造一个数据好了。这样的思想在scala中可以用yield语句很好的体现。最近在学的ruby也有这样的用法。当然,在Python中也是有这样的用法的。

那好,来看这条题目。其实我们要抽象的逻辑很简单——给出9个数字,如何判断他们之中没有重复出现的数字。这当然可以用非常简单的循环来实现。我一开始被给出的test case的样子给误导了,本来以为每一行的数字都是通过str给出的,没想到是通过List[str]给出的。所以我用正则匹配来完成了判断。

def isValid(self, s):
    for i in range(0,10):
        c = chr(ord('0')+i)
        p = re.compile('(.*'+c+'.*)' +'(.*'+c+'.*)+')
        if p.match(s):
            return False
    return True

完成了这样一个判断的逻辑的抽象以后(虽然这是一个非常简单的抽象),接下来我们要做的就是——如何通过原有的数据产生我们要“喂”给这个函数的数据?

要判断一个数独是否合法其实非常简单,只要判断一下是否每行都是合法的,每列都是合法的,每个3×3的九宫格是否是合法的。

首先就像我之前说的那样-。-我判断失误了。。我以为给个input是List[str],没想到是List[List[str]],当然这不是什么大的问题,一行代码就解决了。

board = [reduce(add, [x for x in y]) for y in boardt]

这里的语句就和scala中的yield功能是一样的,只不过将产生的数据放在前面,控制逻辑放在后面。还有就是使用了reduce函数,map, filter, reduce(fold) 再加上zip 等函数是在函数式编程中最经典的处理iterable的数据的方法,有了他们就可以不用写复杂的for循环语句了,对这些不了解的可以看看这个简单的tutorial.

接下来就是分别产生我们要测试的数据了。

  1. 首先是每一行的,这很简单,本身就是每一行的数据了。

  2. 然后是每一列的,每一列的话,就是提取在board中的每个element中的第i的字符,然后拼接在一起,最后放入一个新的list,其实了解过haskell或者scala的人应该会马上想到,这其实就是一个flasMap的过程。

  3. 最后的也是最复杂的,要提取出九个小的九宫格,具体我也不赘述了,直接看代码体会吧。

case1 = board
case2 = [reduce(add, [x[i] for x in board]) for i in range(0,9)]
case3 = [board[3*i+k][3*j:3*j+3] for k in range(3)]) for i in range(3) for j in range(3)]

然后要做的就是,对这三个case中的所有元素进行判断是否合法,这也很简单,通过一个map就可以做到。最后就是,得到了判定结果之后,通过reduce 将他们 卷积 起来,这个卷积是我自己发明的,reduce过程就像一条茅台,从一头卷到另一头,每卷一点,就会把现在的结果和这一格的数据进行运算得到新的结果之后继续卷下去。。

reduce(and, map(isValid, case1))

其实我们还可以把这个运算过程lift到一个更高的抽象,对于了解haskell或者范畴论的朋友来看这个过程其实就是一个functor.

case = [case1, case2, case3]
res = reduce(and, map(reduce(isVaild), case))

当然,上面这段代码是无法在Python中执行的,因为在Python中是无法对函数进行Curry化的。这里只是表述一个思想。就是说:控制抽象数据抽象 的分离。定义好对数据的运算,这个过程一定是要与数据的产生分离的,这对保持代码的整洁与可维护性都是很重要的。

最后贴上我直接在leetcode中写的代码,第一次没能过,加了一句话就过了。

import re
def andt(x,y):
    return x and y
def add(x,y):
    return x+y
class Solution(object):
    def isValid(self, s):
        for i in range(0,10):
            c = chr(ord('0')+i)
            p = re.compile('(.*'+c+'.*)' +'(.*'+c+'.*)+')
            if p.match(s):
                return False
        return True
    def isValidSudoku(self, boardt):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        board = [reduce(add, [x for x in y]) for y in boardt]
        return reduce(andt, map(self.isValid,board), True) \
               and reduce(andt, map(self.isValid,[reduce(add, [x[i] for x in board]) \
               for i in range(0,9)]) ) \
               and reduce(andt,map(self.isValid, [reduce(add, [board[3*i+k][3*j:3*j+3] \
               for k in range(3)]) for i in range(3) for j in range(3)]))
Ivan Yang 19 December 2015
blog comments powered by Disqus