关于golang:golangleetcode初级环形链表

第一题 环形链表

题目信息

解题思路

首先还是思考最暴力的解法
由示例1可知,有两个节点同时指向第二个节点,从而在单链表的根底上造成了闭环。即pos0和pos3领有着雷同的next指针
由示例2可知,对于指向头节点的状况,有必要退出哑节点辅助比拟pos1的next指针
所以咱们只有比对一遍所有节点的next指针,找到指向雷同的节点即可
然而很显著,该思路的复杂度为O(n^2),个别状况下没有写进去的必要。

工夫复杂度高的起因次要是因为比照的过程过于麻烦,有太多重复性的操作。
对此再退出哈希表的概念优化一下,应用哈希表来存储所有曾经拜访过的节点

代码

func hasCycle(head *ListNode) bool {
    seen := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := seen[head]; ok {
            return true
        }
        seen[head] = struct{}{}
        head = head.Next
    }
    return false
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
起源:力扣(LeetCode)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

对于代码的map定义

复杂度剖析

工夫复杂度:O(N),其中 N 是链表中的节点数。最坏状况下咱们须要遍历每个节点一次。

空间复杂度:O(N),其中 N 是链表中的节点数。次要为哈希表的开销,最坏状况下咱们须要将每个节点插入到哈希表中一次。

另一种思路

快慢指针,永远滴神

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow, fast := head, head.Next
    for fast != slow {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
起源:力扣(LeetCode)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

工夫复杂度:O(N),其中 N 是链表中的节点数。

当链表中不存在环时,快指针将先于慢指针达到链表尾部,链表中每个节点至少被拜访两次。

当链表中存在环时,每一轮挪动后,快慢指针的间隔将减小一。而初始间隔为环的长度,因而至少挪动 N 轮。

空间复杂度:O(1)。咱们只应用了两个指针的额定空间。
这很酷

第二题 二叉树的最大深度

题目信息

解题思路

遍历一遍树的所有节点并记录他的深度即可
常见的树的遍历办法即为广度优先搜寻和深度优先搜寻
本题求解为二叉树的深度3,深搜显然更为简洁

代码

func maxDepth(root *TreeNode) int {

if root == nil {
    return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1

}

func max(a, b int) int {

if a > b {
    return a
}
return b

}

复杂度剖析

工夫复杂度:O(n),其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度:O(height),其中 height 示意二叉树的高度。递归函数须要栈空间,而栈空间取决于递归的深度,因而空间复杂度等价于二叉树的高度。

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年50元

阿里云限时活动-2核2G-5M带宽-60G SSD-1000G月流量 ,特惠价99元/年(原价1234.2元/年,可以直接买3年),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据