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的答案不同)是:

之后有些题目也能看到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为核心,比较下来答案中的方式可能更好。