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. 蛇梯棋 复杂状态表示和

组合搜索,隐式图搜索

组合搜索:在有限的搜索空间(也叫隐式图)内穷举搜索出可行答案或最优答案,本质上还是穷举。 组合经常用于各种隐式图搜索,一般既可以 DFS 也可以 BFS,哪种好没有定式,需要结合具体问题。 难点主要有两个: 第一个是搜索空间中的状态表示(隐式图的节点意义)和状态转移(隐式图的边意义)可以很复杂。陷入具体问题或业务问题中有时很难发现其中的状态和转移,进而找到合适的图表示来建模。 第二个是优化,组

【二分难题】力扣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思想1234dp[u][s] = 常数 u为叶子节点 = f(dp[v1], dp[v2], ...) v1,v2,...为u的子节点s 为与 u 相关的状态答案 g(dp[root]) 有时候子树的答案交给根之后就不会再用到了,这种情况有点像后序遍历处理的问题,此时一般就用后序遍历而不提树形DP的事,例如 树

树的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 题,安排邮筒。 安排邮筒说的是

差分维护区间加法

前缀和与差分的关系: 力扣303,304-前缀和 前缀和问题分类汇总 用差分维护区间加, 查询最终单点值 用惰性计算维护区间赋值, 多次查询单点值: 力扣1476-子矩形查询,延迟计算 $1 场景 370. 区间加法 假设你有一个长度为 n 的数组,初始情况下所有的数字均为 0,你将会被给出 k​​​​​​​ 个更新的操作。 其中,每个操作会被表示为一个三元组:[startIndex, e

力扣1476-子矩形查询,延迟计算

第 28 场双周赛 B 题 区间赋值,多次单点查询值:惰性计算 区间赋值,多次查询区间最值: 线段树区间修改+惰性计算 力扣699-平衡树区间模块,线段树区间修改,RMQ 区间加,查询最终单点值: 差分与前缀和, 力扣370-区间加法,差分 惰性计算: 将操作存下来,当询问时再看被询问点最后一次被改的值 惰性更新:面试题03.05-惰性更新 惰性计算和延迟调用相关背景 函数式思维 python

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

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

带权并查集

并查集 带权并查集 集合级的权: 一般是连通分量中的属性,例如元素个数,最值等,查找过程无影响 边级的权:节点到父节点的某种指标,例如长度,查找和合并都会对边权有影响 模板: 399. 除法求值 题目 集合级的权 128. 最长连续序列 连通分量的大小 面试题 17.07. 婴儿名字 连通分量的属性 952. 按公因数计算最大组件大小 连通分量的大小 1061. 按字典序排列最小的等效字符串

并查集

基本操作:same(x, y), union(x, y), find(x) 路径压缩,按秩合并 解决的问题: 加边连通性:不断加边,同时问某两个点是否连通 Kruskal 最小生成树 连通分量:判定,个数,大小, 属性 环:判定,长度,个数 模板 547. 朋友圈 并查集的回滚 题目 (1) 加边连通性 261. 以图判树 305. 岛屿数量 II 1627. 带阈值的图连通性 1101.

图论2-树

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

力扣1203-项目管理,双层拓扑排序

双层拓扑排序 拓扑排序 $1 题目题目链接 1203. 项目管理 题目描述公司共有 n 个项目和 m 个小组,每个项目要不没有归属,要不就由其中的一个小组负责。 我们用 group[i] 代表第 i 个项目所属的小组,如果这个项目目前无人接手,那么 group[i] 就等于 -1。(项目和小组都是从零开始编号的) 请你帮忙按要求安排这些项目的进度,并返回排序后的项目列表: 同一小组的项目,

BFS拓扑排序

拓扑排序算法及其 BFS 实现(Kahn算法) 求排序结果 判断图中是否有环 拓扑排序的 DFS 实现(开栈保存拓扑排序的结果) 拓扑排序的存在性 拓扑排序的唯一性 拓扑排序的方案数 题目 802. 找到最终的安全状态 207. 课程表 269. 火星词典 210. 课程表 II 444. 序列重建 1203. 项目管理 329. 矩阵中的最长递增路径 $1 拓扑排序算法拓扑排序:

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 这一步用

带权图最短路径

BFS 815. 公交路线 864. 获取所有钥匙的最短路径 状态压缩BFS dijkstra 数组实现:$O(E+V^{2})$ 堆实现:$O(ElogV + VlogV)$ 882. 细分图中的可到达结点 bellman ford: $O(VE)$ 可以处理负权 可以检测负环 787. K 站中转内最便宜的航班 spfa: $O(VE)$: bellman ford 的优化,

【搜索难题】力扣864-获取所有钥匙的最短路径

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

惰性更新

栈排序 双栈 将贡献暂存在当前节点,访问时再下传 惰性更新 将贡献暂存在当前节点,访问时再下传 栈排序 线段树区间修改 / 力扣699-平衡树区间模块,线段树区间修改,RMQ 保存贡献序列,查询时在执行:力扣1381-设计一个支持增量操作的栈 保存操作序列,查询时再执行:力扣1476-子矩形查询,延迟计算 保存删除标记,访问到时再执行删除 堆的删除: 力扣480-滑动窗口中位数 闭散

【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

力扣164-桶排序

桶排序 $1 题目题目链接164. 最大间距 题目描述给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。 说明: 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。 样例 示例 1:输入: [3,6,9,1]输出: 3解释: 排序后的数组是 [1,3,6,9

力扣324-摆动排序II,三色排序应用

基本思路:先排序,再做映射 下标映射: 映射的思想和索引数组的思想的联系 三色排序 $1 题目题目链接 324. 摆动排序 II 题目描述给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序 说明:你可以假设所有输入都会得到有效的结果。 进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1

sed操作集锦

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

数组排序

912. 排序数组 基于比较的主流排序 基于插入 基于选择 基于交换 归并排序 不基于比较的主流排序: 非比较排序 非主流排序 非主流排序 链表排序 $0 关于排序稳定性的结论不稳定的排序,都可以通过多关键字排序的办法变成稳定排序(第二个关键字是数组下标) 稳定排序:插入排序,基数排序,归并排序,冒泡排序,计数排序 不稳定的排序:快速排序,希尔排序,选择排序,堆排序 $1 基于比较

非比较排序

912. 排序数组 计数排序 75. 颜色分类 三色排序 280. 摆动排序 324. 摆动排序 II: 三色排序是其中一步:上坡,下坡,平原可以视为三种颜色 274. H 指数 945. 使数组唯一的最小增量 1122. 数组的相对排序 桶排序 164. 最大间距 347. 前 K 个高频元素 451. 根据字符出现频率排序 825. 适龄的朋友 基数排序 $1.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 平台空间超限问题,实践了图

力扣271-字符串的编码与解码

用非 ASCII 作分隔符, 类似于树的序列化 449. 序列化和反序列化二叉搜索树 428. 序列化和反序列化 N 叉树 297. 二叉树的序列化与反序列化 分块编码(HTTP v1.1 使用的编码) 扩展 哈夫曼树哈夫曼编码 贪心-哈夫曼编码 Redis字符串类型内部编码 Redis中字符串的编码 $1 题目题目链接271. 字符串的编码与解码 题目描述请

Redis中字符串的编码

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