文章列表 | Yuhan.Tech

动态连通性问题中的并查集

简介 union-find 是为了解决动态连通性问题而提出来的一个算法，而对应的数据结构被称为并查集，集即集合。动态连通性问题，可以联想到编程中两个变量名是否等价、集合中两个元素是否属于同一个集合、图中两个节点是否连通等。简单地说，给你一些相连的节点对，让你判断一个新的节点对是否相连。

四则运算表达式求值：中缀改后缀

简介在提到栈的应用时，有一个很典型的例子就是表达式求值。具体应用时体现在：中缀表达式转后缀表达式：运算符栈后缀表达式求值：操作数栈若直接进行中缀表达式求值，需同时操作两个栈，而将中缀表达式转为后缀表达式再求值时，每个步骤只需要专注于一个栈，操作起来更简单。本文就介绍这种方法。

KMP 算法：找子串的位置

简介字符串的算法中，有一个是做模式匹配，让你找子串的位置。如果用暴力解法，那就是一个双重 for 循环，以主串的每个字符为开头，往后走，看是不是跟子串完全一致。这样的算法时间复杂度是 $O(n \times m)$。有没有更好的算法呢？

Attention 要自由切换编程语言，必然要通过实践，编程语言之海浩瀚无边，本文会随着作者的实践而不断更新，敬请期待。基本思路熟悉各语言基本语法，怎么定义变量、函数、控制流等，这里有语法简介、数据结构等章节。识别各语言的特性，为什么 Python 有元组等，也就是要知道语言的特性和高级用法等。在熟悉基本语法时，要能搞清楚各编程语言怎么描述相同的功能的。在识别语言特性时，要能搞清楚各编程语言处理方式上的设计哲学。