二分查找 二分查找又叫折半查找，是在有序列表的基础上进行查找，每次查找可以筛掉一半的元素。 算法步骤 以升序数列$L[0…n-1]$为例，假设要查找的数为$x$： 让$x$与数列中间位置的元素$L[\lfloor \frac n2 \rfloor]$进行比较，如果相等则返回该元素下标，否则： 如果$x$比中间元素小，递归地对中间元素左边的数列（比二分查找小的元素）进行二分查找； 如果$x$比中间元素大，递归地对中间元素右边的数列（比二分查找大的元素）进行二分查找。 代码实现 Python实现 递归实现： 1def BinarySearch(arr, target, left = 0, right = 0): 2 """二分排序（递...

经典字符串匹配 BF暴力匹配算法 暴力匹配，即Brute Force，简称BF算法。BF算法是一种简单朴素的模式匹配算法，常用于在一个主串S内查找一个子串T的出现位置。 算法步骤 假设有主串S与子串P，主串S的长度为N，子串T的长度为M。 将S和T左对齐，并比较其第一个元素。 若匹配，则继续比较下一个元素，一直到第M个元素。 若不匹配则T向右移动一个位置。 接着根据步骤3和4进行比较，直到匹配到或者T移动了N-M且仍未匹配到。 代码实现 Python实现 实现1： 1def BFMatch(s, p): 2 if len(s) < len(p): 3 return -1 4 i, j = 0, 0 5 # 匹配阶段 6 while...

临时变量 通过建立一个临时变量来实现两数交换： 1def swap(x, y): 2 print(x, y) 3 tmp = x 4 x = y 5 y = tmp 6 print(x, y) 7 return x, y 8 9if __name__ == '__main__': 10 swap(1, 2) 缺点： 需要消耗额外的内存。 优点： 不限制类型，大多数类型都能使用该操作。 加减交换 通过加减法实现： 1def swap(x, y): 2 print(x, y) 3 x = x + y 4 y = x - y 5 x = x - y 6 print(x, y) 7 return x, y 8 9if __name__...

Python 语法 注释 Python 的注释风格： 1# 行注释 2 3''' 4块注释1 5''' 6 7""" 8块注释2 9""" 注释中的内容将不会被执行。 标识符 首字母必须是大写或小写的英文字母或者下划线 _。 其他部分由大写或小写的英文字母、数字和下划线组成。 大小写敏感（区分大小写）。 Python3 中允许使用非 ASCII 标识符，即中文也可作为标识符： 1>>> 变量 = 5 2>>> print(变量) 35 关键字 Python 关键字（keyword）不能作为标识符使用，关键字又称保留字。 使用 keyword 模块输出 Python 的所有关键字： 1>>> import keyword 2>>>...

正则表达式语法 —— Python 正则表达式是一个特殊的字符序列，能方便地检查一个字符串是否与某种模式匹配。 正则表达式可以拼接。 正则表达式可以包含普通或者特殊字符。 绝大部分普通字符，是最简单的正则表达式。它们就匹配自身。 特殊字符既可以表示它的普通含义， 也可以影响它旁边的正则表达式的解释。 重复修饰符（*、+、?、{m,n}, 等）不能直接嵌套。避免了非贪婪后缀 ? 修饰符，和其他实现中的修饰符产生的多义性。要应用一个内层重复嵌套，可以使用括号。 特殊字符 序列 说明 . （点）在默认模式，匹配除了换行的任意字符。 如果指定了标签 DOTALL，它将匹配包括换行符的任意字符。 \ 转义特殊字符（允许你匹配...

冒泡排序 冒泡排序（Bubble Sort）是一种简单直观的排序算法。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 时间复杂度：$O(n^2)$ 算法步骤 假设一个序列长度为n，m（m≤n）是已排序完成的在末尾的数。 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。对比结束后，最后的元素会是最大的数。 对接下来n-m个未排序的数重复步骤1和2，直到没有任何一对数字需要比较。 第一趟对序列中所有n个数进行比对，第二趟对序列中n-1个未排序完成的数进行比对，以此类推。每次比对的数为n-m。 动画演示： 代码实现 Python实现 1def...