Archive: 2020/8

【二分难题】力扣793-阶乘函数后K个零

摘要: 本文详细拆解 leetcode 793-阶乘函数后K个零 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们看一类阶乘的问题,力扣 793,有多少个整数的阶乘末尾有 K 个零的问题。通过

【DP难题】力扣920-播放列表数量

无串线性 dp 容斥原理 交集 = 并集 - 差集 组合数学解法:官方题解,并没有看懂 求有限制的排列个数问题 生成函数和中国剩余定理的应用 $1 题目题目链接920. 播放列表的数量 题目描述你的音乐播放器里有 N 首不同的歌,在旅途中,你的旅伴想要听 L 首歌(不一定不同,即,允许歌曲重复)。请你为她按如下规则创建一个播放列表: 每首歌至少播放一次。一首歌只有在其他 K 首歌播放完

同余

摘要: 本文介绍同余的算法原理和代码模板、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究同余以及相关的定理。主要内容如下: 同余的定义 同余类与剩余系 费马小

约数

摘要: 本文介绍约数的定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究约数以及相关的定理。主要内容如下: 约数的定义 算术基本定理 算术基本定理的推论 求正约数集合 N :

力扣365-水壶问题

摘要: 本文详细拆解 力扣365-水壶问题,核心是隐式图搜索和裴蜀定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个数学问题,本题可以列出不定方程,可以通过数论中的裴蜀定理

DFS

解决的问题 组合搜索和隐式图搜索 组合搜索,隐式图搜索 树搜索 树的DFS遍历 图搜索 无向图的连通分量 有向图的连通分量 无向图的环 有向图的环 二分图判定 无向图的桥 无向图的割点 无向图的双连通分量 tarjan算法 欧拉路径 DFS拓扑排序 还有很多… 图搜索的 DFS 模板(以遍历为例) 经常配合使的用方法 连通性(DFS基本模型) 1391. 检查网格中是否存在有

BFS

BFS 可解决的问题 组合搜索和隐式图搜索 组合搜索,隐式图搜索 树搜索 树的BFS遍历 图搜索 无权图最短路径 带权图最短路径 无向图的环 有向图的环 无向图的连通分量 二分图判定 拓扑排序 还有很多… 图搜索的 BFS 模板(无权图最短路径为例) 经常配合使用的方法 无权图最短路径(BFS基本模型) 1311. 获取你好友已观看的视频 909. 蛇梯棋 复杂状态表示和

回溯问题汇总:组合搜索,隐式图搜索

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

【二分难题】力扣786-第K个最小的素数分数

摘要: 力扣 786,二分的经典题,外层值域二分,内层区间二分。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们来看一个二分的问题,在文章 二分 中,我们系统梳理过力扣上的二分的题目

树的BFS遍历

基础层序遍历: 102. 二叉树的层序遍历 队列 递归(不用队列方法1) 双指针(不用队列方法2) 429. N叉树的层序遍历 变种层序遍历 自底向上层序 107. 二叉树的层次遍历 II 锯齿形层序 103. 二叉树的锯齿形层次遍历 层平均值 637. 二叉树的层平均值 堂兄弟节点 993. 二叉树的堂兄弟节点 垂序遍历 314. 二叉树的垂直遍历

二分

摘要: 本文系统梳理了二分的算法要点。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于二分的 83 道题。将场景相

力扣460-LFU

460. LFU缓存 LFU 的原理和实现 LRU : 力扣146-LRU,内存淘汰算法 Redis 中的 LFU $1 题目题目链接 460. LFU缓存 题目描述请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。 get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。put(key, value) - 如果键已

树形DP

摘要: 树形DP的思想与经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 树形DP思想 在树形结构上求解问题,在某棵以 u 为根的树上的答案为 dp[u],其重复子问题是子树上的问题,对应的答

树的DFS遍历

前序遍历: 递归、迭代、Morris遍历 144. 二叉树的前序遍历 建树问题 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 889. 根据前序和后序遍历构造二叉树 1028. 从先序遍历还原二叉树 1008. 先序遍历构造二叉树 编码和序列化问题: 数据压缩 结构判断问题 100. 相同的树 572. 另一个树的子树 1367.

二叉查找树的中序遍历和前驱后继

背景: 树的DFS遍历 手撕平衡树-二叉查找树BST 中序遍历 98. 验证二叉搜索树 99. 恢复二叉搜索树 230. 二叉搜索树中第K小的元素 255. 验证前序遍历序列二叉搜索树 272. 最接近的二叉搜索树值 II 426. 将二叉搜索树转化为排序的双向链表 501. 二叉搜索树中的众数 530. 二叉搜索树的最小绝对差 776. 拆分二叉搜索树 1305. 两棵二

