Uwakeme

一、动态规划概述动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为更简单的子问题来解决问题的方法。它是一种强大的算法设计技术，特别适用于具有重叠子问题和最优子结构性质的问题。 （一）算法适用场景动态规划主要适用于以下场景： 最优化问题（求最大值、最小值） 计数问题（求方案数） 具有重叠子问题特性的问题 具有最优子结构特性的问题 （二）算法基本思想动态规划的核心思想是： 将原问题分解为相互依赖的子问题 求解每个子问题仅一次，并将结果存储在表格中 自底向上地构建解决方案 通过组合子问题的解来得到原问题的解 二、动态规划的关键要素（一）最优子结构如果问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质。这是应用动态规划的必要条件。 例如，最短路径问题具有最优子结构：如果从A到C的最短路径经过B，那么A到B的这段路径一定是A到B的最短路径。 （二）重叠子问题当问题的递归算法会重复计算相同的子问题时，我们称该问题具有重叠子问题特性。动态规划通过存储已解决的子问题的结果来避免重复计算。 例如，计算斐波那契数列时，递归算法会重复计算相同的子问...

前言《算法图解》第六章为我们介绍了一种基础且强大的图搜索算法——**广度优先搜索 (Breadth-First Search, BFS)**。这种算法能够系统地探索图中的节点，常用于解决两类核心问题：一是判断从一个节点到另一个节点是否存在路径；二是在无权图中找到两个节点之间的最短路径。本笔记将深入探讨图的基本概念、BFS 的工作原理、其实现方式以及相关的性能分析。 一、图（Graph）简介在讨论 BFS 之前，我们需要理解什么是图。 （一）什么是图图是一种由节点 (Nodes 或 Vertices) 和连接这些节点的边 (Edges) 组成的数据结构。图用于表示各种实体之间的关系。 节点：代表图中的事物或点。例如，在社交网络中，节点可以代表人；在地图中，节点可以代表城市。 边：代表节点之间的连接或关系。例如，在社交网络中，边可以表示朋友关系；在地图中，边可以表示城市间的道路。 （二）有向图与无向图 **有向图 (Directed Graph)**：图中的边具有方向性。如果存在一条从节点 A 指向节点 B 的边，意味着关系是从 A 到 B，但不一定是从 B 到 A。例如，Twi...

前言在上一章中，我们学习了二叉搜索树(BST)的基本概念和操作。虽然BST在平均情况下提供了O(log n)的搜索、插入和删除效率，但在最坏情况下（如按顺序插入数据），它可能退化为链表，导致操作效率降为O(n)。为了解决这个问题，《算法图解》第八章介绍了平衡树的概念和几种主要的平衡树结构，这些结构能够在各种情况下保持较好的平衡性，确保操作的高效性。 一、平衡树的基本概念（一）什么是平衡树平衡树是一种特殊的二叉搜索树，它通过某些机制来保持树的平衡，避免树向一侧过度生长。所谓”平衡”，通常是指树的左右子树高度大致相同，或者满足某些特定的平衡条件。 平衡树的目标是确保树的高度接近于log n（其中n是节点数），这样可以保证基本操作（查找、插入、删除）的时间复杂度为O(log n)，即使在最坏情况下也是如此。 （二）为什么需要平衡树回顾上一章中提到的问题：当按顺序（如升序或降序）向BST中插入数据时，树会变得极度不平衡，形成一个链表状结构： 1234567891 \ 2 \ 3 \ 4 \ 5 在这种情况下，查找、插入和删除操作的...

