[go]字符串拼接

今天做力扣周赛，第一的easy题竟然比第二题难，第三题好不容易想到一个偷懒的方法，最后竟然超时了QAQ

又是掉排名的一天

明明已经过了287个样例，结果在第288个上竟然爆内存了= =

当时还没仔细看，后来发现竟然是这种少见的错误，一看，应该是字符串拼接上出了问题，平时习惯了用 += ，数据量小的时候没啥问题

但是遇到力扣这种恶心人的样例极端，果然就会寄

下面是原题

5944. 从二叉树一个节点到另一个节点每一步的方向

思路

菜如我只能想出前序遍历找到节点，至少这个还是没问题的

找出两个点后我就想记录一下吧，反正最后结果是个字符串，那就拿字符串记录一下，以根节点为出发点

目标节点在左边那就字符串append一个L，右边就append一个R

然后就得到了起始节点对于目标节点的两个字符串

比如图中的3就是 “LL”,6就是“RL”

接下来我想，有没有这么一种可能，把它们两个的公共前缀都去点，然后把剩下的开始节点路径的字符全部替换成“U”，结果一试，嘿，还真过了不少，A了但是没完全A

最后改了一些逻辑，死于out of memory

string

虽然但是，思路是对的，就是字符串的拼接和修改出了问题

一般来说，很多语言中的字符串都是不可修改的，go的话在做题时候一般都是转成[]byte来操作的，但是对于这个题，显然不能预先分配好空间

而且递归的时候删除字符好像也有点麻烦

在百度一些方法后，发现其实go也有类似与java中的stringBuilder的集成工具 为数不多了属于是

通过bytes.NewBufferString 得到一个buffer或者声明一个bytes.Buffer

然后就可以使用

buffer.WriteByte('') :往缓冲中加入一个字符
buffer.Truncate(n int) :保留缓冲中前n个字符

其实感觉和自己用[]byte()也没多大区别，就是封装了一些遍历的方法

最后一发A

双百，可惜上午没改出来，话说那个卡内存的样例数据存下来竟然有1MB,就离谱

代码

func getDirections(root *TreeNode, startValue int, destValue int) string {

    var pathSta string
    var pathEnd string

    var dfs func(*TreeNode, bytes.Buffer, int, bool)

    dfs = func(rt *TreeNode, s bytes.Buffer, val int, tp bool) {
        if rt == nil {
            return
        }

        if rt.Val == val {
            if tp {
                pathSta = s.String()
            } else {
                pathEnd = s.String()
            }
        }
        if rt.Left != nil {
            s.WriteByte('L')
            dfs(rt.Left, s, val, tp)
            s.Truncate(s.Len() - 1)
        }
        if rt.Right != nil {
            s.WriteByte('R')
            dfs(rt.Right, s, val, tp)
            s.Truncate(s.Len() - 1)
        }

    }

    dfs(root, *bytes.NewBufferString(""), startValue, true)
    dfs(root, *bytes.NewBufferString(""), destValue, false)

    var i int

    fmt.Println(pathSta)
    fmt.Println(pathEnd)

    for i < len(pathSta) && i < len(pathEnd) {

        if pathSta[i] == pathEnd[i] {
            i++
        } else {

            break
        }

    }

    fmt.Println(i)
    pathSta = pathSta[i:]
    pathEnd = pathEnd[i:]
    fmt.Println(pathSta)
    fmt.Println(pathEnd)

    st := []byte(pathSta)

    for i := range st {
        st[i] = 'U'
    }

    return string(st) + pathEnd
}