Hilda

「离开世界之前 一切都是过程」

018 二叉树遍历的非递归方法和复杂度分析

本文总结了用栈实现二叉树的三种遍历方式：先序、中序和后序。先序遍历用栈记录节点，先压右子节点再压左子节点。中序遍历利用栈模拟递归，访问左子树为空的节点。后序遍历可用两个栈（易理解，空间O(n)）或一个栈（空间O(h)，更复杂）实现。 遍历的时间复杂度为O(n)，空间复杂度通常为O(h)，Morris遍历可实现O(1)空间复杂度。

前置知识：二叉树、先序、中序、后序、栈 关于栈的笔记，整理如下： 013【入门】队列和栈-链表、数组实现 014【入门】队列和栈入门题目-栈和队列相互实现 015 最小栈-力扣155 建议：不要跳过 1）用栈实现二叉树先序遍历 2）用栈实现二叉树中序遍历 3）用两个栈实现二叉树后序遍历，好写但是不推荐，因为需要收集所有节点，最后逆序弹出，额外空间复杂度...

Posted by Hilda on March 29, 2025

016 双端队列-力扣641-双链表和固定数组实现

这篇博客介绍了循环双端队列的2种实现方式：双链表LinkedList和固定数组。双链表(自己实现)实现速度较快，但需手动编写节点类；LinkedList实现简单，但效率稍逊；固定数组实现适用于已知队列大小上限的情况，通过取模运算或等价逻辑循环利用数组空间。选择哪种实现取决于具体需求和性能考量。

641. 设计循环双端队列 1 双端队列介绍 既能头出也能头入，既能尾出也能尾入。 2 双链表实现双端队列 我自己预先写了一个解法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4...

Posted by Hilda on March 26, 2025

015 最小栈-力扣155

实现常数时间获取最小值的栈（MinStack）。主流方法是维护一个辅助栈记录每个位置的最小值，保证getMin()的O(1)复杂度。文章展示了基于Java内置栈、数组以及单链表三种实现方式，链表解法每个节点额外存储当前最小值。

概览： 155. 最小栈 力扣155. 最小栈 155. 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶...

Posted by Hilda on March 25, 2025

014【入门】队列和栈入门题目-栈和队列相互实现

本篇介绍了如何用栈模拟队列（均摊O(1)）和用队列模拟栈。栈模拟队列使用双栈倒数据，需注意倒数据时机和完整性。队列模拟栈，可用双队列或单队列实现，单队列每次push时需将之前元素重排。双端队列ArrayDeque也可高效实现栈。

概览 用栈实现队列 题目是：232. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty(...

Posted by Hilda on March 25, 2025

013【入门】队列和栈-链表、数组实现

本博客介绍了队列和栈的基本概念及其链表和数组实现。队列遵循先进先出（FIFO）原则，而栈遵循后进先出（LIFO）原则。重点讲解了数组实现队列时环形队列的设计，以及栈和队列的常见操作。最后通过力扣622题展示了环形队列的实际应用和解法。

概览 前置知识：链表 建议：比较初级，会的可以跳过，但是要注意环形队列用数组实现这个高频考点 1）队列的介绍 2）栈的介绍 3）队列的链表实现和数组实现 4）栈的数组实现 5）环形队列用数组实现 队列、栈、双端队列可以组成非常多重要的数据结构 将在【必备】课程里继续 本节涉及的力扣题目：622. 设计循环队列 队列的介绍 先到先出，尾巴进，头部出 【队列的实...

Posted by Hilda on March 25, 2025

012 链表入门题目-划分链表-哑节点

此博客讲解了链表分隔(力扣86)：将链表按给定值x分成小于x和大于等于x两部分，保持原相对顺序。核心是用两个哑节点分别指向两部分链表头，遍历原链表并按节点值连接到对应哑节点后，拼接两链表。补充题是力扣328-奇偶链表，思路类似。

概览： 前置知识：理解链表及其基本调整 建议：做过这个题86. 分隔链表的同学跳过 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前 你应当 保留 两个分区中每个节点的初始相对位置 链表题目在笔试、面试中的意义就是检验coding能力如何 更难的题目会在【必备】课程里讲述 86....

Posted by Hilda on March 21, 2025

011 链表入门题目-两个链表相加

本博客讲解了力扣2.两数相加，用链表逆序存储非负整数，并返回它们的和（链表形式）。解题思路是模拟手算加法，处理进位。代码部分提供了Java实现。此外，博客还补充了力扣67.二进制求和，思路类似。

概览： 前置知识：理解链表及其基本调整 建议：做过这个题2. 两数相加的同学跳过 给你两个 非空 的链表，表示两个非负的整数 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字 请你将两个数相加，并以相同形式返回一个表示和的链表 你可以假设除了数字 0 之外，这两个数都不会以 0 开头 链表题目在笔试、面试中的意义就是检验coding能力如何 ...

Posted by Hilda on March 21, 2025

010 链表入门题-力扣21-合并两个升序链表

这篇博客讲解了如何合并两个升序链表（LeetCode 21）。提供了递归和非递归两种解法。递归解法简洁，通过比较头节点大小，递归合并剩余部分。非递归解法则通过迭代，使用 pre 指针连接较小节点，最终合并两个链表。链表题能有效考察编码能力。

概览： 前置知识：理解链表及其基本调整 建议：做过这个题的同学跳过 将两个升序链表合并为一个新的 升序 链表并返回 新链表是通过拼接给定的两个链表的所有节点组成的 链表题目在笔试、面试中的意义就是检验coding能力如何 更难的题目会在【必备】课程里讲述 测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists...

Posted by Hilda on March 20, 2025

009 单双链表及其反转-堆栈诠释

这篇博客主要讲解链表相关知识，首先强调了按值传递与按引用传递的区别。然后介绍了单链表和双链表的定义，并重点通过 LeetCode 206和92 题详细讲解了链表反转的迭代解法，展示了使用指针调整链表结构的思路，最后给出了双链表反转的迭代代码。作者认为链表题是检验编码能力的重要手段。

概览： 1）按值传递、按引用传递 （我不知道为什么如此多的同学会犯这种错误，这完全是语言问题） 2）单链表、双链表的定义 3）根据反转功能，彻底从系统角度解释链表是如何调整的 链表题目在笔试、面试中的意义就是检验coding能力如何 更难的题目会在【必备】课程里讲述 1 按值传递、按引用传递 左老师讲了Java中的按值传递、按引用传递。结合我个人的一些理解，我将其书面的...

Posted by Hilda on March 20, 2025

023 随机快速排序

经典随机快速排序和用荷兰国旗问题优化后的随机快速排序。经典快排易受重复元素影响，优化后的版本通过荷兰国旗问题将数组划分为小于、等于、大于x三部分，提升效率。文章分析了普通快排和随机快排在不同情况下的时间和空间复杂度，强调随机选择的重要性，并指出随机快排的期望时间复杂度为O(n log n)，空间复杂度为O(log n)。

概览： 前置知识：讲解007-时间复杂度和空间复杂度-分析随机行为的时间复杂度的部分 007笔记 经典随机快速排序流程讲解 荷兰国旗问题优化随机快速排序流程讲解 荷兰国旗问题优化后的过程： 在当前范围上选择一个数字x，利用荷兰国旗问题进行数组的划分，<x =x >x 对<x范围重复这个过程，对>x范围重复这个过程 荷兰国旗问题的优化点：选出一个数字x，数...

Posted by Hilda on March 19, 2025

FEATURED TAGS
书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 Java基础 java集合 ollama工具 python爬虫
ABOUT ME

自由 解放

FRIENDS