跳转云挑战的命令式和函数式编程方案

Question

问题陈述

艾玛正在玩一款新的移动游戏，从连续编号的云开始。一些云是雷锋，另一些是积云。她可以跳到任何积云云上，其数值等于当前云的数目加上1或2。她必须避开雷锋。确定最低跳跃次数，艾玛将从她的起始位置跳到最后一个云端。赢得比赛总是有可能的。对于每一个游戏，艾玛将得到一个编号为0，如果他们是安全的云数组，如果他们必须避免1。例如，从0.6索引的c=0，1，0，0，0，1，0。每个云上的数字是它在列表中的索引，所以她必须避免索引1和5中的云。 0、-> 2、-> 4、-> 6或0 -> 2 -> 3 -> 3 -> 4 -> 6。第一条路径需要3次跳转，第二条路径是4次。函数描述在下面的编辑器中完成jumpingOnClouds函数。它应该以整数的形式返回所需的最小跳转次数。jumpingOnClouds具有以下参数(S)：

• c:二进制整数数组

输入格式第一行包含整数n，云总数。第二行包含n个空格分隔的二进制整数，描述云c我，其中0 <= i

命令式解决方案：

// Complete the jumpingOnClouds function below.
def jumpingOnClouds(c: Array[Int]): Int = {
    var i=0 
    var length = c.length
    var jumps = 0 
    while(i < length -1) { 
        if(i < length-2 && c(i+2) == 0 ) i+=2
        else i+=1
        jumps +=1
    }
    jumps 
}

使用递归的

函数式解决方案：

 def jumpingOnClouds(c: Array[Int]): Int = {
     val limit = c.length -2 
     def rec(jumps: Int, index: Int): Int = {
         if (index > limit) jumps 
         else { 
             val jumpingOffset: Int = if(index < limit && c(index + 2) == 0 ) 2 else 1
             rec(jumps+1, index + jumpingOffset)
         }
     }
     rec(0,0) 
 }

Answer 1

这些“故事”问题的关键是，这个故事如果不是完全误导的话，往往会分散人们对要解决的根本问题的注意力。

在这种情况下，您的代码通过计算和计数从开始到结束所需的跳转次数来解决这个问题。故事的编排方式大致如此。但值得注意的是：

1. N个零点序列的最小跳数总是N/2。
2. 在每一个零位序列的末尾都有一个要跳过的1，除了最后面的那个。

def jumpingOnClouds(c :Array[Int]) :Int =
  c.mkString.split("1").foldLeft(0)(_ + _.length/2 + 1) - 1

这不是最有效的解决方案，但由于输入Array仅限于不超过100个元素，所以我决定采用简洁而非效率的方法。