Go语言切片Append操作的陷阱：理解底层数组与数据覆盖问题

package main

import "fmt"

func main() {
    route := []int{3, 7} // 假设len=2, cap=2
    // 首次append，如果容量不足，会扩容。
    // 假设此处route扩容后为 [3, 7, _, _] 且 cap=4
    // 此时 route 的底层数组为 [3, 7, _, _]

    nextA := 2
    nextB := 4

    // 第一次append
    pathA := append(route, nextA) // pathA: [3, 7, 2, _]
    fmt.Println("pathA check#1:", pathA) // 预期输出: [3 7 2]

    // 第二次append，仍然使用route作为基础切片
    pathB := append(route, nextB) // pathB: [3, 7, 4, _]
    fmt.Println("pathA check#2:", pathA) // 实际输出: [3 7 4] -- pathA被意外修改！
}

package main

import "fmt"

func extendPaths(triangle, prePaths [][]int) [][]int {
    nextLine := triangle[len(prePaths)]
    postPaths := [][]int{} // 初始化为空切片，避免第一个元素是零值

    for i := 0; i < len(prePaths); i++ {
        route := prePaths[i]
        nextA := nextLine[i]
        nextB := nextLine[i+1]

        // 1. 为 pathA 创建一个独立副本
        // make([]int, len(route), cap(route)+1) 确保新切片有足够的容量容纳一个新元素
        routeForA := make([]int, len(route), cap(route)+1)
        copy(routeForA, route)
        pathA := append(routeForA, nextA) // pathA 操作独立副本

        // 2. 为 pathB 创建另一个独立副本
        routeForB := make([]int, len(route), cap(route)+1)
        copy(routeForB, route)
        pathB := append(routeForB, nextB) // pathB 操作另一个独立副本

        postPaths = append(postPaths, pathA)
        postPaths = append(postPaths, pathB)
    }
    // 示例中 postPaths 的第一个元素可能是空切片，这里简化处理
    // 实际应用中需要根据具体逻辑调整
    if len(postPaths) > 0 && len(postPaths[0]) == 0 {
        postPaths = postPaths[1:]
    }
    return postPaths
}

func getSum(sumList []int) int {
    total := 0
    for _, v := range sumList {
        total += v
    }
    return total
}

func getPaths(triangle [][]int) {
    prePaths := [][]int{{triangle[0][0]}}
    for i := 0; i < len(triangle)-1; i++ {
        prePaths = extendPaths(triangle, prePaths)
        // 在这里进行路径筛选，以保持prePaths的精简
        // 示例代码中省略了原始的筛选逻辑，这里仅展示切片操作的修正
        fmt.Println("Filtered prePaths after iteration:", i, prePaths)
    }
    // 最终处理prePaths以找到最高成本路径
}

func main() {
    triangle := [][]int{{3}, {7, 4}, {2, 4, 6}, {8, 5, 9, 3}}
    getPaths(triangle)
}

package main

import "fmt"

func extendPathsOptimized(triangle, prePaths [][]int) [][]int {
    nextLine := triangle[len(prePaths)]
    postPaths := [][]int{}

    for i := 0; i < len(prePaths); i++ {
        route := prePaths[i]
        nextA := nextLine[i]
        nextB := nextLine[i+1]

        // 1. 为 pathA 创建一个独立副本
        newRouteForA := make([]int, len(route), cap(route)+1) // 确保有足够容量容纳nextA
        copy(newRouteForA, route)
        pathA := append(newRouteForA, nextA) // pathA 操作独立副本

        // 2. pathB 直接在原始 route 上操作
        // 此时 pathA 和 pathB 指向不同的底层数组，不会相互影响
        pathB := append(route, nextB)

        postPaths = append(postPaths, pathA)
        postPaths = append(postPaths, pathB)
    }
    if len(postPaths) > 0 && len(postPaths[0]) == 0 {
        postPaths = postPaths[1:]
    }
    return postPaths
}

func main() {
    triangle := [][]int{{3}, {7, 4}, {2, 4, 6}, {8, 5, 9, 3}}
    // 假设调用 extendPathsOptimized
    // getPaths(triangle) // 实际应用中会调用此函数
    fmt.Println("Optimized extendPaths demonstration (output will vary based on full logic)")
    // ...
}