- 博客(1040)
- 资源 (86)
- 收藏
- 关注
原创 【动态规划 状态机dp 性能优化】3098. 求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
2024-04-22 07:00:00 1156 31
原创 线段树汇总
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。区间更新(查询)的时间复杂度是O(logn),使用懒惰法只会影响以下四类节点,每类节点数量都不超过logn。一,左边界及其祖先。二,右边界及其祖先。三,第一类的兄弟节点。四,第二类的兄弟节点。
2024-04-18 08:24:29 1063 39
原创 【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
给你一个整数数组 coins 表示不同面额的硬币,另给你一个整数 k 。你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。返回使用这些硬币能制造的 第 kth 小 金额。
2024-04-15 07:00:00 2658 77
原创 【数学归纳法 组合数学】容斥原理
要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
2024-04-23 17:00:00 622 6
原创 【数学归纳法 反证法】菲蜀定理
裴蜀定理(或贝祖定理,Bézout's identity)得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a、b和它们的最大公约 数d,关于未知数x和y的线性不定方程(称为裴蜀等式):若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1.
2024-04-23 07:00:00 468 9
原创 【状态机dp 动态规划】100290. 使矩阵满足条件的最少操作次数
给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中,你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后,你需要确保每个格子 grid[i][j] 的值满足:如果下面相邻格子存在的话,它们的值相等,也就是 grid[i][j] == grid[i + 1][j](如果存在)。如果右边相邻格子存在的话,它们的值不相等,也就是 grid[i][j] != grid[i][j + 1](如果存在)。请你返回需要的 最少 操作数目。
2024-04-22 17:00:00 1280 10
原创 【图论 单源最短路】100276. 最短路径中的边
给你一个 n 个节点的无向带权图,节点编号为 0 到 n - 1 。图中总共有 m 条边,用二维数组 edges 表示,其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。对于节点 0 为出发点,节点 n - 1 为结束点的所有最短路,你需要返回一个长度为 m 的 boolean 数组 answer ,如果 edges[i] 至少 在其中一条最短路上,那么 answer[i] 为 true ,否则 answer[i] 为 false 。请你返回
2024-04-21 14:35:24 1559 13
原创 【状态压缩 并集查找 图论】2157. 字符串分组
给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中,每个字母都至多只出现一次。如果通过以下操作之一,我们可以从 s1 的字母集合得到 s2 的字母集合,那么我们称这两个字符串为 关联的 :往 s1 的字母集合中添加一个字母。从 s1 的字母集合中删去一个字母。将 s1 中的一个字母替换成另外任意一个字母(也可以替换为这个字母本身)。数组 words 可以分为一个或者多个无交集的 组 。如果一个字符串与另一个字符串关联,那么它们应当属
2024-04-21 07:00:00 728 2
原创 【位运算 拆位法】1835. 所有数对按位与结果的异或和
列表的 异或和(XOR sum)指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素,那么其 异或和 就等于该元素。例如,[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ,而 [3] 的 异或和 等于 3 。给你两个下标 从 0 开始 计数的数组 arr1 和 arr2 ,两数组均由非负整数组成。根据每个 (i, j) 数对,构造一个由 arr1[i] AND arr2[j](按位 AND 运算)结果组成的列表。其中 0
2024-04-20 17:00:00 1338 12
原创 【位运算 反证法 试填法】2897.对数组执行操作使平方和最大
给你一个下标从 0 开始的整数数组 nums 和一个 正 整数 k 。你可以对数组执行以下操作 任意次 :选择两个互不相同的下标 i 和 j ,同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) ,OR 表示按位 或 运算,AND 表示按位 与 运算。你需要从最终的数组里选择 k 个元素,并计算它们的 平方 之和。请你返回你可以得到的 最大 平方和。
2024-04-20 07:00:00 957 6
原创 【数学归纳法】【位运算】【异或】3068最大节点价值之和
给你一棵 n 个节点的 无向 树,节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你,其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ,其中 nums[i] 表示节点 i 的 价值 。Alice 想 最大化 树中所有节点价值之和。为了实现这一目标,Alice 可以执行以下操作 任意 次(包括 0 次):选择连接
2024-04-19 15:30:00 858 7
原创 【位运算 拆位法 二分】3007. 价值和小于等于 K 的最大数字
给你一个整数 k 和一个整数 x 。整数 num 的价值是由它的二进制表示中,从最低有效位开始,x,2x,3x,以此类推,这些位置上 设置位 的数目来计算。下面的表格包含了如何计算价值的例子。x num Binary Representation Price1 13 000001101 32 13 000001101 12 233 011101001 33 13 000001101 13 362 101101010 2num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 n
2024-04-19 07:00:00 1220 10
原创 【动态规划 状态机dp】3082. 求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。一个整数数组的 能量 定义为和 等于 k 的子序列的数目。请你返回 nums 中所有子序列的 能量和 。
2024-04-18 17:00:00 760 1
原创 【贪心 堆 】3081. 替换字符串中的问号使分数最小
给你一个字符串 s 。s[i] 要么是小写英文字母,要么是问号 '?' 。对于长度为 m 且 只 含有小写英文字母的字符串 t ,我们定义函数 cost(i) 为下标 i 之前(也就是范围 [0, i - 1] 中)出现过与 t[i] 相同 字符出现的次数。字符串 t 的 分数 为所有下标 i 的 cost(i) 之 和 。
2024-04-17 17:00:00 961 3
原创 【位运算 子集状态压缩】982按位与为零的三元组
给你一个整数数组 nums ,返回其中 按位与三元组 的数目。按位与三元组 是由下标 (i, j, k) 组成的三元组,并满足下述全部条件:0
2024-04-17 07:00:00 715 4
原创 【位运算 试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。一次操作中,你可以选择 nums 中满足 0
2024-04-16 17:00:00 1501
原创 【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数
给你一个下标从 0 开始的数组 nums ,它包含 非负 整数,且全部为 2 的幂,同时给你一个整数 target 。一次操作中,你必须对数组做以下修改:选择数组中一个元素 nums[i] ,满足 nums[i] > 1 。将 nums[i] 从数组中删除。在 nums 的 末尾 添加 两个 数,值都为 nums[i] / 2 。你的目标是让 nums 的一个 子序列 的元素和等于 target ,请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列,请你返回 -1 。数组中一个
2024-04-16 07:00:00 959 8
原创 【位运算】3097. 或值至少为 K 的最短子数组 II
给你一个 非负 整数数组 nums 和一个整数 k 。如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ,那么我们称这个数组是 特别的 。请你返回 nums 中 最短特别非空 子数组的长度,如果特别子数组不存在,那么返回 -1 。
2024-04-15 17:00:00 1619 15
原创 【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和
给你两个数组 nums 和 andValues,长度分别为 n 和 m。数组的 值 等于该数组的 最后一个 元素。你需要将 nums 划分为 m 个 不相交的连续 子数组,对于第 ith 个子数组 [li, ri],子数组元素的按位AND运算结果等于 andValues[i],换句话说,对所有的 1
2024-04-14 13:56:55 1406 16
原创 【排序 贪心】3107. 使数组中位数等于 K 的最少操作数
给你一个整数数组 nums 和一个 非负 整数 k 。一次操作中,你可以选择任一元素 加 1 或者减 1 。请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数,我们选择中间两个数的较大值为中位数。
2024-04-14 07:00:00 921 6
原创 【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
给你一个 n 个节点的带权无向图,节点编号为 0 到 n - 1 。给你一个整数 n 和一个数组 edges ,其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。在图中,一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点,且图中存在连接旅途中相邻节点的边。注意,一趟旅途可能访问同一条边或者同一个节点多次。如果旅途开始于节点 u ,结束于节点 v ,我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说,如果经过的
2024-04-13 17:00:00 1190 9
原创 【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II
给你一个下标从 0 开始的整数数组 nums 。定义 nums 一个子数组的 不同计数 值如下:令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组(满足 0
2024-04-13 07:00:00 900 2
原创 【线段树 有序映射】715. Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。半开区间 [left, right) 表示所有 left
2024-04-12 15:30:00 961 2
原创 【线段树】2276. 统计区间中的整数数目
给你区间的 空 集,请你设计并实现满足要求的数据结构:新增:添加一个区间到这个区间集合中。统计:计算出现在 至少一个 区间中的整数个数。实现 CountIntervals 类:CountIntervals() 使用区间的空集初始化对象void add(int left, int right) 添加区间 [left, right] 到区间集合之中。int count() 返回出现在 至少一个 区间中的整数个数。注意:区间 [left, right] 表示满足 left
2024-04-12 07:00:00 1025 5
原创 【线段树】2213. 由单个字符重复的最长子字符串
给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ,一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ,这两个都用来描述 k 个查询。第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。返回一个长度为 k 的数组 lengths ,其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子
2024-04-11 17:00:00 659 1
原创 【线段树】【众数】1157数组中占绝大多数的元素
设计一个数据结构,有效地找到给定子数组的 多数元素 。子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。实现 MajorityChecker 类:MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数,如果不存在这样的元素
2024-04-10 17:00:00 791 2
原创 【状态机dp】【 排序 】 2809使数组和小于等于 x 的最少时间
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒,对于所有下标 0
2024-04-10 07:00:00 894 7
原创 【数组】【最长距离】使循环数组所有元素相等的最少秒数
给你一个下标从 0 开始长度为 n 的数组 nums 。每一秒,你可以对数组执行以下操作:对于范围在 [0, n - 1] 内的每一个下标 i ,将 nums[i] 替换成 nums[i] ,nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。注意,所有元素会被同时替换。请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。
2024-04-09 17:00:00 626
原创 【图论 状态压缩 枚举】2959. 关闭分部的可行集合数目
一个公司在全国有 n 个分部,它们之间有的有道路连接。一开始,所有分部通过这些道路两两之间互相可以到达。公司意识到在分部之间旅行花费了太多时间,所以它们决定关闭一些分部(也可能不关闭任何分部),同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。两个分部之间的 距离 是通过道路长度之和的 最小值 。给你整数 n ,maxDistance 和下标从 0 开始的二维整数数组 roads ,其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi
2024-04-09 07:00:00 1029 5
原创 【线段树】【前缀和】:1687从仓库到码头运输箱子
你有一辆货运卡车,你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ,其中 boxes[i] = [portsi, weighti] 。portsi 表示第 i 个箱子需要送达的码头, weightsi 是第 i 个箱子的重量。portsCount 是码头的数目。maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重
2024-04-08 17:00:00 971
原创 【单源最短路 图论】882. 细分图中的可到达节点
给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。图用由边组成的二维数组 edges 表示,其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边,cnti 是将边 细分 后的新节点总数。注意,cnti == 0 表示边不可细分。要 细分 边 [ui, vi] ,需要将其替换为 (cnti + 1) 条新边,和 cnti 个新节点。新节点为 x1, x2,
2024-04-08 07:00:00 2226 28
原创 【线段树】1622. 奇妙序列
请你实现三个 API append,addAll 和 multAll 来实现奇妙序列。请实现 Fancy 类 :Fancy() 初始化一个空序列对象。void append(val) 将整数 val 添加在序列末尾。void addAll(inc) 将所有序列中的现有数值都增加 inc 。void multAll(m) 将序列中的所有现有数值都乘以整数 m 。int getIndex(idx) 得到下标为 idx 处的数值(下标从 0 开始),并将结果对 109 + 7 取余。如果下标大于等于序
2024-04-07 17:00:00 625 2
原创 【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
一个音乐会总共有 n 排座位,编号从 0 到 n - 1 ,每一排有 m 个座椅,编号为 0 到 m - 1 。你需要设计一个买票系统,针对以下情况进行座位安排:同一组的 k 位观众坐在 同一排座位,且座位连续 。k 位观众中 每一位 都有座位坐,但他们 不一定 坐在一起。由于观众非常挑剔,所以:只有当一个组里所有成员座位的排数都 小于等于 maxRow ,这个组才能订座位。每一组的 maxRow 可能 不同 。如果有多排座位可以选择,优先选择 最小 的排数。如果同一排中有多个座位可以坐,优先选择
2024-04-07 07:00:00 744 8
原创 【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
给你三个 正整数 n 、x 和 y 。在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1
2024-04-06 17:00:00 1623 6
原创 【图论】【广度优先】【 并集查找】2092 找出知晓秘密的所有专家
给你一个整数 n ,表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ,其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后,给你一个整数 firstPerson 。专家 0 有一个 秘密 ,最初,他在时间 0 将这个秘密分享给了专家 firstPerson 。接着,这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达
2024-04-06 07:00:00 911 3
原创 【深度优先】【树上倍增 】2846. 边权重均等查询
现有一棵由 n 个节点组成的无向树,节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。另给你一个长度为 m 的二维整数数组 queries ,其中 queries[i] = [ai, bi] 。对于每条查询,请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中,你可以选择树上的任意一条
2024-04-05 15:00:00 768
原创 【图论】【基环内向树】【广度优先】【深度优先】2127. 参加会议的最多员工数
一个公司准备组织一场会议,邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子,可以坐下 任意数目 的员工。员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工,每位员工 当且仅当 他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite ,其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
2024-04-05 07:00:00 869
原创 【逆向思考 】【拓扑排序】1591. 奇怪的打印机 II
给你一个奇怪的打印机,它有如下两个特殊的打印规则:每一次操作时,打印机会用同一种颜色打印一个矩形的形状,每次打印会覆盖矩形对应格子里原本的颜色。一旦矩形根据上面的规则使用了一种颜色,那么 相同的颜色不能再被使用 。给你一个初始没有颜色的 m x n 的矩形 targetGrid ,其中 targetGrid[row][col] 是位置 (row, col) 的颜色。如果你能按照上述规则打印出矩形 targetGrid ,请你返回 true ,否则返回 false 。
2024-04-04 17:00:00 711 1
原创 【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值
给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。总共有 n 名玩家,玩家 编号 互不相同,且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏,receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己,也就是说 receiver[i] 可能等于 i 。你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家,球会被传 恰好 k 次。如果选择编号为 x 的玩家作为开始玩家,定义函数 f(x) 表
2024-04-04 07:00:00 1660 29
搜索矩阵C++实现:二分查找Z形查找
2023-12-17
长度最短的子数组C++实现
2023-12-10
[二分查找双指针]LeetCode881: 救生艇
2023-12-03
两数之和 - 输入有序数组
2023-11-26
C++二分查找算法:132 模式
2023-11-12
C++算法:第 N 位数字原理、源码、测试用例
2023-11-05
C++二分查找算法应用:最长递增子序列 原理、源码、测试用例
2023-10-29
二分应用:峰值查找 原理、源码、测试用例
2023-10-22
C++算法:前缀和基础
2023-10-15
时间复杂度O(40n*n)的C++算法:修改图中的边权
2023-10-14
多源最短路径的原理及C++实现
2023-10-04
堆优化迪氏最短单源路径原理及C++实现
2023-10-03
.有向图计数优化版原理及C++实现
2023-10-02
有向图访问计数的原理及C++实现
2023-10-01
朴素迪氏最短单源路径的原理及C++源码及测试用例
2023-09-30
01BFS最短距离原理和C++实现
2023-09-29
深度优先搜索(BFS)的原理和C++实现
2023-09-28
美丽塔单调栈O(n)解法
2023-09-27
较难算法: 美丽塔 时间复杂度O(nlongn)
2023-09-24
让数组不相等的最小总代价
2023-09-23
喜缺全书算法册 C++实现
2023-09-17
二分查找旋转数组源码和视频
2023-08-20
《闻缺陷则喜》之《主册》
2022-09-10
简单的C#类 生成对应的C#类
2021-11-07
保存文件的同时删除文件,保存用时会略微升高
2021-10-11
多线程样例一 读写参数文件
2021-09-09
《闻缺陷则喜》之《软件开发的那些人》 20230917
2021-08-09
作为公共组软件工程师如何工作
2019-02-10
士农库1.1 头文件、lib、dll 两个测试项目
2019-02-10
面试北京XX数通总结
2019-01-23
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人