V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xxxxware
V2EX  ›  问与答

leetcode-131 golang 关于本地运行和 leetcode vm 的疑问

  •  
  •   xxxxware · 2021-06-30 10:40:59 +08:00 · 784 次点击
    这是一个创建于 1002 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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 全局变量这一块的写法有误解呢

    谢谢大家

    9 条回复    2021-06-30 11:55:29 +08:00
    xxxxware
        1
    xxxxware  
    OP
       2021-06-30 10:44:09 +08:00
    可能 python 转 go 还是有一些作用域使用上的误区吧
    xxxxware
        2
    xxxxware  
    OP
       2021-06-30 10:50:01 +08:00
    以前 python 写算法写的还算稳, 转 golang 之后写的各种问题😂😂😂😂
    xxxxware
        3
    xxxxware  
    OP
       2021-06-30 10:54:49 +08:00
    thet
        4
    thet  
       2021-06-30 11:22:40 +08:00   ❤️ 1
    我用国际版测这段代码和 "ab" 这个 case 没问题啊,用的 Run Code 测的,如果是 Submit,你要在 partition 函数把 LRUCache 重置吧,不然会有影响
    Vegetable
        5
    Vegetable  
       2021-06-30 11:36:47 +08:00
    你这个 cache 应该是每一个 testcase 独立的,只要在 DFS 里边重置一下就行。

    但是,你这也不是 LRU 啊...
    xxxxware
        6
    xxxxware  
    OP
       2021-06-30 11:41:17 +08:00
    @thet 确实该重置。 疏忽了, 还是尽量避免在 leetcode 使用全局变量
    xxxxware
        7
    xxxxware  
    OP
       2021-06-30 11:41:52 +08:00
    @Vegetable 我随便取了个名字啦哈哈, 表示一个记忆优化
    xxxxware
        8
    xxxxware  
    OP
       2021-06-30 11:48:12 +08:00
    @Vegetable 我不太理解为什么要在 DFS 里面重置, 这个变量我只是为了记住字符串从 a 到 b 的函数结果而已。 只要 s 不变,我在 partition 里面重置就够了吧。
    xxxxware
        9
    xxxxware  
    OP
       2021-06-30 11:55:29 +08:00
    有个地方打错字了是
    if right < left {
    LRUCache[key] = false
    return false
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5394 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 09:10 · PVG 17:10 · LAX 02:10 · JFK 05:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.