发现问题:
当用golang刷一道LeetCode题目时,78.子集,发现数据始终对不上,打印数据发现,居然有数据反复
错误代码:
var ans [][]int
func 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] = 10
s2 := s1
fmt.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 [][]int
func 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
}
发表回复