Archive: 2020/6

2020
算法动态规划

数位DP

摘要: 数位 DP 的算法原理，题目列表以及题解 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 数位 DP 在基础的动态规划问题当中算是比较难的一类，因为数位 DP 的状态的物理意义不太好理解。其它

吐槽改进日志

hexo中插入音乐

摘要: 本文介绍在 hexo 中插入音乐的方法。 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings Markdown 通用的音乐视频插入方法(1) iframe 标签以下代码从网易云音

算法数据结构

单调栈题目汇总

摘要: 单调栈的题目汇总 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 单调栈基本思想和模板单调栈的算法原理和代码模板看这篇文章：单调栈。 单调栈的题目以下是单调栈的题目列表，思路类似，可以集

吐槽钢笔图鉴

万宝龙粉王妃

摘要: 万宝龙摩洛哥王妃 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 万宝龙摩洛哥王妃，2020年1月全新入手价 3600

算法数据结构

单调栈

单调栈的核心使用场景：摊销O(1)地获得所有位置上两侧第一个比它大/小的数的位置 基本模型：直方图最大矩形 单调栈题目列表: 单调栈题目汇总 $0 单调栈基本模型模型问题数组 A[i], 求 L[i], R[i] 12L[i] := [0..i-1] 上离 i 最近的大于 A[i] 的下标R[i] := [i+1..n-1] 上离 i 最近的大于 A[i] 的下标 84.

算法leetcode

力扣315-索引数组,归并树

索引数组以及在索引数组上做CDQ分治 归并树的思考过程：归并排序 -> CDQ分治 -> 归并树 归并树应用：无修改区间大于 x 的元素个数问题 $1 题目题目链接315. 计算右侧小于当前元素的个数 题目描述给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素

算法leetcode

力扣215-快速选择算法,划分树

topK 问题有 3 种主流解法 把原始数据视为数据流，然后用堆始终维护前 K 个元素。困难的问题，一般要从堆中保存的元素，以及堆中元素的排序规则入手。 快速选择算法，是一种减治算法，它的划分 partition 进而转化为子问题的思路与快排中的划分方式完全相同。按照该划分 partition 的思路把子问题的结果组织成树形结果保存下来共后续查询，得到划分树(与归并树类似，归并树保存的是归并

算法leetcode

力扣169,299-摩尔投票

求众数问题一般有3种主流方法 直接开哈希表计数最容易想到，但是需要 O(N) 空间 众数出现次数的下界(169题是n/2，229题是n/3)给定的话，可以抽象成topK问题 摩尔投票(多数投票) 分治法 $1 题目题目1链接169. 多数元素 题目1描述给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 $⌊ n/2 ⌋$ 的元素。 你可以

算法leetcode

力扣1157-分块查找表,无修改区间众数

先找可能的候选答案，再验证答案，以下为选出可能候选的一些方法和时间复杂度 随机化 $O(K)$，K 为尝试次数 转换为区间第 k 大，k = j + 1 - (j - i + 1) / 2 - i，可以用划分树 $O(\log N)$ 分块查找表 $O(\sqrt{N})$ 摩尔投票 $O(N)$ 用线段树维护的摩尔投票 $O(\log N)$ 扩展：分块查找表做带修改的 RMQ $

算法leetcode

力扣699-平衡树区间模块,线段树区间修改,RMQ

多次查询区间的最值，也称 RMQ 问题。是一个常用组件。稀疏表和线段树是 RMQ 的两种主流做法。 其中稀疏表适用与数据不变的情况，线段树适用于数据会改变的情况(可能是单点修改或区间修改) 线段树的区间修改模板 数组写法 链式写法 用平衡树维护区间动态插入删除的区间模块，是一个常用组件 实现区间模块 715. Range 模块 扫描线+区间模块处理矩形问题：横轴区间的左右端点作为两

算法数据结构

二维线段树,二维树状数组

以下二维树状数组和二维线段树的内容不含区间修改。 二维树状数组 二维线段树的两种实现方式: 四叉树和树套树 四叉树有链式写法和数组写法 树套树一般不写链式 四分分治：1274. 矩形内船只的数目 $1 题目题目链接308. 二维区域和检索 - 可变 题目描述给你一个 2D 矩阵 matrix，请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形

算法基础算法

区间问题汇总

摘要: 本文总结了 leetcode 上的区间问题相关的题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 力扣上 2000 以内的区间类的题一共 41 道题，按解决方案和问题模型分类。区间类的题有

算法leetcode

力扣1483-树节点的第K个祖先

第 193 场周赛 D 题 LCA 问题 倍增法做 LCA 的在线询问 DFN 序 LCA 问题汇总 $1 题目题目链接1483. 树节点的第 K 个祖先 题目描述给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。 请你设计并实现 getKthAncestor(int nod

算法数据结构

离散化,权值线段树,权值树状数组

离散化模板 权值线段树模板 权值树状数组模板 CDQ 分治 $1 题目题目链接493. 翻转对 题目描述给定一个数组 nums ，如果 $i < j$ 且 $nums[i] > 2 * nums[j]$ 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 数据范围 给定数组的长度不会超过50000。输入数组中的所有数字都在32位整数的表示范围内。

算法图论

带权图最短路径算法与实现

摘要: 带权图单源最短路 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以力扣 743 为模板题来看一下带权图的单源最短路问题的各种算法的原理以及实现。涉及到以下算法： dkijstra

算法数据结构

线段树,树状数组

以下树状数组和线段树的内容不含区间修改。区间修改的内容参考 力扣699-平衡树区间模块,RMQ 线段树单点修改区间查询模板 链式写法 数组写法 树状数组单点修改区间查询模板 线段树和树状数组的区别和联系 $1 题目题目链接307. 区域和检索 - 数组可修改 题目描述给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点

算法基础算法

区间合并问题

摘要: 本文我们以力扣 56 来看一下区间合并问题的各种解法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们系统串讲一下区间合并问题。这个问题有很多解法，每个解法都是主流经典算法。同时区间也

算法字符串

字符串精确匹配

摘要: 字符串精确匹配方法汇总 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以 leetcode 第 28 题为模板题，总结一下字符串精确匹配的各种算法。 字符串精确匹配主流算法 暴力算