V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
magic3584
V2EX  ›  程序员

记一下刚才刷题给我的感受

  •  
  •   magic3584 · 2020-03-31 22:43:39 +08:00 · 1977 次点击
    这是一个创建于 1683 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本人菜鸟,之前刷题中断了,现在又开始从数据结构开始刷,最开始是二叉树。

    今天的题是 寻找最小公共父节点。由于我是在 explore 里学习的二叉树,刚好之前也写过层序遍历,所以就

    写出来如下实现:

    	func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    		guard let root = root, let p = p, let q = q else { return nil }
        
    		//最开始缺少起始点----------------------------
    		if isThereAWayFrom(p: p, to: q) {
    			return p
    		}
        
            if isThereAWayFrom(p: q, to: p) {
    			return q
    		}
            //最开始缺少终点----------------------------
          
    		var tmp = [TreeNode]()
    		tmp.append(root)
        
    		var lca = root
        
    		while tmp.count > 0 {
        
    			let popNode = tmp.removeFirst()
        
    			if isThereAWayFrom(p: popNode, to: p) && isThereAWayFrom(p: popNode, to: q) {
    				lca = popNode
    			}
        
        
    			if let left = popNode.left {
    				tmp.append(left)
    			}
        
    			if let right = popNode.right {
    				tmp.append(right)
    			}
    		}
        
                return lca
    	}
        
        func isThereAWayFrom(p: TreeNode?, to q: TreeNode?) -> Bool {
                if p?.val == q?.val {
                    return true
                }
        
                if p?.left == nil && p?.right == nil {
                    return false
                }
        
                return isThereAWayFrom(p: p?.left, to: q) || isThereAWayFrom(p: p?.right, to: q)
        }
    
    

    前几天刷题做出来以后就过去了,今天我看了一下最高赞的 Java 写法,只有 4 行,换成 swift 如下:

        func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
                if root == nil || root?.val == p?.val || root?.val == q?.val { return root }
                
                let left = lowestCommonAncestor(root?.left, p, q)
                let right = lowestCommonAncestor(root?.right, p, q)
                
                return left == nil ? right : right == nil ? left : root
        }
    
    

    虽然评论里说了最后一行不太容易理解应该展开写,但是这种思路我还是没想到的,感觉就是当头一棒。我写了那么多,别人 4 行就搞定了,这就是差距啊。。。以后自己写完还是应该多看看别人的思路与解法。

    还有一点就是,最开始我的写完以后会有超时,看了例子应该是只有左子树或者右子树的情况,后来就又补上了判断。

    最后还有一点想请教大佬,我分别提交自己和别人的解法后,时间差不多,但是内存会有差别。

    请问这点差别是一定范围内随机的,还是说我的就是快一点???(也不可能吧)

    最后附图:

    WX20200331-223042@2x.png

    8 条回复    2020-04-02 09:51:12 +08:00
    fishCatcher
        1
    fishCatcher  
       2020-03-31 22:45:36 +08:00 via iPhone
    leetcode 运行时间波动很大,要自己分析复杂度
    susecjh
        2
    susecjh  
       2020-03-31 22:47:06 +08:00
    多看看别人的思想,Runtime 不一定是正确的
    magic3584
        3
    magic3584  
    OP
       2020-03-31 22:49:37 +08:00
    @fishCatcher 我也觉得自己写的不可能快😂
    @susecjh 时间复杂度我可能不太把握的准确。。。
    ayase252
        4
    ayase252  
       2020-03-31 22:52:51 +08:00 via iPhone
    实际运行时间是有波动的,理论分析复杂度才是正解
    guolaopi
        5
    guolaopi  
       2020-03-31 22:54:08 +08:00
    #1 说得对。。同一套代码,刷新提交几次你会发现自己能打败自己。。。。
    hbolive
        6
    hbolive  
       2020-04-01 09:35:21 +08:00
    具体代码不做评论,但是短不一定好啊。。
    sunzongzheng
        7
    sunzongzheng  
       2020-04-01 10:11:20 +08:00
    想起了在学校 OJ 为了刷出机器最快执行纪录,写机器人循环提交同样代码的事情
    magic3584
        8
    magic3584  
    OP
       2020-04-02 09:51:12 +08:00
    @hbolive #6 也是,不过别的解法也是另一种思路
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   974 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 22:22 · PVG 06:22 · LAX 14:22 · JFK 17:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.