72. 抢劫环形房子

RT

基于迭代器的版本,这样可兼容更多的集合类型:

  // Time: O(n), Space: O(1)
  def robO1[T](nums: Iterable[T])(implicit ev1: Numeric[T]): T = {
    require(nums != null && nums.nonEmpty)

    def rob(iter: Iterator[T]): T = {
      var prevPrev = ev1.zero
      var prev = ev1.zero
      for (n <- iter) {
        val cur = ev1.max(prev, ev1.plus(prevPrev, n))
        prevPrev = prev
        prev = cur
      }
      prev
    }

    val x = rob(nums.iterator.drop(1))
    val y = rob(nums.iterator.slice(0, nums.size - 1))
    ev1.max(x, y)
  }

测试:

  "Rob" should {
    "robO1(List(8.5, 1.1, 2.7, 9.6, 6.1))" in {
      val result = robO1(List(8.5, 1.1, 2.7, 9.6, 6.1))
      format(result) shouldBe 18.1
    }
    "robO1(Vector(8, 1, 2, 9))" in {
      robO1(Vector(8, 1, 2, 9)) shouldBe 10
    }
    "robO1(Array(8.1, 1.2, 2.2, 9.2))" in {
      val result = robO1(Array(8.1, 1.2, 2.2, 9.2))
      format(result) shouldBe 10.4
    }
  }

  private def format(d: Double) = BigDecimal(d).setScale(1, RoundingMode.HALF_UP).doubleValue