scala99解题小结(List)


一个月之前,我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。

scala99的问题分为List,Arithmetic,Logic,Binary Tree,Multiway Tree,Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。

本次先是List相关。

P06 Find out whether a list is a palindrome

scala99给出的答案很简单,reverse一个list,比较和原来是否相等。想法很简单也很有效。

P26 Generate the combinations of K distinct objects chosen from the N elements of a list.

一个生成组合的题目。其实Scala自带combinations这个方法,而且返回值是个Iterator,你可以认为是一个懒加载,不会一下子生成所有数据。撇开原生解法,个人的解法(和Scala99的答案不同)是:

def combinations[A](n: Int, xs: List[A]): List[List[A]] = {
  // take 2 from (1, 2, 3, 4)
  // 1, take 1 from (2, 3, 4)
  // 2, take 1 from (3, 4)
  // 3, take 1 from (4)
  def tails(m: Int, ys: List[A]): List[(A, List[A])] = {
    if(m == 0 || ys.isEmpty) Nil
    else {
      val h :: tail = ys
      (h, tail) :: tails(m - 1, tail)
    }
  }
  def combinationsR(m: Int, ys: List[A]): List[List[A]] = {
    if(m == 0 || ys.isEmpty) Nil
    else if(m == 1) ys.map(List(_))
    else tails(ys.length - m + 1, ys).flatMap {
      case (y, tail) => combinationsR(m - 1, tail).map(y :: _)
    }
  }
  combinationsR(n, xs)
}

之后有些题目也能看到ListA#flatMap(a => ListB#map( b ? a)),这个其实和for(a <- ListA; b <- ListB)yield (b ? a)一样就是了。

P27 Group the elements of a set into disjoint subsets

我想得有点多,想要用做P26的方式来。但是实际上用P26的答案可能更方便,P27就变成每次去掉前一个组合,直接用剩下的元素即可。

P28 Sorting a list of lists according to length of sublists

我原本是用类似word count的方式在Scala的REPL中一点一点尝试出来的,但是答案中以sortWith为核心,比较下来答案中的方式可能更好。

,