前言《算法图解》第五章为我们介绍了计算机科学中一种极为重要且应用广泛的数据结构——散列表（Hash Table），在 Python 中我们更熟悉它的名字：字典（Dictionary）。散列表以其惊人的平均 O(1) 时间复杂度进行查找、插入和删除操作而闻名，使其成为许多高效算法和系统的基石。本篇笔记将深入探讨散列表的内部工作机制，包括核心的散列函数、如何处理不可避免的冲突，以及影响其性能的关键因素和常见应用场景。 一、散列函数 (Hash Functions)散列函数是散列表的心脏。简单来说，散列函数是一个特殊的函数，它接收任意大小的输入数据（称为”键”或”Key”），并将其转换为一个固定大小的数字，这个数字通常用作数组的索引。 （一）散列函数的主要特性一个好的散列函数应具备以下关键特性： **一致性 (Consistent)**：对于相同的输入键，散列函数必须始终返回相同的输出（散列值/索引）。如果输入 ‘apple’ 得到索引 3，那么每次输入 ‘apple’ 都应该得到 3。 **良好的映射性 (Good Distribution)**：理想情况下，散列函数应将...

一、迪杰斯特拉算法概述迪杰斯特拉算法（Dijkstra’s algorithm）是一种解决带权有向图上单源最短路径问题的贪心算法，由荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）于1956年提出。该算法常用于路由协议，也可以用作其他图算法的子程序。 （一）算法适用场景迪杰斯特拉算法适用于： 带权有向图（每条边都有权重） 所有权重都为非负值（不能有负权边） 需要找出从一个顶点到图中所有其他顶点的最短路径 （二）算法基本思想迪杰斯特拉算法的核心思想是： 从起点开始，逐步扩展到图中的其他顶点 每次选择当前未访问的距离最小的顶点 更新该顶点的所有邻居的距离值 重复这个过程，直到所有顶点都被访问过 二、算法步骤详解（一）算法流程 创建两个集合：已访问顶点集合和未访问顶点集合 将起点的距离设为0，其他顶点的距离设为无穷大 重复以下步骤，直到所有顶点都被访问：a. 从未访问顶点中选择距离最小的顶点b. 将该顶点标记为已访问c. 更新该顶点的所有邻居的距离 （二）图示说明以《算法图解》中的例子为例，假设我们要找从起点到终点的最短路径： 起点的距离为0，其...

前言继第一章介绍了算法的基本概念和二分查找后，《算法图解》第二章将带领我们进一步探索数据组织的方式，引入了两种基础且重要的数据结构：数组（Array）和链表（Linked List）。理解它们的特性和区别对于后续学习更复杂的算法至关重要。此外，本章还介绍了第一个排序算法——选择排序（Selection Sort）。笔者将结合书中内容和个人理解，对本章知识点进行梳理。 一、内存工作原理简介在探讨数组和链表之前，我们有必要简单了解一下计算机是如何存储数据的。想象一下，计算机的内存就像一个巨大的柜子，里面有很多抽屉。每个抽屉都有编号（内存地址），可以存放数据。 存储数据：当程序需要存储数据时，会向操作系统请求一块内存空间。操作系统找到合适的”抽屉”并将数据放进去。 读取数据：当程序需要读取数据时，会根据内存地址找到对应的”抽屉”，取出里面的数据。 这种机制是数组和链表实现的基础。 二、数组（Arrays）数组是一种将相同类型的元素存储在连续内存空间中的数据结构。这意味着数组中的所有元素都是紧挨着存放的。 （一）数组的特点 连续存储：这是数组最核心的特点。由于元素是连续存储的，我们可...

前言《算法图解》第三章为我们揭示了编程中一个强大且富有魅力的概念——递归（Recursion）。递归是一种解决问题的方法，它将问题分解为规模更小的相同问题，直到问题小到可以轻松解决。理解递归对于掌握更高级的算法（如快速排序、归并排序等）至关重要。本篇笔记将跟随书中的脚步，探索递归的原理、运作方式以及其在编程实践中的应用。 一、什么是递归递归，简单来说，就是一个函数直接或间接调用自身的过程。书中用了一个生动的例子来解释：你找到一个上了锁的神秘手提箱，奶奶告诉你钥匙在另一个盒子里。你打开那个盒子，发现里面又是一个盒子… 这个寻找钥匙的过程，就是递归的体现——不断重复相同的动作（打开盒子），直到找到钥匙（达到某个终止条件）。 在编程中，递归函数会不断地调用自己，每次调用处理问题的一个更小的部分，直到达到一个无法再分解的”基本情况”。 二、递归函数的两个基本要素每个递归函数都必须包含两部分，以确保其能正确执行并最终停止： 基线条件（Base Case）：这是递归函数停止调用自身并开始返回结果的条件。没有基线条件，递归函数就会无限地调用下去，直到耗尽所有内存（导致栈溢出）。基线条件是递归...

