Solution in Scala


  • 0
    F

    Step 1. build range map [To,Set(From)]
    Step 2. from last index search in the range map ['lastIndex', [fromIndex1,fromIndex2....]]
    Step 3. recursive find the least effort on find the solution

    trait LC45Solution {
    
    
      def jump(nums: Array[Int]): Int = {
    
        val indexFromToMap = mutable.HashMap[Int,mutable.LinkedHashSet[Int]]()
    
        val k = nums.length - 1
    
        for (i <- 0 until nums.length) {
    
          val from  = i
          var to = i + nums(i)
    
          if (to > k) {
              to = k
          }
    
          val list = indexFromToMap.get(to).getOrElse(mutable.LinkedHashSet[Int]())
              list.+(k)
    
    
        }
    
    
        findMinStepRecursive(indexFromToMap, k, k).getOrElse(-1)
      }
    
      def findMinStepRecursive(indexFromToMap:mutable.HashMap[Int,mutable.LinkedHashSet[Int]],
                               fromKey:Int,
                               remain:Int):Option[Int] = {
    
          if (remain == 0) {
              Some(1)
          }
    
          if (remain < 0) {
              None
          }
    
          var minJumpTimes = Integer.MAX_VALUE
    
          indexFromToMap.get(fromKey).get.map( to => {
    
              val jumpTimes = findMinStepRecursive(indexFromToMap, to, remain - fromKey).get
    
              if (jumpTimes != None && minJumpTimes > jumpTimes + 1) {
                  minJumpTimes = jumpTimes
              }
    
          })
    
          Some(minJumpTimes)
    
      }
    
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.