Python程式：計算到達終點所需的步數

假設我們有一輛汽車，正在一維道路上行駛。目前我們的位置為0，速度為1。我們可以執行以下兩種操作之一。

  • 加速：位置 := 位置 + 速度；速度 := 速度 * 2 倒車：如果速度 > 0，則速度 := -1；否則速度 := 1。

我們需要找到至少到達目標所需的操作次數。

因此，如果輸入目標值為10，則輸出為7。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式dfs()。它將接收數字、成本、正數、負數和目標值。

    • 總成本 := 成本 + max(2 * (正數 - 1), 2 * (負數 - 1))

    • 如果總成本 >= 最小步數，則

      • 返回

    • 如果目標值為0，則

      • 最小步數 := min(最小步數, 總成本)

      • 返回

    • 步長 := (2^數字) - 1

    • 如果步長 * 2 < |目標值|，則

      • 返回

    • dfs(數字 - 1, 成本, 正數, 負數, 目標值)

    • dfs(數字 - 1, 成本 + 數字, 正數 + 1, 負數, 目標值 - 步長)

    • dfs(數字 - 1, 成本 + 數字 * 2, 正數 + 2, 負數, 目標值 - 步長 * 2)

    • dfs(數字 - 1, 成本 + 數字, 正數, 負數 + 1, 目標值 + 步長)

    • dfs(數字 - 1, 成本 + 數字 * 2, 正數, 負數 + 2, 目標值 + 步長 * 2)

  • 在主函式中，執行以下操作：

  • 最小步數 := 無窮大

  • hi := 1

  • 當 2^hi < 目標值 時，

    • hi := hi + 1

  • dfs(hi, 0, 0, 0, 目標值)

  • 返回最小步數

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, target):
      self.ans = int(1e9)
      hi = 1
      while (1 << hi) < target:
         hi += 1
      self.dfs(hi, 0, 0, 0, target)
      return self.ans
   def dfs(self, digit, cost, pos, neg, target):
      tot = cost + max(2 * (pos − 1), 2 * neg − 1)
      if tot >= self.ans:
         return
      if target == 0:
         self.ans = min(self.ans, tot)
         return
      step = (1 << digit) − 1
      if step * 2 < abs(target):
         return
      self.dfs(digit − 1, cost, pos, neg, target)
      self.dfs(digit − 1, cost + digit, pos + 1, neg, target − step)
      self.dfs(digit − 1, cost + digit * 2, pos + 2, neg, target − step * 2)
      self.dfs(digit − 1, cost + digit, pos, neg + 1, target + step)
      self.dfs(digit − 1, cost + digit * 2, pos, neg + 2, target + step * 2)
ob = Solution()
print(ob.solve(10))

輸入

10

輸出

7

更新於：2020-12-26

161 次檢視

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告