做手机网站一般要多少钱深圳大眼睛网站建设

做手机网站一般要多少钱,深圳大眼睛网站建设,河北seo平台,化妆品企业网站案例大全这道题充分利用了链表便于删除节点的特性#xff0c;以及题目给出的**“已排序”**这个关键前提。1. 解题思路#xff1a;一次遍历 由于链表是已排序的#xff0c;所有重复的元素在物理位置上一定是相邻的。 初始化#xff1a;让一个指针 cur 指向 head。比较与去重#x…这道题充分利用了链表便于删除节点的特性以及题目给出的**“已排序”**这个关键前提。1. 解题思路一次遍历由于链表是已排序的所有重复的元素在物理位置上一定是相邻的。初始化让一个指针cur指向head。比较与去重比较cur和cur.next的值。如果相等说明遇到了重复元素。我们只需要让cur.next cur.next.next相当于直接把中间那个重复的节点“跳过”了这就是链表删除节点的高效之处。如果不相等说明当前节点是唯一的将cur向后移动一位。循环终止当cur或cur.next为空时说明遍历结束。2. 代码实现 (Python)# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defdeleteDuplicates(self,head:Optional[ListNode])-Optional[ListNode]:# 如果链表为空或只有一个节点直接返回ifnothead:returnhead curhead# 只要当前节点和下一个节点都存在就继续比较whilecurandcur.next:ifcur.valcur.next.val:# 发现重复删除 next 节点# 直接指向下下个节点cur.nextcur.next.nextelse:# 不重复cur 指针后移curcur.nextreturnhead3. 深度解析为什么这题不需要dummy节点在上一题反转链表 II中由于头节点可能会被反转/改变我们需要dummy。但在本题中头节点永远不会被删除。即使后面有和头节点值一样的元素被删除的也是“后来的”重复项第一个节点始终会被保留。既然头节点固定我们直接返回head即可不需要额外的虚拟节点。4. 复杂度分析时间复杂度O(N)O(N)O(N)。我们只对链表进行了一次完整的线性扫描。空间复杂度O(1)O(1)O(1)。只使用了一个cur指针没有开辟额外空间。规则变了只要一个数字重复出现过它的所有副本都要被删除。例如1 - 2 - 2 - 3变成1 - 3中间的2全部消失。1. 核心突破为什么要用dummy节点在这道题中dummy节点是必须的。原因在于头节点可能会被删除。例如链表是1 - 1 - 2因为1是重复的它必须被删掉。如果没有dummy你很难处理“谁来当新的头”这个问题。有了dummy我们只需要最后返回dummy.next。2. 解题思路三步走设置哨兵创建dummy指向head令pre指向dummy。pre的作用是始终指向“确定不重复的最后一个节点”。寻找重复区间让cur指向pre.next。如果发现cur.val cur.next.val说明我们进入了一个重复区域。批量跳过利用一个while循环让cur一直向后移动直到跳过所有值相同的节点。最后让pre.next cur.next直接把这一整段重复的“一刀切掉”。3. 代码实现 (Python)classSolution:defdeleteDuplicates(self,head:Optional[ListNode])-Optional[ListNode]:# 1. 只要头节点可能被删就请出 dummydummyListNode(0,head)predummywhilepre.nextandpre.next.next:# 检查接下来两个节点的值是否相同ifpre.next.valpre.next.next.val:# 记录这个重复的值xpre.next.val# 只要接下来的节点值等于 x就不断跳过currpre.nextwhilecurrandcurr.valx:currcurr.next# 将 pre 的 next 指向第一个不等于 x 的节点pre.nextcurrelse:# 如果不重复pre 才可以放心前进一步prepre.nextreturndummy.next4. 关键逻辑点拨为什么pre不直接移动在发现重复时pre.next curr之后pre不能立即后移。因为新接上的这个curr节点可能又是另一组重复数字的开始。必须在下一轮循环中再次检查。对比 83 题83 题保留重复项中的一个。所以发现重复时cur.next cur.next.nextcur本身不动。82 题一个不留。所以需要一个内层循环把所有val相同的都走完然后让pre跨越式连接。5. 复杂度分析时间复杂度O(N)O(N)O(N)。虽然有嵌套循环但每个节点最多只被访问两次一次由curr扫描一次作为pre.next依然是线性时间。空间复杂度O(1)O(1)O(1)。通过这两道题83 和 82的对比感觉到dummy节点在处理“头节点可能消失”的问题时是多么好用了whilecurrandcurr.valx:这行代码体现了 Python 中的两个重要概念短路逻辑Short-circuiting和循环过滤。1. 拆解这行代码这行代码的作用是“只要当前节点存在并且它的值还是我们要找的重复值就一直往后走。”while: 开启一个循环。curr: 检查curr是否为None。如果curr已经走到了链表的末尾即空指针这个条件就是False。and: 逻辑与操作。curr.val x: 检查当前节点的值是否等于我们要删除的那个重复值x。2. 为什么要加curr and ...防止报错这是这段代码最关键的地方。在链表操作中我们经常会遇到空指针异常。如果链表的结尾正好是一串重复数字比如1 - 2 - 2 - None第一个2curr存在val是 2进入循环。第二个2curr存在val是 2进入循环。关键点此时curr移动到了None。如果没有curr and代码会直接执行None.val 2。这时候程序会崩溃抛出AttributeError: NoneType object has no attribute val。Python 的短路原则在A and B中如果A已经是False了Python 根本不会去看B是什么。所以先判断curr是否存在可以安全地保护后面的.val操作不报错。3. 这种语法的目的批量跳过在第 82 题中我们要“一个不留”地删除重复项。假设链表是pre - 2 - 2 - 2 - 3此时x 2。curr最初指向第一个2。while curr and curr.val x:会让curr像跳格子一样跳过第一个2跳过第二个2跳过第三个2最后curr停在了3的位置。退出循环后我们执行pre.next curr。效果就是pre的下一跳直接变成了3中间那串2被整体切除了。总结这是一种非常经典的**“过滤重复区间”**的写法用x记住那个“坏掉”的值。用while配合指针移动把所有等于x的连续节点全部走完。利用and的短路特性保证代码的健壮性鲁棒性。这种“先检查指针是否为空再访问指针成员”的习惯在写任何链表或树Tree的代码时都是必须具备的。