Archive: 2023/9

字典序法枚举组合

摘要: 按照字典序来枚举组合 $\binom{n}{r}$ 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字典序法枚举排列 中,我们用字典序方法完成了排列的枚举。在 C++ 中,std::n

阶乘数系统与康托编码

摘要: 阶乘数系统、康托编码,全排列和字典序互相转换 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 回溯法的思想、设计与分析 中,我们系统学习了回溯法。回溯法将解空间看做树形结构,称为状态空

字典序法枚举排列

摘要: 按照字典序来枚举全排列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 回溯法的思想、设计与分析 中,我们系统学习了回溯法。回溯法将解空间看做树形结构,称为状态空间树,在文章 回溯法三

SJT算法:沿哈密顿路径枚举全排列

摘要: 枚举全排列与哈密顿路径 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 回溯法的思想、设计与分析 中,我们系统学习了回溯法。回溯法将解空间看做树形结构,称为状态空间树,在文章 回溯法三

n皇后-同一问题构造不同的状态空间树

摘要: n 皇后问题与回溯法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 回溯法的思想、设计与分析 中,我们系统了解了回溯法的思想。 我们知道要用回溯法解决问题,首先需要明确问题的解空间,

回溯法三种常见的状态空间树:子集树、排列树、满m叉树

摘要: 三种常见的状态空间树 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 回溯法在文章 回溯法的思想、设计与分析 中,我们系统地了解了回溯法的思想。 回溯法是一种在解空间中搜索可行解或最优解的方法

回溯法的思想、设计与分析

摘要: 回溯法基本思想 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 回溯法思想回溯法是一种在解空间中搜索可行解或最优解的方法。该方法通常将解空间看做树形结构,称为状态空间树。 搜索过程以 DFS

记忆化搜索解决DP过程有效状态值稀疏的问题

摘要: 最优子结构+重复子问题 -> 动态规划 -> 有很多对结果无影响的无效状态 -> 改为记忆化搜索 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算

记忆化搜索解决DP状态转移方向不好想的问题

摘要: 最优子结构+重复子问题 -> 动态规划 -> 状态转移方向不明显 -> 改为记忆化搜索 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算法。相应地

从递归/搜索出发到记忆化搜索

摘要: 原问题的解依赖子问题的解 -> 先写出递归算法 -> 然后发现有很多重复子问题 -> 增加记忆化 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算

渐进分析的一些例子

摘要: 渐进分析的一些经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 函数增长与渐进分析入门 中我们学习了函数增长的阶和渐进分析的一些基础知识。本文我们看一些渐进分析中的一些经典问题

在归并排序中对小数组采用插入排序

摘要: 使递归的叶子变粗 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分治算法的设计与分析-归并排序 中,我们了解了分治算法的设计和分析方法,并且得出了归并排序算法的最坏情况运行时间为 $

函数增长与渐进分析入门

摘要: 函数增长与渐进分析入门 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 基于随机访问机模型分析算法 中我们了解了算法分析确定算法精确运行时间的方法论。 当输入规模足够大,精确运行时间中

分治算法的设计与分析-归并排序

摘要: 以归并排序为例来看分治算法的设计与分析 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分治法的设计思路一些算法在结构上是递归的,为了解决一个给定的问题,算法一次或多次递归地调用自身以解决相关

基于随机访问机模型分析算法

摘要: 分析算法的方法论 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分析算法,也就是预测算法需要的时间和资源。我们关心的资源问题包括内存、通信带宽、计算机硬件等。但我们往往更关

关联矩阵$M$与节点的度,$MM^{T}$

摘要: 关联矩阵与节点的度 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个算法导论中比较有意思的一个习题,具体见第三版 22. 1-7,关于关联矩阵与节点的度。 关

霍尔三元组、循环不变式与程序正确性

摘要: 循环不变式 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 托尼·霍尔 (Hoare) 是 20 世纪非常有影响力的一位计算机科学家,1980 年图灵奖。我们熟知的快速排序

力扣32-最长有效括号子串

摘要: 最长有效括号子串 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们之前了解过有效括号如何判定的问题,本文我们看一个进一步的问题:在字符串中找到最长有效括号子串,有两种方法,除了栈以外,还有

【二分难题】力扣2560-打家劫舍4

摘要: 值域二分+其他算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个最小化最大值的问题,值域二分是解决这种问法的常规思路。对于二分的答案,一般还需要别的算法来判断该答案能否满足要

北京有哪些巡河道可以骑行

摘要: 截至 2023.10 北京的可以骑行的巡河道整理 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于我来说,骑车是最近几年唯一还在保持的运动项目,不管怎么来回来去搬家,始终

含集合级信息的并查集

摘要: 带集合级信息的并查集的原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 并查集 中我们学习了并查集的原理和代码模板,本文介绍带集合级信息的并查集。 我们知道并查集的结构是

树上差分

摘要: 树上差分算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 前缀和与差分,我们对一个序列定义了前缀和序列和差分序列,根据差分序列的前缀和序列是原序列,原序列区间上的增减转化为了前缀和

生物演化史诗

摘要: 生物历史 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings