今天做力扣周赛,第一的easy题竟然比第二题难,第三题好不容易想到一个偷懒的方法,最后竟然超时了QAQ
又是掉排名的一天
明明已经过了287个样例,结果在第288个上竟然爆内存了= =
当时还没仔细看,后来发现竟然是这种少见的错误,一看,应该是字符串拼接上出了问题,平时习惯了用 += ,数据量小的时候没啥问题
但是遇到力扣这种恶心人的样例极端,果然就会寄
下面是原题
思路
菜如我只能想出前序遍历找到节点,至少这个还是没问题的
找出两个点后我就想记录一下吧,反正最后结果是个字符串,那就拿字符串记录一下,以根节点为出发点
目标节点在左边那就字符串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
}