首页 文章

在列表上迭代时，在scala中突破循环

提问于
浏览 次
0

我正在努力解决问题 .

Problem : 您将获得4种颜色的N球序列：红色，绿色，黄色和蓝色 . 当且仅当满足以下所有条件时，序列才会充满颜色：

绿球和红球一样多 . 蓝球和黄球一样多 . 序列的每个前缀中的红球和绿球的数量之间的差异最多为1.序列的每个前缀中的黄球和蓝球的数量之间的差异最多为1.您的任务是编写程序，对于给定序列，如果它充满颜色则打印True，否则打印False .

我的解决方案：对于每个字符串，我生成所有可能的前缀和后缀以验证条件编号3和4.但是它需要更多时间 .

我们不是每次都生成前缀和验证条件，而是迭代字符串并验证条件 . 我想在不满足条件时突破循环 . 我无法在功能风格中得到它 . 有人可以帮助我如何实现它 .

我的解决方案

object Test {

    def main(args: Array[String]) {

      def isValidSequence(str: String) = {
        def isValidCondition(ch1:Char, ch2:Char, m:Map[Char, Int]):Boolean = m.getOrElse(ch1, 0) - m.getOrElse(ch2, 0) > 1
        def groupByChars(s:String) = s.groupBy(ch => ch).map(x => (x._1, x._2.length))
        def isValidPrefix(s:String):Boolean = (1 to s.length).exists(x => isValidCondition('R', 'G', groupByChars(s.take(x))))

        val x = groupByChars(str)
        lazy val cond1 = x.get('R') == x.get('G')
        lazy val cond2 = x.get('B') == x.get('Y')
        lazy val cond3 = isValidPrefix(str)
        lazy val cond4 = isValidPrefix(str.reverse)

        cond1 && cond2 && !cond3 && !cond4
      }
      def printBoolValue(b:Boolean) = if(b) println("True") else println("False")

      val in = io.Source.stdin.getLines()
      val inSize = in.take(1).next().toInt
      val strs = in.take(inSize)
      strs.map(isValidSequence(_)).foreach(printBoolValue)
    }
}
algorithm scala functional-programming

3 回答

  • 3

    作为另一个答案，这是一个更直接的解决方案，它可以缩短差异检查 .

    val valid = List("RGYBRGYB")      
val invalid = List("RGYBR", "RGYBY", "RGYBY", "RGYYB")

def checkBalls(s:String) = {
def differences(s:String, a:Char, b:Char) = {
  def differenceHelp(s:String, a:Char, b:Char, current:Int):Boolean = {
      if (current < -1 || current > 1) false
      else if (s.length == 0) true
      else differenceHelp(s.tail, a, b,
           if (s.head == a) current + 1 else if (s.head == b) current - 1 else current)
    }

  differenceHelp(s, a, b, 0)
}

lazy val cond1 = s.count('R'==) == s.count('G'==)
lazy val cond2 = s.count('Y'==) == s.count('B'==)
lazy val cond3 = differences(s, 'R', 'G')
lazy val cond4 = differences(s, 'Y', 'B')
cond1 && cond2 && cond3 && cond4
} 
valid.forall(checkBalls(_))                       //> res0: Boolean = true
invalid.forall(!checkBalls(_))                    //> res1: Boolean = true

    编辑：作为优化，我们可以将cond1作为cond3的一部分（和cond2作为cond4的一部分） . 当且仅当字符串末尾的计数为0时，每个都有相等的数字 . 我们可以检查差异，只有在这种情况下才会返回true . 所以这给了

    def checkBalls(s:String) = {
def differences(s:String, a:Char, b:Char) = {
  def differenceHelp(s:String, a:Char, b:Char, current:Int):Boolean = {
      if (current < -1 || current > 1) false
      else if (s.length == 0) (count == 0) // <- this line changed
      else differenceHelp(s.tail, a, b,
           if (s.head == a) current + 1 else if (s.head == b) current - 1 else current)
    }

  differenceHelp(s, a, b, 0)
}

lazy val cond3 = differences(s, 'R', 'G')
lazy val cond4 = differences(s, 'Y', 'B')
cond3 && cond4
}

    它像以前的版本一样通过了测试 . 通过一次调用 differences 进行R / G和Y / B检查可以稍快一点，但这看起来有点过度专业化 .

    回复于
  • 0

    所以，诀窍是首先检查最长的前缀 . 如果失败了，我们就完成了 . 否则，我们采用下一个最长的前缀并递归 . 如果我们到达空字符串，它会传递所有前缀，因此它是有效的 .

    def isValidPrefix(s: String): Boolean = 
if (s.length == 0)
  true
else if (!isValidCondition('R', 'G', groupByChars(s)))
  false
else isValidPrefix(s.init)
    回复于
  • 0

    如果需要，这是一个使用流的解决方案 .

    代码： -

    object RGYB extends App {

val validPattern = List(
        "RG","RYBG","RYGB","RBGY",
        "GR","GYBR","GYRB","GBRY",
        "YB","YRGB","YRBG","YGRB",
        "BY","BRGY","BRYG","BGYR"
        )

        val pattern ="RGRG"
        pattern.sliding(4).foreach { x1 =>
        val count = validPattern.filter { p1 => {
            x1.equalsIgnoreCase(p1)
        } 
        }.size
        if(count<1)
        {
            x1.sliding(2).foreach {
                x2=>
                val counter  = validPattern.filter { p2 => {
                    x2.equalsIgnoreCase(p2)
                } 
                }.size
                if(counter<1)
                {
                    println("false !! not valid due to "+x2);
                    System.exit(0)
                }
            }
            println("false !! not valid due to "+x1);
            System.exit(0)
        }
}

println("True !!"+pattern+" Is a valid string pattern")
}
    回复于

相关问题