主页 / 问题 / 1560934
Accepted
Mr Babls
Asked:2024-01-10 03:43:01 +0000 UTC2024-01-10 03:43:01 +0000 UTC

为什么指针算法更快？

  • 772

大家好。任何人都可以帮助完成任务吗？有两个解决方案，第一个是我的，它没有通过测试时间：coins=[186, 419, 83, 408]，amount=6249。我注意到的第二件事是决策。

实际上，它们唯一的区别在于 dp 中的数据类型，在我的解决方案中它是 int，在第二个中有指向 int 的指针。第一个在时间限制下失败，第二个成功通过，上述测试的速度差异很大。第一个解决方案需要 30 秒以上，第二个解决方案需要 30 秒以上。我不明白为什么速度会有这么大的差异。我将感谢你的帮助

第一的：


func coinChange(coins []int, amount int) int {
 dp := make([]int, amount+1)
 for i := range dp {
  dp[i] = math.MaxInt32
 }
 var r func(need int) int
 r = func(need int) int {
  if need < 0 {
   return math.MaxInt32
  }
  if need == 0 {
   return 0
  }
  if dp[need] != math.MaxInt32 {
   return dp[need]
  }
  needCoins := math.MaxInt32
  for _, c := range coins {
   needCoins = min(needCoins, 1+r(need-c))
  }
  dp[need] = needCoins
  return needCoins
 }

 ans := r(amount)
 if ans == math.MaxInt32 {
  return -1
 }
 return ans
}

第二：


func coinChange(coins []int, amount int) int {
 dp := make([]*int, amount+1)
 var r func(need int) int
 r = func(need int) int {
  if need < 0 {
   return math.MaxInt32
  }
  if need == 0 {
   return 0
  }
  if dp[need] != nil {
   return *dp[need]
  }
  needCoins := math.MaxInt32
  for _, c := range coins {
   needCoins = min(needCoins, 1+r(need-c))
  }
  dp[need] = &needCoins
  return needCoins
 }

 ans := r(amount)
 if ans == math.MaxInt32 {
  return -1
 }
 return ans
}
алгоритм

1 个回答

  1. Best Answer

    区别在于如何存储有关无法解析金额的信息。

    1. 如果是指针：

      • 你写下dp[unsolvable] = &math.MaxInt32，
      • 当搜索过程中再次出现 时unsolvable，检查dp[unsolvable] != nil该值是否不为 nil，并r返回保存的结果。

    2. 如果是整数：

      • 你正在录音dp[unsolvable] = math.MaxInt32
      • 当在搜索过程中再次出现 时unsolvable，您检查dp[unsolvable] != math.MaxInt32，但缓存的值等于math.MaxInt32，并r再次尝试查找unsolvable硬币总和的分解。

    在整数选项中，您需要dp使用一个绝对不会作为返回值出现的数字进行初始化r，如下所示-1：

    func coinChange2(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = -1
    }
    var r func(need int) int
    r = func(need int) int {
        if need < 0 {
            return math.MaxInt32
        }
        if need == 0 {
            return 0
        }
        if dp[need] >= 0 {
            return dp[need]
        }
        needCoins := math.MaxInt32
        for _, c := range coins {
            needCoins = min(needCoins, 1+r(need-c))
        }
        dp[need] = needCoins
        return needCoins
    }

    ans := r(amount)
    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

    带指针的选项：0.000686374 秒

    选项coinChange2：0.000269819 秒

    • 7

相关问题