货仓选址与安排邮筒

摘要: 安排邮筒问题,使用动态规划解决 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天看一个非常经典的动态规划的问题,本题是第 28 双周赛 D 题,安排邮筒。 安排邮筒说的是

差分维护区间加法

摘要: 本文通过详细拆解 leetcode 370 来理解差分的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【模板】前缀和与差分 中,我们串讲了前缀和的算法原理和代码模板,并

力扣1476-子矩形查询

摘要: 惰性更新与延迟计算的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在很多数据结构中,对节点更新的时间复杂度是比 $O(1)$ 要大的。当修改非常频繁,但是查询相对稀少的时候,可以将

图论4-欧拉图,哈密顿图

摘要: 欧拉图和哈密顿图的相关概念和定理,参考徐俊明《图论及其应用》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文记录图论中的基本概念和定理,证明省略,本文是个备忘录,需要细

带边权的并查集

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

并查集

摘要: 并查集的原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍并查集的原理和代码模板,最后针对并查集可以解决的几类问题,列出了一些题目列表。 $1 并查集并查集是一种可以动

图论2-树

摘要: 树的相关概念和定理,参考徐俊明《图论及其应用》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文记录图论中的基本概念和定理,证明省略,本文是个备忘录,需要细节的时候再查相

异构图建图

摘要: 两种类型的点和边的异构图建图 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们知道图论的算法相对比较固定,变化的地方不多,难点在于怎样从实际问题转换为图,图中的节点、边在原问题中是什么含义

拓扑排序

摘要: 拓扑排序原理、代码模板、题目列表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumFloyd算法的原理与代码模板plings 本文我们学习拓扑排序的原理、给出代码模板和题目列表,然后解决力扣 210. 拓

LaTeX符号

摘要: 本文记录常用的 LaTeX 符号,在写文章的时候可以直接复制粘贴使用。 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 带帽 希腊字母 二元关系 二元运算符 大运算符 数学

图论1-基本概念

摘要: 图论的基本概念,参考徐俊明《图论及其应用》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文记录图论中的基本概念和定理,证明省略,本文是个备忘录,需要细节的时候再查相应的

素数筛

摘要: 本文介绍素数筛的算法原理和代码模板、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究素数筛。首先以力扣第 204 题为模板题学习埃氏筛和线性筛,然后讨论素

最大公约数算法以及C++17组件

摘要: 本文介绍最大公约数算法的实现、C++17 相应的组件、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最大公约数是数论中最基础的内容,在算法中也经常见到关于最大公约数相关的问

组合数学4-容斥原理,鸽巢原理

摘要: 组合数学:容斥原理、鸽巢原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式;在 组合数学2-母函数,递推关系 中我们

数组中出现的元素

范围内某数字缺失和重复(数字范围1~n,有点置换群的意思oo) 268. 缺失数字 41. 缺失的第一个正数 645. 错误的集合 287. 寻找重复数 448. 找到所有数组中消失的数字 面试题 17.19. 消失的两个数字 765. 情侣牵手 某数字出现次数(数字范围不限) 136. 只出现一次的数字 389. 找不同 137. 只出现一次的数字 II 260. 只出现一次的数字

【DP难题】力扣741-摘樱桃

dp[位置1][位置2] 二维的线性 DP,但是状态由矩阵上的两个位置共同决定 一维的线性 DP 也有两个位置共同决定状态的情况 873. 最长的斐波那契子序列的长度 dp[i][j]:= 以 j, i 结尾,转移时在 [0..j] 中找满足条件的 k 这一步可以二分或哈希表 1027. 最长等差数列 dp[i][j]:= 以 j, i 结尾,转移时在 [0..j] 中找满足条件的 k 这一步用

带权图最短路径的变种问题

摘要: 带权图最短路径的变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 带权图最短路径算法与实现 中我们以力扣 743 作为模板题,全面梳理了带权图最短路径的各种算法与实现。 本文

带压缩的额外状态的 BFS

摘要: 带压缩的额外状态的 BFS 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较难的 BFS 的问题。说的是我们在二维矩阵上走迷宫,其中除了常规的道路和墙,还有

惰性更新

摘要: 惰性更新的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 惰性更新是一种常见的思想,简单理解就是将更新操作存下来,但是不实际执行更新,而当查询的内容需要更新后的结果的时候,才执行更新

