发现问题:
当用golang刷一道LeetCode题目时,78.子集,发现数据始终对不上,打印数据发现,居然有数据反复
错误代码:
var ans [][]intfunc dfs(nums []int, nowNums []int, l, r int) { ans = append(ans, nowNums) if l == r { return } for i := l; i < r; i++ { dfs(nums, append(nowNums, nums[i]), i+1, r) }}func subsets(nums []int) [][]int { ans = [][]int{} lenNums := len(nums) dfs(nums, []int{}, 0, lenNums) return ans}
排查问题发现,nowNums切片在appen进ans后,居然还产生了扭转,导致原先不同数据变为雷同
问题剖析:
当dfs的形参用这种时
dfs(nums, append(nowNums, nums[i]), i+1, r)
等价与上面这种
x := append(nowNums, nums[i])dfs(nums, x, i+1, r)
咱们都晓得,切片是会主动扩容的,以后容量有余时,会主动依据最佳状况进行扩容(这里就不开展了),然而要晓得一点,扩容是从新申请一块内存,也就是说之前的内存没有用上了,看看这个例子
代码:
s1 := make([]int, 1, 1)s1[0] = 10s2 := s1fmt.Printf("%p,%p\n", s1, s2)fmt.Println(s1, s2)s2 = append(s1, 10)fmt.Printf("%p,%p\n", s1, s2)fmt.Println(s1, s2)
输入:
能够发现,s1数组在s2批改后是没有变动的,因为s2从新申请了一块内存空间,没有用s1的,所以s1不受影响
哪这个不就保障了操作一个切片,另一个切片不受影响吗,跟问题有啥关系,甚至是解决了问题!
然而,这是在扩容的状况下,要是没扩容呢?
没扩容,s2的批改就会影响s1的数据,这就导致了方才题目的数据产生错乱,起因就是nowNums切片没有扩容,导致曾经进入ans的切片数据,在后续的递归中还会产生更改。
怎么解决这个问题,最好的办法是间接取出以后切片的数据,管它后续会不会产生更改
代码:
var ans [][]intfunc dfs(nums []int, nowNums []int, l, r int) { nowNumsCopy := make([]int, len(nowNums)) copy(nowNumsCopy, nowNums) // 间接copy出以后切片数据,不论它后续是否更新 ans = append(ans, nowNumsCopy) if l == r { return } for i := l; i < r; i++ { dfs(nums, append(nowNums, nums[i]), i+1, r) }}func subsets(nums []int) [][]int { ans = [][]int{} lenNums := len(nums) dfs(nums, []int{}, 0, lenNums) return ans}