package main
import (
"fmt"
)
var LRUCache map[[2]int]bool = make(map[[2]int]bool)
func isPali (s string, left, right int) bool {
key := [2]int{left, right} // get LRU CACHE
value, has := LRUCache[key]
if has {
return value
}
if right > left {
LRUCache[key] = false
return false
}
for ;left < right; left++ {
if s[left] != s[right] {
LRUCache[key] = false
return false
}
right --
}
LRUCache[key] = true
return true
}
func DFS(s string, start int, element []string, res *[][]string) {
if start >= len(s) {
// 指针越界 结束递归
t := make([]string, len(element)) // 新建一个和 temp 等长的切片
copy(t, element) // temp 还要在递归中继续被修改,不能将它的引用推入 res
*res = append(*res, t) // 将 temp 的拷贝 加入解集 res
return
}
for i:=start ; i < len(s) ; i++ {
if isPali(s,start,i) { // 如果满足了条件 那就切掉子树
element = append(element, s[start:i+1]) // 切割 开始递归
DFS(s, i+1, element, res) // 从 i 开始接着往深处探索
element = element[:len(element)-1] // 递归结束 撤销改动,下一轮迭代
}
}
}
func partition(s string) [][]string {
var res [][]string
DFS(s, 0, make([]string, 0), &res)
return res
}
func main() {
s := partition("ab")
fmt.Println(s)
fmt.Println(LRUCache)
}
我在本地运行是获得的结果是
1:[[a b]]
2:map[[0 0]:true [0 1]:false [1 1]:true]
但是在 leetcode 提交确得到了不一样的结果
1:[["a","b"],["ab"]]
2:map[[0 0]:true [0 1]:true [0 2]:false [1 1]:true [1 2]:false [2 2]:true]
可以确认的是 LRUCache 的问题,golang 小白是不是对 golang 全局变量这一块的写法有误解呢
谢谢大家
1
xxxxware OP 可能 python 转 go 还是有一些作用域使用上的误区吧
|
2
xxxxware OP 以前 python 写算法写的还算稳, 转 golang 之后写的各种问题😂😂😂😂
|
3
xxxxware OP |
4
thet 2021-06-30 11:22:40 +08:00 1
我用国际版测这段代码和 "ab" 这个 case 没问题啊,用的 Run Code 测的,如果是 Submit,你要在 partition 函数把 LRUCache 重置吧,不然会有影响
|
5
Vegetable 2021-06-30 11:36:47 +08:00
你这个 cache 应该是每一个 testcase 独立的,只要在 DFS 里边重置一下就行。
但是,你这也不是 LRU 啊... |
8
xxxxware OP @Vegetable 我不太理解为什么要在 DFS 里面重置, 这个变量我只是为了记住字符串从 a 到 b 的函数结果而已。 只要 s 不变,我在 partition 里面重置就够了吧。
|
9
xxxxware OP 有个地方打错字了是
if right < left { LRUCache[key] = false return false } |