前言《算法图解》是一本入门算法的优秀读物，以图文并茂的方式讲解了各种基础算法。笔者最近在学习此书，特此记录学习笔记。本篇笔记主要记录第一章的核心内容，包括什么是算法、二分查找的思想及其实现、以及衡量算法效率的大O表示法。 一、什么是算法算法（Algorithm）是一组用于完成特定任务的指令。简单来说，就是解决问题的方法和步骤。一个好的算法，不仅要能够正确解决问题，还要追求更高的效率，即用更少的时间和更少的内存。 二、二分查找二分查找（Binary Search）是一种高效的查找算法，但它有一个重要的前提：输入的数据必须是有序的。 （一）算法原理二分查找的原理非常简单。想象一下在电话簿里找一个名字，或者在字典里查一个单词。我们通常不会从第一页开始逐个查找，而是会： 打开书大约中间的一页。 比较中间的条目与我们要查找的目标。 如果目标条目在当前条目的前面，则在书的前半部分重复此过程。 如果目标条目在当前条目的后面，则在书的后半部分重复此过程。 重复以上步骤，直到找到目标或确定目标不存在。 这个过程就是二分查找。每次查找都将搜索范围缩小一半，因此效率很高。 例如，在一个包含 100...

前言在前面的章节中，我们学习了数组、链表、散列表等基本数据结构，以及一些基础算法。本章将介绍一种非常重要的数据结构——树(Tree)，特别是二叉搜索树(Binary Search Tree)。树结构在计算机科学中应用广泛，从文件系统到数据库再到人工智能，都能看到树的身影。《算法图解》第七章深入浅出地介绍了树的基本概念、实现和应用，帮助读者理解这一关键数据结构。 一、树的基本概念（一）什么是树树是一种分层数据的抽象模型，它由一系列节点组成，这些节点通过边相连。树具有以下特性： 树有一个根节点(Root)，它是树的起始点 除根节点外，每个节点都有且仅有一个父节点 每个节点可以有零个或多个子节点 节点之间没有循环连接（这意味着树是无环的） 没有子节点的节点称为叶节点(Leaf) 树的常见术语： 节点(Node): 树中的基本单位，包含数据和指向其他节点的链接 边(Edge): 连接两个节点的线 根(Root): 树顶部的节点，是树中唯一没有父节点的节点 叶节点(Leaf): 没有子节点的节点 父节点(Parent): 有子节点的节点 子节点(Child): 有父节点的节点 兄弟节...

前言《算法图解》(Grokking Algorithms) 是由 Aditya Y. Bhargava 编写的一本算法入门书籍，以其通俗易懂的语言和生动形象的图解闻名。本书特别适合算法初学者，通过简明的解释和丰富的插图，将复杂的算法概念转化为易于理解的内容。笔者通过系统学习这本书，记录了各章节的学习笔记，本文作为总结和导航，帮助读者快速了解全书内容并方便查阅各章节的详细笔记。 一、《算法图解》整体内容概述《算法图解》从基础的算法概念开始，逐步深入到更复杂的算法思想，全书共13章，涵盖了以下核心内容： （一）基础算法与数据结构 二分查找：一种针对有序数组的高效查找算法，时间复杂度为O(log n) 数组与链表：两种基本数据结构，各有优缺点 递归：一种解决问题的重要思想，通过函数调用自身来解决问题 栈：一种后进先出(LIFO)的数据结构，用于实现递归 **散列表(哈希表)**：通过键值对实现快速查找的数据结构 （二）排序算法 选择排序：一种简单直观的排序算法，时间复杂度为O(n²) 快速排序：一种高效的分治排序算法，平均时间复杂度为O(n log n) 归并排序：另一种分治排序算法...