算法数据结构

「算法与数据结构真解」

以算法思想与数据结构为核心，贯穿不同编程语言的实现。这里不问语言门派，只探算法本源。

「数据结构篇」· 万物皆结构

📊 「刷题一统春秋」：

📊 「线性结构」：

「数组与链表」：内存的连续与离散之美

C 列表实战 —— 从指针到链表的演练记录。
计划：动态数组扩容策略、双向链表实现比较

「栈与队列」：后进先出与先进先出的哲学

计划：递归调用栈剖析、消息队列应用场景
计划：双端队列的妙用、优先队列实现方案

🌳 「树形结构」：

「二叉树」：二分思想的具象化

计划：二叉搜索树增删查、AVL树旋转平衡
计划：红黑树原理图解、B树在数据库中的应用

「堆结构」：优先级的艺术

计划：二叉堆实现、堆排序的原地版本
计划：Top K 问题的多种解法对比

🔑 「哈希世界」：

「哈希表」：从键到值的瞬间映射

计划：哈希冲突解决策略、布谷鸟哈希原理
计划：一致性哈希在分布式系统中的运用

🕸️ 「图论基石」：

「图的表示」：邻接矩阵与邻接表的抉择

路线规划 —— Grid-Based Route (Re-)Planning
计划：稠密图与稀疏图的存储优化

「算法篇」· 思维的模式

🔍 「搜索算法」：

「深度优先」：一条路走到黑的探索

计划：回溯法解数独、排列组合问题模板

「广度优先」：层层递进的扩张

计划：最短路径问题、状态空间搜索

🔄 「排序算法」：

「比较排序」：基于比较的秩序建立

计划：快速排序优化、归并排序的迭代实现
计划：堆排序的建堆技巧

「非比较排序」：突破O(nlogn)的界限

计划：计数排序的适用场景、基数排序的位数处理

🧩 「动态规划」：

「经典模型」：从斐波那契到背包问题

计划：状态定义技巧、状态转移方程推导
计划：背包九讲精要、区间DP的遍历顺序

「字符串DP」：编辑距离与最长公共子序列

计划：DNA序列比对中的DP应用

⚡ 「贪心算法」：

「局部最优」：何时贪心能得全局最优

计划：区间调度问题、霍夫曼编码构造

✂️ 「分治思想」：

「大事化小」：递归分解的艺术

计划：最近点对问题、矩阵乘法的Strassen算法

「高级专题」· 思想的融合

🎯 「算法设计范式」：

「双指针」：相向而行的智慧

计划：滑动窗口模板、快慢指针判环

「位运算」：0与1的魔法

计划：状态压缩技巧、位操作优化

📈 「复杂度分析」：

「时间空间」：算法效率的度量衡

计划：主定理的应用、均摊分析实例

「实战演练」· 知行合一

💻 「LeetCode精讲」：

「高频题目」：面试常考题型深度解析

计划：每题多语言实现、多种解法对比
C语言趣味算法 —— 汉诺塔、百鸡百钱、常胜将军、约瑟夫环。

🏆 「竞赛算法」：

「ACM模板」：竞赛常用算法模板库

计划：并查集优化、线段树懒更新

◀ 返回

汉诺塔

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从上往下按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新排在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

#include <stdio.h>

void move(char x, char y)
{
    static int cnt = 0;
    printf("%d %c => %c\n", ++cnt, x, y);
}

void hanno(int n, char a, char b, char c)
{
    if ( n == 1 )
        move(a, c);
    else {
        hanno(n-1, a, c, b);
        move(a, c);
        hanno(n-1, b, a, c);
    }
}

int main( void )
{
    hanno(3, 'A', 'B', 'C');
    return 0;
}

百鸡百钱

今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？

#include <stdio.h>

int main( void )
{
    int x;
    int y;
    int z;

    for (x=0; x<=100; x++)
    {
        for (y=0; y<=100; y++)
        {
            z = 100-x-y;
            if (z%3==0 && 5*x+3*y+z/3==100)
            {
                printf("公鸡%d,母鸡%d,小鸡%d\n",
                    x, y, z);
            }
        }
    }

    return 0;
}

常胜将军

现有21根火柴，两人轮流取，每人每次可以取走1至4根，不可多取，也不能不取，谁取最后一楰火柴谁输。请编写一个程序进行人机对弈，要求人先取，计算机后取；计算机一方为“常胜将军”

◀ 返回

Grid-Based Route (Re-)Planning

路线规划用于自主代理的导航，例如自动驾驶车辆、机器人和人类（考虑地图服务）基于网格的路由规划研究在二维空间中，将一个初始单元到一个目标单元的路由划分为阻塞或空的网格单元的问题.图1a显示了一个由10行10列组成的示例网格，第0行和第0列的初始单元格由I表示（是的，我们从零开始计算），第9行和第9列的目标单元格由G表示。绿色箭头显示了从I到G的计划移动，阻塞路段显示为橙色正方形的块。

路线规划图1

随着环境的变化，即块被移除或放置在一些新的单元上，计划的路由可能变得无效如图所示。例如一个机器人，按照计划的路线从图1a到达图1b网格中的单元格I和单元格g，它将被阻塞，故需要并重新规划绕过障碍物，如图1c所示。

Input Data

输入数据从文件中获取，如图2所示，第1行为表格大小，第2行为起始坐标,第3行为目的坐标。第三行开始为路线障碍节点坐标直到读取有“$”。之后行指示的是路线。

Reading and Analyzing Input Data

解决问题的第一步，读取文件数据并分析。将各节点关键信息如下方式显示:

[localhost]>ass2-soln<test0.txt ==STAGE 0======================================= The grid has 10 rows and 10 columns. The grid has 9 block(s). The initial cell in the grid is [0,0]. The goal cell in the grid is [9,9]. The proposed route in the grid is: [0,0]->[0,1]->[0,2]->[0,3]->[0,4]-> [1,4]->[2,4]->[3,4]->[4,4]->[5,4]-> [6,4]->[7,4]->[8,4]->[9,4]->[9,5]-> [9,6]->[9,7]->[9,8]->[9,9]. The route is valid!

Drawing and Replanning

进入第二阶段，当路线中遇到障碍时需要重新规划路线。首先打印路线如图3所示: 重新规划的路线的整体思路是：如何图1f所示，将遇到障碍点为原点扩散，离原点的距离。我们通过上下左右的方式遍历可访问的每个节点放入唯一队列当中，并判别放入的节点是否等于阻塞点的下个节点。如果相等则遍历结束，并获取了重新规划的路线。将队列的课访问路线添加到之前的路线当中。

coding

下列是我遍历路线的代码：

《算法圣子：我靠刷题一统春秋》

小说框架设定

世界观背景

时代：平行宇宙的春秋时期，算法为尊
核心规则：解决问题的算法复杂度决定社会地位
- O(1) → 圣人境界（可封侯拜相）
- O(log n) → 宗师境界（各国争抢）
- O(n) → 高手境界（一方豪强）
- O(n log n) → 才子境界（受人尊敬）
- O(n²)及以上 → 凡人境界

主角设定

姬玄（男主）：

表面身份：齐国放荡不羁的七王子
真实身份：穿越者+算法系统宿主
系统名称：“天机算法系统”
系统功能：每日发布算法题，完成可获得：
- 金币（春秋货币）
- 声望值（影响地位）
- 算法典籍（如《九章算法》《孙子算经·进阶版》）
- 特殊道具（“快速幂符”、“动态规划卷轴”）

势力划分

齐国：算法治国，推崇分治思想（男主所在）
秦国：暴力算法派，崇尚穷举之力
楚国：递归深修派，讲究大道归一
鲁国：伦理算法派，注重算法道德
江湖算法盟：散修高手聚集地

第一章：链表分治，初露锋芒

剧情大纲：

场景一：朝堂风波

齐王宫，算法殿。

齐王（面色凝重）：“今日天机系统出题——‘链表分区’。
谁能以最低复杂度解之，赏千金，封上卿！”

大殿中央，悬浮着天机系统的光幕：
【题目：给定链表头结点 head 和整数 x，将链表分隔成两部分，
使得所有小于 x 的节点都在大于等于 x 的节点之前】
【要求：保持节点初始相对位置】
【当前最优解：O(n²)，提供者：秦使商鞅】

秦使（傲然）：“我大秦‘双重遍历法’，虽复杂度稍高，
但气势磅礴！齐国可有更高明解法？”

满朝文武，面面相觑。

场景二：男主登场

“父王，儿臣有一解。”

众人回头，只见姬玄慵懒地倚在殿柱旁，
手中还把玩着酒樽，一副醉醺醺的模样。

齐王（怒）：“玄儿！朝堂重地，休得胡闹！”
宰相田忌（冷笑）：“七王子整日流连花丛，
也懂算法？莫要贻笑大方。”

姬玄（晃晃悠悠走上前）：“不就是个 O(n) 的事儿嘛...
给我两个虚拟头结点，一次遍历，原地修改...”

他随手拿起笔，在光幕上写下了代码框架：

场景三：算法演绎（关键剧情）

姬玄一边写，一边内心与系统对话：

【系统】：宿主正在解题“链表分区”
【系统】：检测到最优解法思路
【系统】：正在生成算法可视化...

突然，光幕上出现动画：
- 两个透明袋子（dummy1、dummy2）浮现在空中
- 链表节点如珍珠般被分类装入
- 指针如灵蛇游走，精准连接

姬玄（口中念念有词）：
“p1管小数袋，p2管大数袋，原链p来遍历...
遇小给p1，遇大给p2，断开重连莫要乱...”

【系统提示】：
时间复杂度：O(n)
空间复杂度：O(1)
击败率：100%

场景四：震惊朝野

光幕绽放金光！
【新纪录诞生！O(n)解法，提供者：齐国七王子姬玄】

秦使（震惊）：“一次遍历？！这...这是何等高深算法！”
田忌（难以置信）：“你...你何时修得如此造诣？”

姬玄（打个哈欠）：
“昨夜梦中有仙人传授，名曰‘双指针分区法’...
哦对了，这算法有几个要点：
1. 虚拟头结点，避免边界判空烦
2. 断开原链接，防止成环惹祸端
3. 最后要拼接，小数链表接大数前...”

【系统】：任务完成！
【奖励】：
- 金币+5000
- 声望+1000
- 获得“链表大师”称号
- 解锁新典籍《算法导论·春秋特别版》

场景五：暗中交易

当晚，姬玄府邸。

神秘商人（黑袍遮面）：
“殿下今日的O(n)解法，魏王愿出万金购买专利。”
姬玄（把玩着金币）：“不卖。但可以授权使用，
每月抽成...对了，你们魏国最近在搞‘合并K个有序链表’？
我这有O(n log k)的解法，要不要？”

商人（激动）：“要！多少钱都行！”
姬玄（微笑）：“钱？我要你们魏国的‘优先队列’秘法。
还有...听说你们有个算法天才叫庞涓？
让他来齐国交流交流...”

【系统】：触发支线任务“挖角庞涓”

场景六：女主登场

次日，算法学宫。

楚国公主芈月（女主）前来交流学习，
她以“递归解法”闻名列国。

芈月（挑衅）：“听闻七王子擅长迭代，
可敢与我比试‘二叉树直径’一题？”
姬玄（眼前一亮）：
“美...不对，芈月公主愿意赐教，荣幸之至。
不过赌点什么？我若赢了...公主陪我游临淄城三日？”
芈月（脸红）：“你若输了，当众承认楚国算法天下第一！”

【系统】：新任务发布
【题目】：二叉树直径
【特殊要求】：使用递归但空间复杂度O(1)
【奖励】：若胜利，获得“月公主的好感度+50”

后续章节框架

第二章：递归之美，情愫暗生

姬玄与芈月比试递归 vs 迭代
展示Morris遍历法，O(1)空间震惊四座
两人共同优化“汉诺塔问题”解法
感情线发展：从竞争对手到算法知己

第三章：列国算法大会

各国派遣算法天骄参赛
题目：“寻找旋转排序数组的最小值”
姬玄使用二分查找O(log n)碾压全场
揭露秦国使用“作弊算法”的阴谋

第四章：系统升级，危机显现

天机系统发布“NP完全问题”
列国无人能解O(n^k)以下
姬玄发现系统背后有神秘组织操控
获得“近似算法”特殊能力

第五章：算法治国

姬玄用“贪心算法”优化齐国赋税
“图论算法”解决各国交通问题
“动态规划”制定战略资源分配
引发“算法伦理”大辩论

每日更新机制

每章结构：

朝堂/江湖出题（现实问题转化为算法题）
各方势力解法展示（展示不同思路）
男主降维打击（给出最优解）
奖励与成长（系统奖励+势力变化）
感情/权谋支线（丰富剧情）
下集预告（明日题目剧透）

明日题目预告（第二章）：

【芈月的挑战】：
“给定一棵二叉树，求其直径（任意两节点间最长路径）”
【当前最佳】：O(n²)递归，楚国秘法
【姬玄目标】：O(n)一次遍历
【剧情冲突】：比试中有人暗中破坏，篡改测试用例...

算法知识点融入技巧：

招式命名：如“快慢指针法”叫“阴阳双鱼步”
境界比喻：递归深度=修仙层级
道具设计：哈希表=“天罗地网符”
比试场景：擂台赛=在线判题系统(OJ)

人物成长体系

姬玄的算法技能树：

基础层（已掌握）：
├── 链表操作（O(n)）
├── 双指针技巧
└── 虚拟头结点

进阶层（待解锁）：
├── 递归优化（尾递归）
├── 动态规划（背包问题）
└── 图论算法（最短路径）

宗师层（后期）：
├── 数论算法（加密解密）
├── 近似算法（NP问题）
└── 并行算法（多线程思想）

红颜知己线：

芈月（楚国公主）：递归专精，纯真傲娇
西施（越国间谍）：图论高手，身世神秘
郑旦（算法商人）：贪心算法，精明算计

写作建议

每章必备元素：

一道清晰算法题（可在章末附解法）
至少两个不同复杂度的解法对比
系统奖励的趣味描述
一个算法技巧的通俗解释
埋下后续剧情伏笔

俏皮话术示例：

“这时间复杂度，比我追姑娘还慢！”
“空间复杂度O(1)，这就叫‘一叶知秋’！”
“暴力解法？那是莽夫行为！”
“看我分治思想——‘分而治之，各个击破’！”

读者互动设计：

每章结尾让读者猜明日题目
征集现实问题转化为算法题
读者提供解法思路可成书中龙套角色