Tag: 算法

2022春季赛与LCP刷题

摘要: 2022 年春季赛,计划参加 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Leetcode 2022 年春季赛的时间表出来了,个人赛 4 月 15 号报名截止,4 月 1

leetcode题目卡片

摘要: 刷题笔记中质量比较好的题目汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 这是汇总我早期刷题时写的笔记,当时每一道题都会抄题,然后手写思路,当然后来就不这么做了。 因为只是自己的笔记,大

leetcode难题卡片

摘要: 困难题的手写笔记汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 这是汇总我早期刷题时写的笔记,当时每一道题都会抄题,然后手写思路,当然后来就不这么做了。 因为只是自己的笔记,大部分的都是

算法备忘录-2022

摘要: 2022 年想学的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Ref: 算法备忘录-2021 字符串 CYK算法 数据结构 Splay Treap Scapegoat(替罪

模板栏

摘要: 算法代码模板整理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 01 基础算法 02 数据结构 03 字符串 04 搜索 05 动态规划 06 图论 07 组合数学 08 几何 09 数论

面试官如何做好算法题环节的考察

摘要: 算法题主要考察哪些内容 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文主要记录一下算法题面试时,面试官需要注意的一些点,主要参考外企的一些经验。外企的 Tech 主要考察以下 4 点,并

校招笔试疑难杂症记录

摘要: 记录一些在各种群里见过的有意思的或者比较难的题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 1 (阿里2020)Tag: 图论,数学 描述3 个人陆行,目的地有 n 家酒店,通过 n -

适合面试的算法题

摘要: 面经中的概率题,有的没有答案 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 关于算法题面试流程,以及面试官需要注意考察的点,可以参考 面试官在算法题上的考察点。 除了流程要

算法备忘录-2021

摘要: 2021年没有解决的算法问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 图论 最小环问题,dijkstra 解法,基于 Floyd 搜索有向图的所有最小环 leetcode 854,

【连载】leetcode周赛

摘要: 2020 年开始参加周赛的记录及文章 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 时间地点leetcode周赛入口 周赛时间:周日上午 10:30~12:00 双周赛时间:周六晚上 22

力扣754-到达终点数字

推公式 $1 题目题目链接754. 到达终点数字 题目描述在一根无限长的数轴上,你站在0的位置。终点在target的位置。 每次你可以选择向左或向右移动。第 n 次移动(从 1 开始),可以走 n 步。 返回到达终点需要的最小移动次数。 注意:1target是在[-10^9, 10^9]范围中的非零整数。 样例 示例 1:输入: target = 3输出: 2解释:第一次移动,从 0 到 1

LCA,树上倍增,树上差分

LCA 向上标记法(搜索) 236. 二叉树的最近公共祖先 / 面试题 04.08. 首个共同祖先 树上倍增 1483. 树节点的第 K 个祖先 tarjan 算法 LCA 题目 1257. 最小公共区域 235. 二叉搜索树的最近公共祖先 1123. 最深叶节点的最近公共祖先 LCA 应用 树上差分 次小生成树 支配树 $1 LCA问题 给定一棵有根树,若 z 既是 x

区间DP

区间 DP 分治型 减治型 减治型区间DP题目 5. 最长回文子串 647. 回文子串 486. 预测赢家 516. 最长回文子序列 1147. 段式回文 730. 统计不同回文子字符串 1312. 让字符串成为回文串的最少插入次数 1216. 验证回文字符串 III 1278. 分割回文串 III 分治型区间DP题目 312. 戳气球 471. 编码最短长度的

【搜索难题】力扣675-BFS常数优化,Astar,Hadlock算法

BFS 中的常数优化办法 基本BFS12中文版 TLE英文版 1712ms 勉强过 优化1:将 forest[i][j] 值加进 Point 字段,而不在 cmp 中持有 forest 矩阵121944ms英文版 1628 ms 优化2:将 Point 的 x, y 变成 pos (x * m + y)121760ms英文版 1392ms 优化3:将 visited 的索引从 x, y 变成 p

无向图的桥

桥和割点的图论阐释:图论1-基本概念 无向图的桥 寻找桥的算法 1192. 查找集群内的「关键连接」 1489. 找到最小生成树里的关键边和伪关键边 $1 无向图的桥无限图中,如果删除某条边,导致连通分量个数加1,则该条边为桥。 应用:交通系统,社交网络。 一个图中可能有多个桥。 树的所有边都是桥 无向图寻找桥的算法:DFS难点在于在 DFS 中要记录哪些信息。 DFS 遍历图中的边123

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

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

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

力扣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

非比较排序

912. 排序数组 计数排序 75. 颜色分类 三色排序 280. 摆动排序 324. 摆动排序 II: 三色排序是其中一步:上坡,下坡,平原可以视为三种颜色 274. H 指数 945. 使数组唯一的最小增量 1122. 数组的相对排序 桶排序 164. 最大间距 347. 前 K 个高频元素 451. 根据字符出现频率排序 825. 适龄的朋友 基数排序 $1.1 计数排序当

稀疏相似度-倒排索引

double 转 string 时如何控制位数并正确地四舍五入,以下代码注意 1e-9,这是 C++ 的精度误差问题。123stringstream ss;ss << std::fixed << std::setprecision(4);ss << double_val + 1e-9; 倒排索引 $1 题目题目链接面试题 17.26. 稀疏相似度 题目描述两

【冷门算法】乘二取余法-小数十进制转二进制

冷门算法:十进制小数转二进制小数的算法 — 乘二取余 $1 题目题目链接二进制数转字符串 题目描述二进制数转字符串。给定一个介于0和1之间的实数(如0.72),类型为double,打印它的二进制表达式。如果该数字不在0和1之间,或者无法精确地用32位以内的二进制表示,则打印“ERROR”。 32位包括输出中的”0.”这两位。 样例 示例1:输入:0.625输出:”0.101”示例2:输入:0.

手撕平衡树-二叉查找树BST

摘要: 二叉查找树(BST)的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 二叉查找树定义二叉查找树(Binary Search Tree)是指一棵空树

树状数组维护区间最值RMQ

考虑以下需求:给定一个数组 a,支持区间和的查询, 其中 a 中的元素可变,每次变化 a 中的 1 个元素。这个需求用带单点修改和区间查询的线段树或树状数组都可以解决,其中用树状数组的代码量少很多。 如果 a 不变,则是前缀和解决的问题。而对与 a 可变的情况,区间和查询是树状数组解决的最基本的问题,它在力扣上有对应的题目: 线段树,树状数组 二维线段树,二维树状数组 现在需求变一下,把支

单调栈

单调栈的核心使用场景:摊销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.

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

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

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

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

力扣169,299-摩尔投票

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

力扣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 $

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

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

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

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

区间问题汇总

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

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

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

线段树,树状数组

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

分拆类问题分类汇总

摘要: 本文梳理了分拆类的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分拆这个动作在业务场景中是一个非常常见的动作。简单理解就是把一个集合的元素分到若干个小集合里,比如有一个集合 $\{1

力扣135-峰谷类问题

通过贪心策略将问题抽象成山脉上找峰谷的问题 对当前点的判断与左右两边都有关系,左右两侧均有大于小于等于三种情况,综合起来共有 9 种,需要画图辅助理解 峰谷类问题分类汇总 $1 题目题目链接135. 分发糖果 题目描述老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到

力扣1388-3n块披萨

第 22 场双周赛 D 题 通过猜想和证明,将问题抽象为从 n 个元素的环上选最优的 n / 3 个不相邻的元素 环上取任意多不相邻元素的问题:213. 打家劫舍 II n 个点选不相邻的 k 个,最优解是贪心的做法,但是证明比较难难 用堆维护每个时刻最大的点,在双向循环链表上进行贪心模拟 $1 题目题目链接1388. 3n 块披萨 题目描述给你一个披萨,它由 3n 块不同大小的部分组成,

力扣1383-最大的团队表现值

第 180 场周赛 D 题 1e5 的数据范围,一般不会是 DP,因为复杂度正比于状态数$\times$状态转移复杂度,应该往贪心(经常以排序,堆作辅助)、单调栈、滑动窗口等算法去考虑 抽象出 topK 问题,然后考虑 topK 问题的两种解法,分治和堆 最多选择 k 个而不是正好选 k 个,因此堆中元素小于 k 时也要更新答案 topK 问题题目列表 $1 题目题目链接1383. 最大的

topK问题分类汇总

题目 解决方案 373. 查找和最小的K对数字 堆+哈希表去重 1439. 有序矩阵中的第 k 个最小数组和 堆+哈希表去重 / 值域二分 703. 数据流中的第K大元素 堆 / multiset 295. 数据流的中位数 对顶堆 / multiset 480. 滑动窗口中位数 对顶堆 / multiset 668. 乘法表中第k小的数 值域二分 786.

力扣325,1248,1371-前缀状态

HashMap 维护前缀和以便后续的搜索,保存前缀和最早出现的位置 前缀和的值可以理解状态,作为 HashMap 的键,值保存状态最早出现的位置或状态出现过的次数 枚举当前值计算当前状态,根据条件查询历史状态,更新答案 根据情况不必要直接开哈希表,当状态是整数或者可以做状态压缩(把状态映射成整数),可以考虑用数组代替哈希表 (2) 题中奇数出现的次数不会超过数组长度, (3) 题中一个字母的奇偶