【DP难题】力扣546-移除盒子

如果 n <= 20,还可能用搜索来做,有点类似 【搜索难题】力扣488-祖玛游戏 朴素DP思路:区间DP 状态升维 记忆化搜索 $1 题目题目链接546. 移除盒子 题目描述给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子(k >= 1),这样一轮之后你

【搜索难题】力扣488-祖玛游戏

DFS 暴力 剪枝 数据结构优化 刁钻样例(不能乱剪枝) “RRYGGYYRRYGGYYRR”“GGBBB”该样例答案为 5。做法 "RRYGGYYRRYGGYYRR" --插入B-> "RRYGGYYRBRYGGYYRR" --插入B-> "RRYGGYYRBBRYGGYYRR" --插入G-> "

链表排序

147. 对链表进行插入排序 148. 排序链表 基于插入 插入排序 基于选择 选择排序 基于交换 冒泡排序 快速排序 86. 分隔链表 归并排序 自顶向下 自底向上 725. 分隔链表 23. 合并K个升序链表 21. 合并两个有序链表 链表排序的实现有两个大方向,一个是交换节点,一个是交换值。如果是交换值,则使用下面的辅助函数1234567// 交换链表节点值void _s

三色排序

摘要: 计数排序的特例:三色排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过一个模板题看一下三色排序问题。有计数排序和双指针两种方法。之后我们解决力扣 324 摆动排序2,其

力扣164-最大间距

摘要: 桶排序的经典问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 非比较排序 中,我们学习了计数排序、桶排序、基数排序的原理、代码模板、题目,本文我们看一个稍微难点的问题,但很经典,

sed操作集锦

摘要: 本文记录一下日常的项目中遇到的 sed 的问题以及解决方案 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在某一行后面插入内容a 命令 12345CONTENT=...for file in

数组排序

本文通过模板题力扣 912 总结一下常见的数组排序方法和代码模板。 912. 排序数组 基于比较的主流排序 基于插入 基于选择 基于交换 归并排序 不基于比较的主流排序: 非比较排序 非主流排序 非主流排序 链表排序 $0 关于排序稳定性的结论不稳定的排序,都可以通过多关键字排序的办法变成稳定排序(第二个关键字是数组下标) 稳定排序:插入排序,基数排序,归并排序,冒泡排序,计数排序

非比较排序

摘要: 计数排序、桶排序、基数排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 计数排序当数据范围较小,例如十万级,可以通过一个计数数组统计各个数字出现的次数,然后在按照出现的数字和次数从小

非主流排序

非主流排序 912. 排序数组 鸡尾酒排序 栈排序: 面试题 03.05. 栈排序 煎饼排序: 969. 煎饼排序 $1 非主流排序$1.1 鸡尾酒排序冒泡排序法的改良,也叫摇晃排序。 将原数据分成未排序及已排序两部份,利用left、right来识别已排序和未排序的部分 算法: 每回合均利用冒泡排序法 将未排序部分中最大值,移到未排序部分的最右边 将未排序部分中最小值,移到未排序部分的

组合数学3-特殊计数序列,指数型母函数

摘要: 组合数学:特殊计数序列、指数型母函数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式;在 组合数学2-母函数,递推关系

组合数学2-母函数,递推关系

摘要: 组合数学:母函数与递推关系 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式,本文我们看一下组合数学的第二部分,母函数和

DP问题分类汇总-加强版

摘要: 文章《dp问题分类汇总》的加强版 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings dp问题分类汇总 的加强版,《动态规划精讲》 系列的目录结构的主要参考。题目主要是 2000 以内的。 1、

数据压缩

摘要: 本文总结了 leetcode 上的数据压缩相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 数据压缩的背景 相似的概念:序列化,序列化/反序列化,编码/解码(加密/解密),压缩/解

用图床sm.ms

摘要: 使用 sm.ms 图床的过渡时期 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天是 2020 年 8 月 13 日,昨天由于 coding 平台空间超限问题,实践了图

比较简单的两种字符串的编码与解码

摘要: 字符串的编码解码,分隔符、分块编码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 哈夫曼树与哈夫曼编码 和 k叉哈夫曼树 中,我们学习了 2 叉和 k 叉哈夫曼树和哈夫曼编码,并用于

Redis中字符串的编码

摘要: Redis 中字符串的编码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Redis字符串类型内部编码 src/server.h src/sds.h src/object.c 相关题目