牛客159707358号

分类

/ 注册

TA的专栏 40篇文章 0人订阅

剑指offer回顾

40篇文章 116人学习

全部文章（共99篇）

题解 | 滑动窗口的最大值 JZ73 双头队列实现单调极值队列来自专栏

栈思想和含有min函数的栈那像：保存极值，当极值更新为新的数字或者追溯到上一个极值，追溯+时间O(n) 意味着不能遍历，每次移动都要保存当前情况下的极值。窗口移动时，如果过期元素恰好为极值，那么重新寻找，不然新元素只需要和v的尾部元素比较，尾部元素代表i~i+size-2的最大值。 class So...

2025-03-17

0 103

题解 | 栈的压入、弹出序列 JZ31 栈进出顺序问题来自专栏

栈进出模拟直接用一个栈去模拟，而不是探究规律注意判断都为空情况考虑栈为空情况 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV...

2025-03-17

0 92

题解 | 翻转单词序列 JZ73 进出栈法/二次字符串翻转来自专栏

进出栈法：栈完成倒序利用栈来完成字符串的倒序字符串的切片用substr（pos,len)，切片出从pos开始的长度为len出的新字符串原字符串加" "使得最后字符串片段不用特殊处理别忘加空格，最后一个切片不用加 class Solution { public: strin...

2025-03-17

0 69

题解 | 包含min函数的栈 JZ30 双栈实现最小值来自专栏

双栈法一个栈保证栈的先入后出，一个栈每次压栈最小值，保证min。同时压栈可以保证每个栈的元素个数相同，栈2的栈顶元素始终为当前元素的最小值的。避免开一个全局变量保存最小值，直接用栈顶元素作为当前最小值，同时考虑栈2为空的情况。 class Solution { public: stack&l...

2025-03-17

0 82

题解 | 用两个栈实现队列 JZ9 将进出队列过程分离来自专栏

双栈表示队列将进出过程分离，不需要一直保持先进先出的顺序，在出的时候保存即可 class Solution { public: void push(int node) { stack1.push(node); } int pop() { if...

2025-03-17

0 92

题解 | 复杂链表的复制来自专栏

双指针法双指针法一克隆节点在原节点后，遍历链表构建随机映射关系，拆分节点。新链表的随机节点可以通过原链表随机关系获得。核心：new_cur->random=cur->random->next。时间/空间: O(n)/O(n) #include <cstdlib> cla...

2025-03-17

0 79

题解 | 链表中环的入口结点快慢指针法

快慢指针法圆环相遇问题，用快慢指针，快指针步长为2，慢指针步长为1，如果存在环必然相遇。有画图可得当，相遇时，快指针到环的入口节点距离和头节点到入口节点距离相同，此时相遇点和头节点同步长出发，必然相遇在入口节点。注意非环节点时判断，快指针移动时判断本身节点以及下一个节点是否为空。 class Sol...

2025-03-16

0 98

题解 | 删除链表的节点遍历法，构建新头节点

遍历法构建一个新的头节点，使得头节点和非头节点的值删除一样核心在于front->next=cur->next，因此只要两个节点并保持步长相差一 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

2025-03-16

0 116

题解 | 链表中倒数最后k个结点快慢指针法/递归法/遍历法

快慢指针法快指针比慢指针快k步，当快指针为空时，慢指针刚好指向倒数第k个快慢指针的思路来源于相对距离，倒数第k个->两个指针相差k步保持不变判断长度是否符合要求，应该用k是否等于0而不是快指针为空，当第一个就是倒数第k个，快指针为空符合要求。 class Solution { public: ...

2025-03-16

0 65

题解 | 两个链表的第一个公共结点双指针法

双指针法，当两个指针相遇时走的距离一样。一个指针走到空时，从另外一端开始走。两个指针会最终会在公共节点或者空指针相遇移动到新头节点属于一步，和移动到下一个节点地位等价，所以要并列处理如果先移动后判断为空时移动，则错过两个节点都为空的情况如果先判断再为空，相当于走了两步，一步到新头节点，一步到新头节点...

2025-03-16

0 98