How to make a static local variable in golang

huangapple
go评论145阅读模式
英文:

How to make a static local variable in golang

问题

描述：编写一个函数canSum(targetSum, numbers)，该函数接受一个目标和一个数字数组作为参数。

该函数应返回一个布尔值，指示是否可以使用数组中的数字生成目标和。

您可以根据需要多次使用切片的元素。
假设所有输入数字都是非负的。

  1. package main
  3. import "fmt"
  5. func canSum(targetSum int, numbers ...int) bool {
  6. 	if targetSum == 0 {
  7. 		return true
  8. 	}
  9. 	if targetSum < 0 {
  10. 		return false
  11. 	}
  12. 	for index := 0; index < len(numbers); index++ {
  13. 		if canSum(targetSum-numbers[index], numbers...) == true {
  14. 			return true
  15. 		}
  16. 	}
  17. 	return false
  18. }
  20. //var memo = map[int]bool{} //Getting wrong values due to shared function scope from package scope
  21. func memo_canSum(targetSum int, numbers ...int) bool {
  22. 	memo := map[int]bool{} //Defeats dp func since we continue to reinitialize during recursive calls
  23. 	if _, exists := memo[targetSum]; exists {
  24. 		return memo[targetSum]
  25. 	}
  27. 	if targetSum == 0 {
  28. 		return true
  29. 	}
  30. 	if targetSum < 0 {
  31. 		return false
  32. 	}
  33. 	for index := 0; index < len(numbers); index++ {
  34. 		if memo_canSum(targetSum-numbers[index], numbers...) == true {
  35. 			memo[targetSum] = true
  36. 			return memo[targetSum]
  37. 		}
  38. 	}
  39. 	memo[targetSum] = false
  40. 	return false
  41. }
  43. func main() {
  45. 	//Non-Dp Solution
  46. 	fmt.Println(canSum(21, 2, 4, 8))
  47. 	fmt.Println(canSum(80, 2, 4, 8))
  48. 	fmt.Println(canSum(300, 7, 14))
  50. 	//Dp Solution
  51. 	fmt.Println(memo_canSum(21, 2, 4, 8))
  52. 	fmt.Println(memo_canSum(80, 2, 4, 8))
  53. 	fmt.Println(memo_canSum(300, 7, 14))
  54. }

所以我在使用golang编程时遇到了一个问题，如果我在函数外部声明我的记忆化映射，则所有函数调用共享同一个映射，这会导致结果出错。
如果我在函数内部声明映射，则每次递归调用都会重新初始化映射。有没有办法使映射成为静态局部变量？

英文: 
  1. /*
  2. Description: Write a function canSum(targetSum, numbers) that takes in a
  3. targetSum and an array of numbers as arguments.
  4. The function should return a boolean indicating whether or not it is possible  
  5. to generate the targetSum using numbers from the array
  6. You may use an element of the slice as many times as needed.
  7. Assume that all input numbers are non-negative.
  8. */
  1. package main
  2. import &quot;fmt&quot;
  3. func canSum(targetSum int, numbers ...int) bool {
  4. if targetSum == 0 {
  5. return true
  6. }
  7. if targetSum &lt; 0 {
  8. return false
  9. }
  10. for index := 0; index &lt; len(numbers); index++ {
  11. if canSum(targetSum-numbers[index], numbers...) == true {
  12. return true
  13. }
  14. }
  15. return false
  16. }
  17. //var memo = map[int]bool{} //Getting wrong values due to shared function scope from package scope
  18. func memo_canSum(targetSum int, numbers ...int) bool {
  19. memo := map[int]bool{} //Defeats dp func since we continue to reinitialize during recursive calls
  20. if _, exists := memo[targetSum]; exists {
  21. return memo[targetSum]
  22. }
  23. if targetSum == 0 {
  24. return true
  25. }
  26. if targetSum &lt; 0 {
  27. return false
  28. }
  29. for index := 0; index &lt; len(numbers); index++ {
  30. if memo_canSum(targetSum-numbers[index], numbers...) == true {
  31. memo[targetSum] = true
  32. return memo[targetSum]
  33. }
  34. }
  35. memo[targetSum] = false
  36. return false
  37. }
  38. func main() {
  39. //Non-Dp Solution
  40. fmt.Println(canSum(21, 2, 4, 8))
  41. fmt.Println(canSum(80, 2, 4, 8))
  42. fmt.Println(canSum(300, 7, 14))
  43. //Dp Solution
  44. fmt.Println(memo_canSum(21, 2, 4, 8))
  45. fmt.Println(memo_canSum(80, 2, 4, 8))
  46. fmt.Println(memo_canSum(300, 7, 14))
  47. }

So I've ran into an issue while programming with golang, if i declare my memoized map outside of my function then all function calls share the same map and it leads to error's with the results.
If i declare the map inside the function then each recursive call reinitializes the map. Is there any way to make the map a static local variable?

答案1

得分: 1

使用map参数编写一个不同的函数，并在其中进行递归。最初在memo_canSum函数中调用该函数，并声明一个新的map。

  1. func memo_canSum(targetSum int, numbers ...int) bool {
  2.     memo := map[int]bool{} //由于来自包范围的共享函数作用域，导致获取错误的值
  3.     return momoWithMap(memo, targetSum, numbers...)
  4. }
  6. func momoWithMap(memo map[int]bool, targetSum int, numbers ...int) bool {
  7.     if val, exists := memo[targetSum]; exists {
  8.         return val
  9.     }
  11.     if targetSum == 0 {
  12.         return true
  13.     }
  14.     if targetSum < 0 {
  15.         return false
  16.     }
  17.     for index := 0; index < len(numbers); index++ {
  18.         if momoWithMap(memo, targetSum-numbers[index], numbers...) == true {
  19.             memo[targetSum] = true
  20.             return true
  21.         }
  22.     }
  23.     memo[targetSum] = false
  24.     return false
  25. }
英文:

Write a different function with map parameter and do recursive in it. Initially call that function inside your memo_canSum function with declaring new map.

  1. //var memo = map[int]bool{} //Getting wrong values due to shared function scope from package scope
  2. func memo_canSum(targetSum int, numbers ... int) bool {
  3. memo := map[int]bool{} //Defeats dp func since we continue to reinitialize during recursive calls
  4. return momoWithMap(memo, targetSum, numbers...)
  5. }
  6. func momoWithMap(memo map[int]bool, targetSum int, numbers ... int) bool{
  7. if _, exists:=memo[targetSum]; exists{
  8. return memo[targetSum]
  9. }
  10. if targetSum == 0 {
  11. return true
  12. }
  13. if targetSum &lt; 0{
  14. return false
  15. }
  16. for index:= 0; index &lt; len(numbers); index++{
  17. if momoWithMap(memo, targetSum - numbers[index], numbers...) == true {
  18. memo[targetSum] = true
  19. return true
  20. }
  21. }
  22. memo[targetSum] = false
  23. return false
  24. }

huangapple
  • 本文由 发表于 2021年5月21日 04:40:01
  • 转载请务必保留本文链接：https://go.coder-hub.com/67627633.html
  • dynamic-programming
  • go
  • memoization
  • recursion
  • static-variables
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定