Category: 算法

有序数据结构在编程中（尤其是算法竞赛和竞技编程）非常实用。在 Python 中，主要由 Sorted Containers 库提供三种有序数据结构：SortedDict、SortedSet 和 SortedList。 深入理解 Python 有序数据结构：从内置到 SortedContainers Python 有序数据结构完整指南 Python 中的有序列表、字典与集合实战解析 带你玩转 Python SortedContainers 与内置排序结构 Python 开发者必读：SortedContainers 与内置数据结构对比 Python 有序数据结构教程 排序是编程中最常见的操作之一。Python 提供了多种方式来维护有序数据，从内置的列表、集合、堆，到第三方库 sortedcontainers。 本教程将介绍 …

什么是竞技编程（Competitive Programming）？ 竞技编程的英文是 Competitive Programming，是指在限定时间内通过编写程序解决一系列算法问题的比赛形式。比较知名的赛事有 ACM-ICPC、Codeforces、Google Kick Start 等。这类比赛不仅考验选手的算法功底和编程技巧，还需要良好的思维敏捷性和代码调试能力。 比如我二十多年前在高中参加的 ICPC，就是一种典型的竞技编程。当时我们使用的编程语言还是 Turbo Pascal，比赛时间是三个小时，要解决四道题。那时候只要程序能输出正确的结果就行了，根本不太在意代码的实现方式和写得是否优雅。 我家娃在做 LeetCode 的一道算法题时，由于算法不够高效，有两三个测试用例出现了超时。他索性“投机取巧”地加了一个 if 判断，针对那些特定的输入直接返回正确结果。这样做在 LeetCode 上是可行的——前提是你知道测试数据，并能手动处理特殊情况。 但在实际的比赛中，这种做法往往行不通。一方面你无法提前知道测试输入；另一方面题目设计者也会故意防止这种“硬编码逃课”手法，所以比赛更要求通用、稳健的算法方案。这也是竞技编程和普通刷题平台之间的一个重要区别。 🏆 ACM-ICPC（国际大学生程序设计竞赛） 由 ACM 发起，目前由 ICPC Foundation 主办。 …

停机问题：程序能预测自己吗？ 问题：给定程序 P 和输入 x，你能判断 P(x) 是否会停机，还是永远运行下去吗？ 由阿兰·图灵于 1936 年提出 被证明为不可判定——不存在通用算法能解决所有情况 本质是自指问题：程序能分析另一个程序（甚至是自己）吗？ 图灵的思想实验 假设：H(P, x) 判断 P(x) 是否停机 定义下面的Python函数： def D(P): if H(P, P): while True: pass # 无限循环 …

使用 Bash 脚本计算最大公约数（GCD） 什么是 GCD？ GCD 是 最大公约数（Greatest Common Divisor） 的缩写。 它是能同时整除两个整数的最大正整数。 例如： 8 和 12 的 GCD 是 4 14 和 49 的 GCD 是 7 GCD 常用于化简分数、密码算法以及数论中。 …

币圈的P站是Poloniex，前几年被孙宇晨收购了，它是一个交易所。我很久之前用过Poloniex，当时对其印象并不是很好。 不过，现在我对其好感增加，因为币安买下的coinmarketcap免费的接口就很多限制。 官方文档），这个接口的频率限制是一秒200次，很慷慨了。 https://api.poloniex.com/markets/price 能返回所有交易配对，比如这样的： 这个JSON返回的结构是一个数组，每个元素是个结构体，也就是一个币价的具体配对信息，我们可以看成是一条边Edge两个顶点Vertice，这样就是一个图结构（带权图 Weighted Graph，权值就是兑换价格），虽然给的是单边，但其实是个双向的，比如USD_BTC得值可以反过来推得BTC到USD的价格。我们可以设计一个算法，从币价A到币价B，可以通过BFS广度优先搜索算法来获取价格。比如有配对A_B、B_C、C_D我们就可以获得A_D的值。 深度优先搜索算法DFS也可以，不过这个算法会返回找到的第一条路径，并不能保证是最短的，最短的确实是最准确的，因为链也长，转换精度就会下降。 当然，可能存在多条路径，最理想的状态是把这些路径都求出来，取个平均啥的，不过这样就得暴力搜索所有的路径了，算法时间复杂度就会比较高。 以下是BFS广度优先算法的代码，Javascript的，可以用于网页前端或者NodeJs后端，甚至是CloudFlare Serverless Worker或者是其它无服务框架：Azure Function、AWS Lambda等。 const fetch = require('node-fetch'); async function getTicker(a, b) { try { const response = …

P、NP、NP-hard 和 NP-complete 是计算复杂性理论中的关键概念，用于描述不同类型的计算问题以及它们的求解难度。 P 类问题 P 类问题是指多项式时间内可以通过确定性算法解决的问题。这意味着，给定一个输入，问题可以在有限的步骤内得到解决，且步骤的数量是输入大小的多项式函数。换句话说，P 类问题的求解效率较高。例如，最短路径问题和排序问题都是 P 类问题。 NP 类问题 NP（Non-deterministic Polynomial time）类问题是指能够在多项式时间内验证解是否正确的问题。换句话说，虽然找到问题的解可能比较难，但一旦给出了解，我们可以在多项式时间内验证它是否正确。一个典型的 NP 问题是旅行商问题：找出某个城市之间的最短旅行路径可能很复杂，但给定一条路径，我们可以快速验证它是否满足要求。 NP-complete 问题 NP-complete 问题是 NP 类问题中的一种特殊类型。这类问题满足以下两个条件： 它是 NP 类问题，意味着给定解后可以在多项式时间内验证其正确性。 它是 NP …

“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。 深度优先搜索 (DFS) DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。 剪枝/Pruning 剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。 回溯算法/Backtracking 回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。 结合三者的理解 DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索； 剪枝 则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。 因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。 例子：Alpha-beta 算法剪枝 Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。 …