- 博客(65)
- 收藏
- 关注
RSS订阅原创 历史名人集锦 | 计算机 | 数学 | 物理学 | 工程学
各位好，本文给大家盘点了一些数学、物理学、计算机科学、工程学领域的历史名人，按出生时间顺序罗列。
2025-02-01 14:40:04
815
原创 最少硬币组合问题2：贪心算法【附算法导论习题答案下载】
等比数列只是其中一种可贪心的面额集，能不能找到更多的可贪心面额集，或者更激进一点，有没有贪心算法成立的充分必要条件。退而求其次，有没有比较通用的算法，任意给定一个面额集后可以通过该算法来判断该面额集能不能贪心。事实上这两个问题非常复杂，在学术论文中可以找到一些结果，以后有机会在跟大家分享。
2025-01-11 15:35:26
806
原创 滑动窗口字符计数的优化：增加维护聚合信息应对高频查询
在维护滑动窗口时，一个最常见的查询操作是判断窗口是否合法，这是一个高频查询，为了优化这个查询的效率，需要灵活使用各种数据结构来维护窗口内的信息，本文的题目比较简单，通过增加一个聚合信息即可解决，在更复杂的场景需要一些数据结构，比如之前我们提到过，数据压缩的 LZ77 方法，在优化过程中使用了后缀树来提高查询效率。
2025-01-11 15:16:45
559
原创 滑动窗口 | 满足条件的子串数目
摘要: 以滑动窗口的方式统计满足条件的子串数目【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】各位好，今天我们来看一个在字符串上通过滑动窗口进行子串统计的问题。在滑动窗口推进的过程中，维护字符计数进行一些统计是一大类问题，参考此前的汇总文章。最早提出滑动窗口这个概念是在数据压缩的论文中，Jacob Ziv 和 Abraham Lempel 在 1977 和 1978 年发表了两篇基于自适应词典进行数据压缩的里程碑式论文，两篇论文构建词典的路线不一样。
2025-01-10 19:57:59
868
原创 最少硬币组合问题1：动态规划、完全背包
摘要: 最少硬币组合问题，对任意面额集的动态规划算法【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我们此前详细讲解过背包问题，题目的分类汇总参考。其中硬币组合是完全背包的一个经典问题。在完全背包中，每个物品都是不限个数的，我们要做的是在背包容量范围内，拿走的总价值尽可能多。而硬币组合问题中，每种面值的硬币也是不限个数，我们要做的是拿走的面值总和刚好是给定值，使得硬币的个数最少。
2025-01-06 10:24:10
921
原创 最少硬币组合问题1：完全背包
摘要: 最少硬币组合问题，对任意面额集的动态规划算法【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我们此前详细讲解过背包问题，题目的分类汇总参考。其中硬币组合是完全背包的一个经典问题。在完全背包中，每个物品都是不限个数的，我们要做的是在背包容量范围内，拿走的总价值尽可能多。而硬币组合问题中，每种面值的硬币也是不限个数，我们要做的是拿走的面值总和刚好是给定值，使得硬币的个数最少。
2025-01-05 00:28:17
619
原创 Weierstrass不等式 | 概率方法
本文我们通过概率方法解决了魏尔斯特拉斯不等式的一部分，而要完整解决该不等式，还是需要借助 Schur 凸函数相关的概念。通过本例我们可以看到，一些很难的不等式，通过概率方法可以轻易解决。因此当看到不等式中累加、累乘的各项有01(0, 1)01的范围限制时，可以考虑概率方法。
2025-01-02 18:54:18
752
原创 2025年的内容与栏目建设
各位好，今天是 2024 年最后一天，祝各位新年快乐。今天没有题目，主要跟各位聊聊天，交流一下 2025 年内容与栏目的设想。我的账号早期是写 leetcode 题解起盘的，当时的刷题量很大，所以题解中的很多内容的总结性还不错，可以举一反三。写的多了，经常能把相同思路的题目聚合到一起，让刚开始刷题的人迅速了解一个大的算法点都有哪些小点，哪些题目是属于同一个小点下的，基本上解了一个题就等于所有题都解了，所以早期我还出了很多 2000 题以内的各个算法点的题目清单，很多人看过。
2025-01-01 14:32:34
478
原创 字符串精确匹配的主流算法总结（含书籍推荐）
摘要: 字符串精确匹配方法汇总【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】各位好，此前我们讨论了字符串精确匹配的很多主流算法。实际上字符串匹配算法是一个单独的大课题，这里推荐一本书 《Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology》 作者 Dan Gusfield。
2024-12-14 12:45:42
934
原创 字符串匹配暴力算法比KMP算法更实用
摘要: 字符串匹配的暴力算法平均情况时间复杂度【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】在文章中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它是一种预处理+相应查询的思想，通过巧妙设计的预处理信息，避免扫描指针的回退，使得在最坏情况下也有线性的时间复杂度。事实上，在实用场景中，字符串的精确匹配的暴力算法就很有效，原因在于如果输入数据分布是均匀的，暴力算法在平均情况下的时间复杂度依然是线性的。本文我们来推导一下这个事情。
2024-12-12 10:03:51
714
原创 在加边过程中随时查询最短路径
摘要: 加边松弛操作【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】在文章中我们了解到了求最短路径的 Floyd 算法。理解这个算法需要一些动态规划的概念，其中阶段的定义与推导比较特殊，涉及到松弛操作的概念，也就是每推导一个阶段就相当于进行了一次松弛操作。当我们推完了所有的阶段，dp 数组中就有了所有点对之间的最短路径。因此当需要多次查询不同点对之间的最短路径时，用 Floyd 算法是比较合适的，先ON3地预处理出 dp 数组，然后就可以O1。
2024-04-01 10:46:08
959
原创 沃利斯积分的分段渐近估阶：拉普拉斯方法的思想启蒙
本文我们解决了沃利斯积分In∫−π2π2cosxndxn→∞In∫−2π2πcosxndxn→∞的渐近估阶问题。解决过程可以推广到被积函数在幂上有一个大参数 n 这一大类情形，解决这一大类情形的方法称其为拉普拉斯方法，步骤如下：(1) 忽略尾部：估计原积分的尾部并忽略(2) 中心逼近：在中心区域进行逼近并得到误差界(3) 完成尾部：将尾部的积分范围加到中心区域的逼近中。
2024-02-19 08:52:13
1120
原创 插入多少次发生哈希冲突：拉马努金Q分布与二元渐近分析
本文我们解决了第一次发生哈希冲突时，平均插入了多少数据的问题。其结果正是我们拉马努金 Q 函数QNQ(N)QN。QNQ(N)QN是一个和式，具体为QN∑k1∞fkNQNk1∑∞fkN，本文我们详细推导了fkNf(k, N)fkN的渐近估阶，其推导过程是处理二元渐进性非常有代表性的操作，有了这个例子，以后再遇到二元渐近分析的问题，思路可以仿照本例。在此前解决冒泡排序平均扫描趟数的问题中，我们接触过拉马努金 Q 函数QNQ(N)QN。
2024-02-16 09:46:59
920
原创 冒泡排序平均需要跑多少趟：拉马努金Q函数初探
本文我们讨论了排序算法的分析中的一个问题：冒泡排序平均需要跑多少趟。首先引入了排列中的一些概念定义，包括逆序、逆序表，然后基于冒泡排序的算法流程，发现冒泡排序扫描的趟数就是逆序表中的最大值。再结合排列的逆序表自身的性质，以及通过累积分布函数求数学期望的性质，最终我们将问题归结到了∑k0Nk!kN−kN!k^{N-k}}{N!k0∑NN!k!kN−k的渐近估阶。
2024-02-15 11:33:39
1044
原创 n节点的无序标号树有多少种：拉格朗日反演的应用
本文我们讨论了图论中的算法分析的常见问题：n 节点的无序标号树共有多少个。其结果称为凯莱公式。本文的推导基于拉格朗日反演，首先介绍了拉格朗日反演定理的描述，然后用该定理重新解决了二叉树计数的问题，可以发现拉格朗日反演在简化生成函数计数问题的价值。凯莱公式是图论中的经典结论，主流的推导方式有矩阵树定理和 Prufer 编码等，前置的知识都比较冗长。而本文使用拉格朗日反演，非常轻易地就得到了结果。当然为了突出重点，一些结论本文跳过了推导步骤，比如 n 节点无序标号树的指数生成函数满足的函数方程Czz。
2024-02-13 11:33:44
1117
原创 在归并排序中对小数组采用插入排序
摘要: 使递归的叶子变粗【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】在文章中，我们了解了分治算法的设计和分析方法，并且得出了归并排序算法的最坏情况运行时间为Θnlogn。在文章中，我们了解了算法分析的方法论，并且以插入排序为例，得到了插入排序最坏情况运行时间为Θn2。虽然开起来好像归并排序比插入排序的运行时间要好，但插入排序中的常量因子可能使得它在 n 较小时，在许多机器上实际运行得更快。因此归并排序中，当子问题规模足够小时，采用插入排序。
2024-02-10 13:54:50
835
原创 二叉树的计数：直接方法与间接方法
本文我们讨论了有N1N+1N1个虚拟节点的二叉树的个数，类似的树上的计数是分析树上算法的基础问题。基于生成函数的解决过程可以分为三步，第一步是找到生成函数满足的方程，第二步是求解方程得到生成函数，第三步是将生成函数展开取zNz^{N}zN项的系数。其中最关键的是第一步，只要得到了生成函数满足的方程，不管是微分方程还是函数方程，后续的过程就比较好解决了。
2024-02-10 13:49:27
1204
原创 生成函数性质速查表
摘要: 生成函数的性质【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。生成函数的一个重要线索来自于 18 世纪欧拉对整数分拆问题的研究，其中有了一些生成函数思想的雏形（该项研究同样也是卷积和的思想来源的线索）。最早提出母函数的是法国数学家拉普拉斯，他在其 1812 年出版的《概率的分析理论》中明确提出“概率生成函数的计算”，书中对欧拉的整数分拆的研究做了延伸。
2024-02-07 23:03:54
882
原创 算法分析中的欧拉方程：基于三数中值法的快速排序
本文我们分析了快排中的一个常见的优化思路：三数中值法。其动机主要是为了解决分割元取字数最小值时会造成过多无效比较的问题。写出优化后算法的递归式，利用生成函数性质转化为微分方程，然后我们发现这竟然是我们之前考试刷过的欧拉方程，可以用换元和微分算子法解出显式解得到生成函数。然后将生成函数展开，取其znz^{n}zn的系数就得到了平均情况的比较次数，将调和数的渐近估阶代入，得到比较次数的渐近估阶。上述步骤中，求解方程得显式解，以及将显式解展开取znz^{n}zn。
2024-02-04 10:34:19
998
原创 随机队列的原理与实现
摘要: 本文介绍随机队列的原理和代码模板，以及 2 道 leetcode 相关题目。【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings随机队列增加删 key 的支持380. 常数时间插入、删除和获取随机元素381. O(1) 时间插入、删除和获取随机元素 - 允许重复$1 随机队列.
2022-05-24 15:38:49
342
原创 Java白皮书关键词总结
Java 设计者写过一个很有影响力的白皮书，用来解释设计的初衷。白皮书可以在这里看： 《The Java Language Environment: Contents A White Paper》。并且发布了一个简短的摘要，摘要分为 11 个术语。摘要中的论述如下简单性希望构建学习成本低的编程系统Java剔除了C++中许多很少使用、难以理解、易混淆的特性没有头文件、指针运算、结构、联合、操作符重载、虚基类等希望支持开发能够在小型机器上独立运行的软件面向对象重点放在数据(对象)和数据的
2022-05-20 14:09:12
505
原创 Java核心技术1-对象与类
摘要: 本文是《Java核心技术 10th》中对象与类的要点总结【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings本文是《Java核心技术1》第10版 【Chap4 类和对象】 的要点总结。由于此前在 C++ 中已经接触过面向对象编程，这里主要关注 Java 与 C++ 有区别的地方。面向对象程序设.
2022-05-17 08:38:11
379
原创 频率派和贝叶斯派
摘要: 频率派和贝叶斯派的区别和联系。【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings在机器学习中，我们把概率引入进来是比较自然的事情，本文我们探讨一下频率派和贝叶斯派的区别和联系。问题抽象X=(x1,x2,...,xN)N×pTX = (x_{1}, x_{2}, ..., x.
2022-05-11 10:25:18
420
原创 shell 的 break 和 continue 与 C++/Java/Python 的区别
摘要: 本文简单了解一下在 shell 脚本中的 continue 和 break 与 C++/Java/Python 中的不同【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings在 C++, Java, Python 中，都有 continue, break 用来提前结束循环，在 She.
2022-05-10 10:13:54
442
原创 Shell脚本中的set命令
摘要: 本文简单了解一下在 shell 脚本中 set 命令的作用和用法【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplingsBash 脚本执行时，会创建一个子 Shell。bash script.sh以上命令执行后，script.sh 是在一个子 Shell 里执行。Bash 会给.
2022-05-10 10:06:49
1849
1
原创 Bash Shell 常见概念和操作速查表
摘要: 本文记录 Bash Shell 中常见的概念和操作【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings参考链接: https://devhints.io/bash基本操作条件执行git commit && git pushgit commit || echo "commi.
2022-05-10 01:01:33
213
原创 分层抽样的总结
摘要：本文通过几个例子学习了 matplotlib.animation 画动图的方法---对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎： 潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings分层抽样的概念抽样时，将总体分成互不交叉的层，然后按照一定的比例，从各层独立地抽取一定数量的个体，将各层取出的个体合在一起作为样本，这种抽样方法叫分层抽样...
2021-12-12 17:21:01
12471
原创 用matplotlib的Animation画动图
摘要：本文通过几个例子学习了 matplotlib.animation 画动图的方法---对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings我们在使用 matplotlib 时，常用的是 pyplot，可以画各种静态图，常见的代码模板如下fig = plt.figure()ax = fig.add_su
2021-12-08 22:43:02
5669
2
原创 【概率面试题连载】5. 试验直到第一次成功
这是【概率面试题连载】第5期，这次我们继续看《Fifty challenging problems in probability with solutions》中的一题。问题描述On average, how many times must a die be thrown until one gets a 6?一枚骰子掷出第一个 6 平均需要掷多少次。思路参考1记 p(k) := 第一个 6 需要掷 k 次的概率。p := 在一次投掷中得到 6 的概率, q = 1 - pk.
2021-11-23 15:10:22
604
原创 【Python性能分析与优化】1. Python性能分析基础
1. 什么是性能分析性能分析就是分析代码和它正在使用的资源之间有着怎样的关系。性能分析软件有两类方法论：(1)基于事件的性能分析(event-based profiling)(2)统计式性能分析(statistical profiling)Event-based profiling不是所有的编程语言都支持这类性能分析。支持这类基于事件的性能分析的编程语言主要有以下几种:java： JVMTI(JVM Tools Interface，JVM工具接口)为性能分析器提供了钩子，可以跟踪诸如函数调用
2021-07-24 00:30:51
459
原创 【概率面试题连载】4. 三人循环赛
写在前面现在的技术岗位面试中，大部分公司都会问概率相关的问题。比如互联网公司的研发工程师，算法工程师，算法研究员，数据分析师，以数据驱动为核心的公司的风控/营销相关的岗位等等。特别是算法工程师和数据分析师，如果工龄较短或者是校招，几乎是必考。此专栏将持续更新概率计算问题及解答。对于每道题，首先给出个人的思路参考，从概率论的角度推公式求解，然后用蒙特卡洛模拟的方式来验证结果。这是概率面试题连载第 4期，本期我们看一个最近朋友在面试中遇到的问题。往期的内容整理在这篇文章里；或者看这个gi..
2021-07-15 21:57:46
1127
原创 【面试概率题连载3】系列赛中连续获胜
参考: 《Fifty challenging problems in probability with solutions》问题描述To encourage Elmer’s promising tennis career, his father offers him a prize if he wins (at least) two tennis sets in a row in a three set series to be played with his father and the club
2021-05-26 20:18:51
286
原创 【面试概率题连载2】轻率的陪审团
参考: 《Fifty challenging problems in probability with solutions》问题描述A 3 man jury has 2 members each of whom independently has probability p of making the correct decision, and a 3rd member who flips a coin for each decisionA one man jury has probability
2021-05-26 20:17:50
163
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人