函数式编程刷题笔记

作者 uunnfly 日期 2020-12-20
函数式编程
函数式编程刷题笔记

刷题地址见此：hackerrank的fp刷题专题

使用语言：scala

List Replication

解法一：for + yield

1
2
3
def f(num:Int,arr:List[Int]):List[Int] = {
    for {e <- arr; _ <- 1 to num} yield e
}

注意for 后面是大括号，一行写了两个循环

解法二：flatMap

1
arr flatMap (List.fill(num)(_))

用了List.fill(num)(_),柯里化函数（偏应用函数）

Filter Positions in a List

1
def f(arr:List[Int]):List[Int] = arr.zipWithIndex.filter(_._2 %2 == 1).map(_._1)

zipWithIndex返回一个元组列表，每个元组第一个是值，第二个是下标

或者使用view，性能更好

1
def f(arr:List[Int]):List[Int] = arr.view.zipWithIndex.filter { _._2 % 2 != 0 }.map { _._1}.force.toList//force可以不要

或者使用collect（collect接受一个偏函数类型的参数），collect可以代替filter + map

1
2
//case是偏函数的语法糖
arr.view.zipWithIndex.collect{case (a,b) if b % 2 == 1 => a}

Reverse a List

不用reverse： 

1
arr.foldLeft(List[Int]())((acc, v) => v::acc)

另一种解法：递归，每次把原数组尾部放到新数组的最前面

1
2
3
4
5
6
7
8
9
def f(arr:List[Int]):List[Int] = {
    def revList(orig: List[Int], rev: List[Int]): List[Int] = {
        orig match {
            case Nil => rev
            case x::xs => revList(xs, x :: rev)
        }
    }
    revList(arr, Nil)
}

Scala中的List存在两种情况：要么是空List，写做Nil；要么由一个head元素紧接着另一List tail组成。

双冒号（::）表示cons操作符；x表示List的首元素，xs表示剩余部分。

Sum of Odd Elements

本题可以有负数，用%2 == 1来判断会有错误，用位元算就不会有这种问题。

注：在java里 -1 % 2 = 1, 而在scala里 -1%2 = -1

常规解法：filter + sum，filter(x => x% 2 == 1) 里面的x只出现一次，用filter(_%2 ==1)就可以

1
def f(arr:List[Int]):Int = arr.filter(_% 2 != 0).sum

解法二：不用sum用reduceLeft

1
arr filter(_ % 2 != 0) reduceLeft(_ + _)

解法三：用foldLeft, 0是一个初始值

1
arr.foldLeft(0){(acc, cur) => if (cur % 2 != 0) acc+cur else acc}

List Length

解法一：使用foldLeft

1
def f(arr:List[Int]):Int = arr.foldLeft(0){(acc, _) => acc+1}

解法二：递归

1
2
3
4
5
6
def f(arr:List[Int]):Int = {
    arr match {
        case Nil => 0
        case hd::tl => 1 + f(tl)
    }
}

Update List

1
2
3
arr.map(Math.abs(_))
arr.map(Math.abs) //此参数可以省略
arr.map(_.abs) //Int本身就有abs方法

Evaluating ex

1
2
3
4
5
def factorial(n: Int): Int = (1 to n).product

def f(x: Float): Float = 
    (List.range(0, 10) map (e => math.pow(x, e) / factorial(e)))
        .sum.toFloat

http://giocc.com/exploring-functional-programming-in-scala-through-hackerrank.html

FRIENDS