- 博客(55)
- 收藏
- 关注
RSS订阅原创 在加边过程中随时查询最短路径
摘要: 加边松弛操作【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】在文章中我们了解到了求最短路径的 Floyd 算法。理解这个算法需要一些动态规划的概念，其中阶段的定义与推导比较特殊，涉及到松弛操作的概念，也就是每推导一个阶段就相当于进行了一次松弛操作。当我们推完了所有的阶段，dp 数组中就有了所有点对之间的最短路径。因此当需要多次查询不同点对之间的最短路径时，用 Floyd 算法是比较合适的，先ON3地预处理出 dp 数组，然后就可以O1。
2024-04-01 10:46:08
751
原创 沃利斯积分的分段渐近估阶：拉普拉斯方法的思想启蒙
本文我们解决了沃利斯积分In∫−π2π2cosxndxn→∞In∫−2π2πcosxndxn→∞的渐近估阶问题。解决过程可以推广到被积函数在幂上有一个大参数 n 这一大类情形，解决这一大类情形的方法称其为拉普拉斯方法，步骤如下：(1) 忽略尾部：估计原积分的尾部并忽略(2) 中心逼近：在中心区域进行逼近并得到误差界(3) 完成尾部：将尾部的积分范围加到中心区域的逼近中。
2024-02-19 08:52:13
812
原创 插入多少次发生哈希冲突：拉马努金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
775
原创 冒泡排序平均需要跑多少趟：拉马努金Q函数初探
本文我们讨论了排序算法的分析中的一个问题：冒泡排序平均需要跑多少趟。首先引入了排列中的一些概念定义，包括逆序、逆序表，然后基于冒泡排序的算法流程，发现冒泡排序扫描的趟数就是逆序表中的最大值。再结合排列的逆序表自身的性质，以及通过累积分布函数求数学期望的性质，最终我们将问题归结到了∑k0Nk!kN−kN!k^{N-k}}{N!k0∑NN!k!kN−k的渐近估阶。
2024-02-15 11:33:39
892
原创 n节点的无序标号树有多少种：拉格朗日反演的应用
本文我们讨论了图论中的算法分析的常见问题：n 节点的无序标号树共有多少个。其结果称为凯莱公式。本文的推导基于拉格朗日反演，首先介绍了拉格朗日反演定理的描述，然后用该定理重新解决了二叉树计数的问题，可以发现拉格朗日反演在简化生成函数计数问题的价值。凯莱公式是图论中的经典结论，主流的推导方式有矩阵树定理和 Prufer 编码等，前置的知识都比较冗长。而本文使用拉格朗日反演，非常轻易地就得到了结果。当然为了突出重点，一些结论本文跳过了推导步骤，比如 n 节点无序标号树的指数生成函数满足的函数方程Czz。
2024-02-13 11:33:44
938
原创 在归并排序中对小数组采用插入排序
摘要: 使递归的叶子变粗【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】在文章中，我们了解了分治算法的设计和分析方法，并且得出了归并排序算法的最坏情况运行时间为Θnlogn。在文章中，我们了解了算法分析的方法论，并且以插入排序为例，得到了插入排序最坏情况运行时间为Θn2。虽然开起来好像归并排序比插入排序的运行时间要好，但插入排序中的常量因子可能使得它在 n 较小时，在许多机器上实际运行得更快。因此归并排序中，当子问题规模足够小时，采用插入排序。
2024-02-10 13:54:50
741
原创 二叉树的计数：直接方法与间接方法
本文我们讨论了有N1N+1N1个虚拟节点的二叉树的个数，类似的树上的计数是分析树上算法的基础问题。基于生成函数的解决过程可以分为三步，第一步是找到生成函数满足的方程，第二步是求解方程得到生成函数，第三步是将生成函数展开取zNz^{N}zN项的系数。其中最关键的是第一步，只要得到了生成函数满足的方程，不管是微分方程还是函数方程，后续的过程就比较好解决了。
2024-02-10 13:49:27
960
原创 生成函数性质速查表
摘要: 生成函数的性质【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。生成函数的一个重要线索来自于 18 世纪欧拉对整数分拆问题的研究，其中有了一些生成函数思想的雏形（该项研究同样也是卷积和的思想来源的线索）。最早提出母函数的是法国数学家拉普拉斯，他在其 1812 年出版的《概率的分析理论》中明确提出“概率生成函数的计算”，书中对欧拉的整数分拆的研究做了延伸。
2024-02-07 23:03:54
789
原创 算法分析中的欧拉方程：基于三数中值法的快速排序
本文我们分析了快排中的一个常见的优化思路：三数中值法。其动机主要是为了解决分割元取字数最小值时会造成过多无效比较的问题。写出优化后算法的递归式，利用生成函数性质转化为微分方程，然后我们发现这竟然是我们之前考试刷过的欧拉方程，可以用换元和微分算子法解出显式解得到生成函数。然后将生成函数展开，取其znz^{n}zn的系数就得到了平均情况的比较次数，将调和数的渐近估阶代入，得到比较次数的渐近估阶。上述步骤中，求解方程得显式解，以及将显式解展开取znz^{n}zn。
2024-02-04 10:34:19
847
原创 随机队列的原理与实现
摘要: 本文介绍随机队列的原理和代码模板，以及 2 道 leetcode 相关题目。【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings随机队列增加删 key 的支持380. 常数时间插入、删除和获取随机元素381. O(1) 时间插入、删除和获取随机元素 - 允许重复$1 随机队列.
2022-05-24 15:38:49
232
原创 Java白皮书关键词总结
Java 设计者写过一个很有影响力的白皮书，用来解释设计的初衷。白皮书可以在这里看： 《The Java Language Environment: Contents A White Paper》。并且发布了一个简短的摘要，摘要分为 11 个术语。摘要中的论述如下简单性希望构建学习成本低的编程系统Java剔除了C++中许多很少使用、难以理解、易混淆的特性没有头文件、指针运算、结构、联合、操作符重载、虚基类等希望支持开发能够在小型机器上独立运行的软件面向对象重点放在数据(对象)和数据的
2022-05-20 14:09:12
431
原创 Java核心技术1-对象与类
摘要: 本文是《Java核心技术 10th》中对象与类的要点总结【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings本文是《Java核心技术1》第10版 【Chap4 类和对象】 的要点总结。由于此前在 C++ 中已经接触过面向对象编程，这里主要关注 Java 与 C++ 有区别的地方。面向对象程序设.
2022-05-17 08:38:11
301
原创 频率派和贝叶斯派
摘要: 频率派和贝叶斯派的区别和联系。【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings在机器学习中，我们把概率引入进来是比较自然的事情，本文我们探讨一下频率派和贝叶斯派的区别和联系。问题抽象X=(x1,x2,...,xN)N×pTX = (x_{1}, x_{2}, ..., x.
2022-05-11 10:25:18
351
原创 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
364
原创 Shell脚本中的set命令
摘要: 本文简单了解一下在 shell 脚本中 set 命令的作用和用法【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplingsBash 脚本执行时，会创建一个子 Shell。bash script.sh以上命令执行后，script.sh 是在一个子 Shell 里执行。Bash 会给.
2022-05-10 10:06:49
1728
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
182
原创 分层抽样的总结
摘要：本文通过几个例子学习了 matplotlib.animation 画动图的方法---对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎： 潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings分层抽样的概念抽样时，将总体分成互不交叉的层，然后按照一定的比例，从各层独立地抽取一定数量的个体，将各层取出的个体合在一起作为样本，这种抽样方法叫分层抽样...
2021-12-12 17:21:01
10548
原创 用matplotlib的Animation画动图
摘要：本文通过几个例子学习了 matplotlib.animation 画动图的方法---对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings我们在使用 matplotlib 时，常用的是 pyplot，可以画各种静态图，常见的代码模板如下fig = plt.figure()ax = fig.add_su
2021-12-08 22:43:02
4589
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
548
原创 【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
392
原创 【概率面试题连载】4. 三人循环赛
写在前面现在的技术岗位面试中，大部分公司都会问概率相关的问题。比如互联网公司的研发工程师，算法工程师，算法研究员，数据分析师，以数据驱动为核心的公司的风控/营销相关的岗位等等。特别是算法工程师和数据分析师，如果工龄较短或者是校招，几乎是必考。此专栏将持续更新概率计算问题及解答。对于每道题，首先给出个人的思路参考，从概率论的角度推公式求解，然后用蒙特卡洛模拟的方式来验证结果。这是概率面试题连载第 4期，本期我们看一个最近朋友在面试中遇到的问题。往期的内容整理在这篇文章里；或者看这个gi..
2021-07-15 21:57:46
588
原创 【面试概率题连载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
176
原创 【面试概率题连载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
124
原创 【面试概率题连载1】抽屉中的袜子
参考: 《Fifty challenging problems in probability with solutions》问题描述A drawer contains red socks and black socksWhen two socks are drawn at random, the probability that both are red is 1/2a. How small can the number of socks in the drawer be?b. How sma
2021-05-25 19:54:33
678
原创 leetcode第242场周赛
总览A题: 单串单向双指针参考: 尺取法B题: 值域二分参考: 二分C题: 前缀和优化 DP; 队列参考: 前缀和优化DPD题: 前缀和+博弈DP参考: 博弈DPA 题1869. 哪种连续子字符串更长给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。例如，s = “110100010” 中，由 1 组成的最长连续子字符串的长度是 2 ，
2021-05-25 11:43:21
204
2
原创 前缀和优化 DP
前缀和优化 DP当 DP 转移方程是如下形式的时候计算 dp[i] 时需要一步求和 sum(dp[a..b])，如果用遍历的方式，则转移的时间复杂度为 O(N)。如果在状态转移的过程中维护一个 dp 数组的前缀和 sums，则这步求和可以用 sums[b + 1] - sums[a] 直接得到，转移的时间复杂度变为 O(1)题目1871. 跳跃游戏 VII给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为
2021-05-25 08:32:05
284
原创 力扣1707-与数组中元素的最大异或值
算法要点:01Trie参考: 01Trie离线查询与在线查询01Trie节点中可以额外维护子树的某些统计信息$1 题目题目链接1707. 与数组中元素的最大异或值题目描述给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有
2021-05-24 12:53:48
111
原创 leetcode第52场双周赛
本文关于leetcode第52场双周赛4道题总览A题: 字符串B题: 模拟参考: 模拟问题汇总C题: 单串单向双指针参考: 尺取法D题: 前缀和；排序+二分参考: 前缀和问题分类汇总, 【模板】前缀和与差分参考: 二分A题1859. 将句子排序一个 句子 指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词 打乱
2021-05-21 16:22:46
286
原创 leetcode第241场周赛
总览A题: 枚举子集参考: 位运算操作B题: 分类讨论参考: 分类讨论, 【分类讨论】力扣335-路径交叉C题: 设计，哈希表参考: 设计-功能系统D题: 动态规划, 组合数学参考1: 组合数学3-特殊计数序列,指数型母函数参考2: 单串线性DP-多维状态,在阶段的基础上附加维度A 题1863. 找出所有子集的异或总和再求和一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。例如，数组 [
2021-05-19 13:25:04
148
原创 围棋AI-KataGo安装记录
KataGo 项目地址: https://github.com/lightvector/KataGo/releases计算平台选择最新版本为 v1.8.2有三种版本: OpenCL vs CUDA vs Eigen项目说明中的描述如下KataGo has three backends, OpenCL (GPU), CUDA (GPU), and Eigen (CPU).The quick summary is:Use OpenCL if you have any good or
2021-05-05 12:38:25
2674
原创 2021力扣杯春季赛团队赛
本次团队赛我(力扣账号 FennelDumplings)与以前在陌陌的一位同事(力扣账号 yiwiy), 以及他之前的同学(力扣账号 chrisx) 组队。大家的个人发挥和团队配合都很好，取得了相当不错的成绩。团队解决了六道题中的前五道，得分 29/41，加上罚时后的总用时为 03:01:43。最终名次 43/3219 ，进了前 50 名，于是捞到了 11~50 名的 500 积分 + 力扣幸运周边小奖品，还是挺开心的。其中我主要完成的是第二题和第五题，解题思路和代码如下。力扣LCP34-二叉树染色
2021-04-11 10:14:43
214
原创 力扣LCP37-最小矩形面积
注：2021力扣杯春季赛团队赛第5题算法要点:两条直线的交点按斜率分桶细节处理题目题目链接LCP 37. 最小矩形面积题目描述二维平面上有 NN 条直线，形式为 y = kx + b，其中 k、b 为整数 且 k > 0。所有直线以 [k,b] 的形式存于二维数组 lines 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 (N2)\binom{N}{2}(2N) 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间
2021-04-11 09:45:46
488
原创 力扣LCP34-二叉树染色
注: 2021力扣杯春季赛团队赛第2题算法要点:树形DP二叉树的后序遍历(参考 树的DFS遍历)$1 题目题目链接LCP 34. 二叉树染色题目描述小扣有一个根结点为 root 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，模型的每个结点有一个 val 价值。小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个，求所有染成蓝色的结点价值总和最大是多少？提示：1 <= k <= 101 <= val <= 10
2021-04-11 09:41:22
258
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人