闻缺陷则喜何志丹-CSDN博客

原创线段树汇总

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。区间更新（查询）的时间复杂度是O(logn)，使用懒惰法只会影响以下四类节点，每类节点数量都不超过logn。一，左边界及其祖先。二，右边界及其祖先。三，第一类的兄弟节点。四，第二类的兄弟节点。

2024-04-18 08:24:29 568 6

原创【状态压缩容斥原理组合数学】100267. 单面值组合的第 K 小金额

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。你有无限量的每种面额的硬币。但是，你不能组合使用不同面额的硬币。返回使用这些硬币能制造的第 kth 小金额。

2024-04-15 07:00:00 1446 64

原创图论知识汇总

深度优先广度优先

2024-04-11 07:00:00 1222 82

原创【贪心堆】3081. 替换字符串中的问号使分数最小

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。对于长度为 m 且只含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同字符出现的次数。字符串 t 的分数为所有下标 i 的 cost(i) 之和。

2024-04-17 17:00:00 664 3

原创【位运算子集状态压缩】982按位与为零的三元组

给你一个整数数组 nums ，返回其中按位与三元组的数目。按位与三元组是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：0

2024-04-17 07:00:00 483 4

原创【位运算试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。一次操作中，你可以选择 nums 中满足 0

2024-04-16 17:00:00 1269

原创【位运算贪心】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 883 8

原创【位运算】3097. 或值至少为 K 的最短子数组 II

给你一个非负整数数组 nums 和一个整数 k 。如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是特别的。请你返回 nums 中最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。

2024-04-15 17:00:00 1424 15

原创【动态规划区间dp 位运算】100259. 划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。数组的值等于该数组的最后一个元素。你需要将 nums 划分为 m 个不相交的连续子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1

2024-04-14 13:56:55 1285 16

原创【排序贪心】3107. 使数组中位数等于 K 的最少操作数

给你一个整数数组 nums 和一个非负整数 k 。一次操作中，你可以选择任一元素加 1 或者减 1 。请你返回将 nums 中位数变为 k 所需要的最少操作次数。一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。

2024-04-14 07:00:00 911 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 1168 9

原创【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II

给你一个下标从 0 开始的整数数组 nums 。定义 nums 一个子数组的不同计数值如下：令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0

2024-04-13 07:00:00 892 2

原创【线段树有序映射】715. Range 模块

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为半开区间的范围并查询它们。半开区间 [left, right) 表示所有 left

2024-04-12 15:30:00 953 2

原创【线段树】2276. 统计区间中的整数数目

给你区间的空集，请你设计并实现满足要求的数据结构：新增：添加一个区间到这个区间集合中。统计：计算出现在至少一个区间中的整数个数。实现 CountIntervals 类：CountIntervals() 使用区间的空集初始化对象void add(int left, int right) 添加区间 [left, right] 到区间集合之中。int count() 返回出现在至少一个区间中的整数个数。注意：区间 [left, right] 表示满足 left

2024-04-12 07:00:00 1018 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 655 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 784 2

原创【状态机dp】【排序】 2809使数组和小于等于 x 的最少时间

给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0

2024-04-10 07:00:00 889 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 621

原创【图论状态压缩枚举】2959. 关闭分部的可行集合数目

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。两个分部之间的距离是通过道路长度之和的最小值。给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi

2024-04-09 07:00:00 1020 5

原创【线段树】【前缀和】：1687从仓库到码头运输箱子

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有箱子数目的限制和总重量的限制。给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [portsi, weighti] 。portsi 表示第 i 个箱子需要送达的码头， weightsi 是第 i 个箱子的重量。portsCount 是码头的数目。maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重

2024-04-08 17:00:00 965

原创【单源最短路图论】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 2182 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 619 2

原创【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票

一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：同一组的 k 位观众坐在同一排座位，且座位连续。k 位观众中每一位都有座位坐，但他们不一定坐在一起。由于观众非常挑剔，所以：只有当一个组里所有成员座位的排数都小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能不同。如果有多排座位可以选择，优先选择最小的排数。如果同一排中有多个座位可以坐，优先选择

2024-04-07 07:00:00 739 8

原创【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

给你三个正整数 n 、x 和 y 。在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1

2024-04-06 17:00:00 1606 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 902 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 761

原创【图论】【基环内向树】【广度优先】【深度优先】2127. 参加会议的最多员工数

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张圆形的桌子，可以坐下任意数目的员工。员工编号为 0 到 n - 1 。每位员工都有一位喜欢的员工，每位员工当且仅当他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己。给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的最多员工数目。

2024-04-05 07:00:00 861

原创【逆向思考】【拓扑排序】1591. 奇怪的打印机 II

给你一个奇怪的打印机，它有如下两个特殊的打印规则：每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。一旦矩形根据上面的规则使用了一种颜色，那么相同的颜色不能再被使用。给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 targetGrid[row][col] 是位置 (row, col) 的颜色。如果你能按照上述规则打印出矩形 targetGrid ，请你返回 true ，否则返回 false 。

2024-04-04 17:00:00 701 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 1631 29

原创【图论】【树】【拓扑排序】2603. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：收集距离当前节点距离为 2 以内的所有金币，或者移动到树中一个相邻节点。你需要

2024-04-03 17:00:00 687 1

原创【拓扑排序】【图论】1203. 项目管理

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：同一小组的项目，排序后在列表中彼此相邻。项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目

2024-04-03 07:00:00 792 4

原创【图论】【拓扑排序】1857. 有向图中最大颜色值

给你一个有向图，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的颜色（下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条有向边。图中一条有效路径是一个点序列 x1 -> x2 -> x3 -> ... -> xk ，对于所有 1

2024-04-02 17:00:00 768

原创【反悔贪心】【优先队列】3049. 标记所有下标的最早秒数 II

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中所有下标。从第 1 秒到第 m 秒（包括第 m 秒），对于每一秒 s ，你可以执行以下操作之一：选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。将 nums[changeIndices[s]] 设置成任意的非负整数。选择范围 [1, n] 中的一个下标 i ，满足 num

2024-04-02 12:06:19 876 5

原创【动态规划】【最长子序列】2901. 最长相邻不相等子序列 II

给你一个整数 n 和一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的数组 groups ，两个数组长度都是 n 。两个长度相等字符串的汉明距离定义为对应位置字符不同的数目。你需要从下标 [0, 1, ..., n - 1] 中选出一个最长子序列，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，它需要满足以下条件：相邻下标对应的 groups 值不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij]

2024-04-01 17:00:00 732 3

原创【键值皆有序map 线段树数学】100240. 最小化曼哈顿距离

给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。两点之间的距离定义为它们的曼哈顿距离。请你恰好移除一个点，返回移除后任意两点之间的最大距离可能的最小值。

2024-04-01 07:00:00 3436 117

原创【图轮】【最小生成树】【并集查找】1489. 找到最小生成树里的关键边和伪关键边

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所

2024-03-31 17:17:33 780 6

原创【二分图】【二分图最大匹配】LCP 04. 覆盖

骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。

2024-03-31 07:00:00 973 4

原创【数位dp】【数论】【动态规划】2999. 统计强大整数的数目

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个正整数。如果一个正整数 x 末尾部分是 s （换句话说，s 是 x 的后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是强大的。请你返回区间 [start..finish] 内强大整数的总数目。如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是

2024-03-30 17:00:00 997 4

原创【动态规划】1223. 掷骰子模拟

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。不过我们在使用它时有个约束，就是使得投掷骰子时，连续掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回模 10^9 + 7 之后的结果。

2024-03-30 07:00:00 697 6

原创【单调栈】【网格】【柱图面积】85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

2024-03-29 15:30:00 845 5

利用二分查找解决H指数问题

利用二分查找解决H指数问题。

2024-01-01

搜索矩阵C++实现：二分查找Z形查找

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

2023-12-17

长度最短的子数组C++实现

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。示例 1：输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：输入：target = 4, nums = [1,4,4] 输出：1 示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0 提示： 1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105

2023-12-10

[二分查找双指针]LeetCode881: 救生艇

给定数组 people 。people[i]表示第 i 个人的体重，船的数量不限，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回承载所有人所需的最小船数。

2023-12-03

两数之和 - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

2023-11-26

C++二分查找算法：132 模式

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。如果 nums 中存在 132 模式的子序列，返回 true ；否则，返回 false 。

2023-11-12

C++算法：第 N 位数字原理、源码、测试用例

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。示例 1：输入：n = 3 输出：3 示例 2：输入：n = 11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。提示： 1 <= n <= 231 – 1

2023-11-05

C++二分查找算法应用：最长递增子序列原理、源码、测试用例

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例 1：输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：输入：nums = [0,1,0,3,2,3] 输出：4 示例 3：输入：nums = [7,7,7,7,7,7,7] 输出：1 参数范围： 1 <= nums.length <= 2500 -104 <= nums[i] <=104

2023-10-29

二分应用：峰值查找原理、源码、测试用例

1. 题目长度为n的数组nums，请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。 n等于1 i等于0 n>1 i等于0 nums[i] >nums[i+1] n>1 i等于n-1 nums[i] > nums[i-1] 0<i<n-1 nums[i]>nums[i-1] nums[i]>nums[i+1] 题目保证nums[i]不等于nums[i+1]。 2. 分析假定： nums[left,r)符合nums[left]>nums[left-1]，且nums[r-1]>nums[r]。显然初始情况nums[0,n)符合。推论一：如果[left,r)的长度为1，则left就是返回的索引。推论二：假定left < mid<r。如果mid[mid] > mid[mid-1],则nums[mid,r)也符合假定。如果mid[mid] < mid[mid-1]，则nums[left,mid)也符合假定。推论三：推论二也可以也可以理解成分别抛弃[left,mid)和[mid,r)。令mid = left+(r-left)/2，由于r-left>=2，所以left<mid<

2023-10-22

C++算法：前缀和基础

长度为n的数组nums，共有n+1个以nums[0]开始的子数组。索引范围分别为[0,i)，i取值区间[0,n]。preSum[i]记录子数组[0,i)的和。比如：nums = {1,2,3,4},则preSum = {0,1,3,6,10}。通过preSum，我们可以求任意nums的子数组和。子数组[i,j)等于子数组[0,j)减去[0,i)，也就是子数组[i,j)的和等于preSum[j] – preSum[i]。如果i等于j，则preSum[i]-preSum[i]，和为0，符合计算公式。如果i大于j，则非法，需要提前排除。

2023-10-15

时间复杂度O(40n*n)的C++算法：修改图中的边权

给你一个 n 个节点的无向带权连通图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。部分边的边权为 -1（wi = -1），其他边的边权都为正数（wi > 0）。你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 10^9] 中的正整数，使得从节点 source 到节点 destination 的最短距离为整数 target 。如果有多种修改方案可以使 source 和 destination 之间的最短距离等于 target ，你可以返回任意一种方案。如果存在使 source 到 destination 最短距离为 target 的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个空数组。注意：你不能修改一开始边权为正数的边。

2023-10-14

多源最短路径的原理及C++实现

当一层循环执行完后，m_vMat[i1][i2]表示经过[0,i)中的任意个点的最短距离。初始状态下, m_vMat[i1][i2]表示直达的最小距离，也就是经过0个点。通过[0,i)中任意个点，i1到i2的最短路径记为PrePathi1i2，通过[0,i+1)中任意个点，i1到i2的距离的路径为Pathi1i2，如果Path不经过Pathi1i2，则和PrePathi1i2相同。如果经过则可以拆分成{i1…i}+{i…i2}，显然{i1…i}是PrePathi1i,{i…i2}是PrePathii2，否则替换成PrePathi1i和PrePathii2。 m_vMat同时表示PreMath和Math，如果m_vMat[i1][i]或m_vMat[i][i2]已经更新，会带来错误的结果么？结果是不会，会更新但值不变。当i1等于i时： m_vMat[i][i2] = min(…, m_vMat[i][i] + m_vMat[i][i2]); 由于m_vMat[i][i]为0,所以右式就是左式。当i2等于i时，类似。

2023-10-04

堆优化迪氏最短单源路径原理及C++实现

4.1. 时间复杂度 O(ElogE)，E是边数。适用与稀疏图。 4.2. 使用前提边的权为正。可以非连通，非连通的距离为-1。 4.3. 原理优选队列（小根堆）记录两个数据：当前点到源点距离，当前点。先处理距离小的点；如果距离相等，先处理谁都可以。可以用pair记录，不用重写小于。优先队列只记录如下情况的距离：一，{0，源点}。二，任意点的最短距离和可以直达的边。如果是有向图，则入队数量等于边数，计算出起点最短路径的那一轮。无向图，则翻倍。显然出队数量等于入队数量。优先队列入队和出队时间复杂度都是O(logn)，故总时间复杂度为O(nlogn)。

2023-10-03

.有向图计数优化版原理及C++实现

不需要拓扑排序，也不需要并集查找，直接dfs了。完成以下三个职责：一，DFS那些端点在环上。二，DFS环上各点此环的长度。三，DFS非环上各点。

2023-10-02

有向图访问计数的原理及C++实现

现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。想象在图上发生以下过程：你从节点 x 开始，通过边访问其他节点，直到你在此过程中再次访问到之前已经访问过的节点。返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。 2 <= n <= 100000 无自环。

2023-10-01

朴素迪氏最短单源路径的原理及C++源码及测试用例

Dijkstra算法，翻译为迪杰斯特拉或狄克斯特拉。在下驽钝，记不住如此长的翻译，故简称迪氏。 3.1.时间复杂度 O(n2)，端点数的平方。 3.2.使用前提边的权为正。可以非连通，非连通的距离为-1。

2023-09-30

01BFS最短距离原理和C++实现

n个端点的无向图，编号范围[0,n)。Edges0表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有路联接。Edges1表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有损坏的路连接。要想让s和d之间至少有一条通道,最小需要维修多少条路。如果无法到达，请返回-1。可能有环，但无自环，重边，可能不联通。

2023-09-29

深度优先搜索(BFS)的原理和C++实现

n个端点的无向图，编号范围[0,n)。每个端点最多4条出边。edges表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有边联接。求s到d的最少需要经过多少条边。如果无法到达，请返回-1。可能有环，但无自环，重边，可能不联通。

2023-09-28

美丽塔单调栈O(n)解法

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。如果以下条件满足，我们称这些塔是美丽的： 1 <= heights[i] <= maxHeights[i] heights 是一个山状数组。如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个山状数组：对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j] 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k] 请你返回满足美丽塔要求的方案中，高度和的最大值。

2023-09-27

较难算法：美丽塔时间复杂度O(nlongn)

2023-09-24

让数组不相等的最小总代价

让数组不相等的最小总代价可运行源码，VS2022 C++17 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的开销为两个下标的和。你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行任意次操作，请你返回达到这个目标的最小总代价。请你返回让 nums1 和 nums2 满足上述条件的最小总代价，如果无法达成目标，返回 -1 。

2023-09-23

喜缺全书算法册 C++实现

当前阶段：以二分查找为主，前缀和为辅，之后会有其它算法的。文字算法见我的博文，视频算法见我的学院课程。给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的开销为两个下标的和。你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行任意次操作，请你返回达到这个目标的最小总代价。请你返回让 nums1 和 nums2 满足上述条件的最小总代价，如果无法达成目标，返回 -1 。给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。如果以下条件满足，我们称这些塔是美丽的：

2023-09-17

二分查找旋转数组源码和视频

包括视频和三个版本的源码（初始、寻找右数组左边界、完成）已知整数数组nums，先按升序排序后，再旋转。旋转k位后，元素分别为nums[k],nums[k+1]...nums[0]...nums[k-1]。请查找target 是否存在，如果存在返回所在索引；否则返回-1。假定nums没有重复的元素。假定排序后的数组为{1,2,3,4,5}。旋转0位：不变。旋转1位：{2,3,4,5,1} 旋转2位：{3,4,5,1,2} 旋转3位：{4,5,1,2,3} 旋转4位：{5,1,2,3,4} 1.解题思路观察后，可以得到如下结论：旋转数组，可以拆分成左右两个升序数组，且左数组的任意元素都大于右数组的任意元素。分两步：一，找到数组的分界线RBegin，[0,RBegin)是左数组，[RBegin,n)是右数组。特殊情况：只有一个升序数组，则RBegin为0，左数组为空。如果是小于等于nums.back()，在右边找；否则在左边找。升序寻找元素之前已经讲过了，就不累赘了。

2023-08-20

闻缺陷则喜之平凡的经历

自己的经历：一，工作中的踩得坑。二，生活的点点滴滴。三，女儿成长相关。四，投资理财的亏损与教训

2023-08-18

《闻缺陷则喜》之《主册》

闻缺陷则喜 1 第一章：平凡的经历 5 第二章：观念与想法 5 1. 基础 6 1.1. 认知鸿沟 6 2. 传播 6 3. 沟通 6 3.1. 淡化对错 6 3.2. 不要随意批评别人 6 3.3. 参与感 6 3.4. 如果错了，马上认错 7 3.5. 从别人的立场说服对方 7 3.6. 具体到场景 7 4. 交往与合作 7 4.1. 双赢思维 7 4.2. 合作层次 8 4.3. 能力+信息（情报）+资源=成就 8 5. 工作相关 8 5.1. 金融骗局 8 5.2. 对小白而言创业比股票危险的多 9 5.3. 投资比创业稳妥的多 9 5.4. 程序员干不到30岁 9 5.5. 忠诚度与能力 10 5.6. 拒绝无意义加班 10 5.7. 内卷的历史 11 5.8. 关于社保 11 6. 家庭相关 12 6.1. 我的遗产 12 6.2. 金钱观 12 6.3. 借贷观 13 6.4. 女儿的婚姻 13 6.5. 轶事 14 6.6. 生育观 15 6.7. 教育观 15 6.8. 不要因为担心亲友不舒服，而不指出错误 16 7. 工作技巧 16 7.1. 八二原理 16 8.

2022-09-10

C# 获取C++的连续数据

C# 获取C++的连续数据。两种方式：1，返回C++指针,2，将值存到C#的数组中。

2022-04-02

闻缺陷则喜版本号20220123

包括：问题定义、系统分析、架构、概要设计、详细设计、测试等！

2022-01-23

闻缺陷则喜2021年12月26.doc

闻缺陷则喜，本人拙作，注将软件工程。

2021-12-26

闻缺陷则喜20211205

包括：问题定义、系统分析、架构、概要设计、详细设计、测试等！

2021-12-07

关于halcon膨胀腐蚀开闭.doc

关于halcon膨胀腐蚀开闭

2021-11-14

简单的C#类生成对应的C#类

开发工具： C#2013 功能：针对简单的C#类，生成对应的非托管C++类，并生成托管C++的转换函数。应用场景：界面层、数据层C#，逻辑层C++。简单的C#类：类型只包括 double string List

2021-11-07

Windows性能监控工具Perfmon使用

2021-10-31

保存文件的同时删除文件，保存用时会略微升高

保存文件的同时删除文件，保存用时会略微升高。没必要花大功夫专门处理保存500文件用时（毫秒）：30906 删除文件同时，保存500文件用时（毫秒）：30263 删除500文件用时（毫秒）：363 保存500文件用时（毫秒）：29155 删除文件同时，保存500文件用时（毫秒）：29258 删除500文件用时（毫秒）：426 保存500文件用时（毫秒）：27992 删除文件同时，保存500文件用时（毫秒）：29068 删除500文件用时（毫秒）：686 保存500文件用时（毫秒）：29172 删除文件同时，保存500文件用时（毫秒）：31837 删除500文件用时（毫秒）：337 保存500文件用时（毫秒）：29373 删除文件同时，保存500文件用时（毫秒）：29563 删除500文件用时（毫秒）：321 保存500文件用时（毫秒）：29663 删除文件同时，保存500文件用时（毫秒）：30180 删除500文件用时（毫秒）：350

2021-10-11

闻缺陷则喜2021九月版

主要增加：C#调用托管C++，托管C++调用C++

2021-09-11

多线程样例一读写参数文件

事情起因：修改配置后，C++函数取读配置xml时，相机缓存满了而引起崩溃。几率发生。解决思路：读文件费时间，所以开一个线程读文件。抽象后的类似demo：假定读文件需要0.6秒，图像处理（用存文件代替）需要0.5秒，各执行100次。类和函数读取文件函数：一，List<int>增加本序号（0开始）。二，随机生成5000整数，加到list<int>中。三，写文件(文件名为序号，如0.txt），文件夹File。四，Sleep(600)。五，记录日志：本函数开始执行时间，结束时间，序号。六，复制List<int>到参数。模拟图像处理函数：一，复制参数二，参数保存到文件，文件名list<int>第一个int，文件夹img。三，Sleep(500)。六，记录日志：本函数开始执行时间，结束时间，序号。参数类（跨线程）：一，从list<int>复制参数。二，复制数据到list<int>。线程：启动线程“读取参数”线程：执行100次读取参数功能。启动线程“模拟图像处理”线程：执行100次模拟图像处理。运行预期结果： File文件夹中有0到100共101个文件。 img有约80个文件。 img有的文件，File文件夹中一定有，且完全相同。用文件夹比较工具（如：BCompare）查看。查看日志：“读取参数”线程约60秒完成，模拟图像处理”线程约50秒完成。

2021-09-09

C#调用C++的类和函数

C#直接调用C++的函数，C#调用托管C++，C++托管调用非托管C++

2021-08-31

《闻缺陷则喜》之《软件开发的那些人》 20230917

软件团队的那些人（理论） 4 1. 引言 5 1.1. 你的灯开着么？ 5 1.2. 货车过山洞 5 1.3. 软件维护之痛 5 2. 软件过程与思想 6 2.1. 基础 6 2.2. 过程模型 12 2.3. 敏捷开发 14 2.4. 编程范式 15 2.5. 工具 16 3. 问题定义 18 3.1. 基础 18 3.2. 过滤概念（可行性分析） 20 3.3. 用户细分 22 3.4. 模式 22 4. 系统分析 23 4.1. 基础 24 4.2. 用户画像 25 1.1 RFM模型 25 4.3. 需求收集与整理 25 4.4. 系统分析 26 5. 架构设计 26 5.1. 开发期质量 26 5.2. 运行期质量 28 5.3. 沟通 35 5.4. 架构内容 36 5.5. 架构模式 38 5.6. 关于重构 39 5.7. 其它 42 6. 概要设计 44 6.1. 设计模式六大原则 44 6.2. 设计模式 45 6.3. 反模式 46 6.4. 模块划分、公共数据、资源设计、接口 46 6.5. 界面设计 49 6.6. 数据存储设计 49 6.7. 工时预估与工作

2021-08-09

作为公共组软件工程师如何工作

作为公共组软件工程师如何工作 1 1 为什么需要公共组 1 1.1 专业化分工带来高效 1 1.2 复用 2 2 公共组成员特点 3 3 公共组成员职责 3 3.1 一般团队公共软件工程师职责 3 3.2 小团队公共软件工程师职责 3 4 已整理的类库介绍 4 4.1 SNGraph 4 4.2 SN 5 4.3 SNMFC 6 4.4 SNSTL 7 4.5 其它 7 5 专业化分工 7 5.1 专业化分工实例 7 5.2 专业化分工优点（亚当斯密） 7 5.3 专业化分工优点（无名高人） 8 5.4 专业化分工缺点 8 6 软件复用 8 6.1 软件复用的优点 8 6.2 软件复用级别 9 6.3 代码复用的类型 9

2019-02-10

士农库1.1 头文件、lib、dll 两个测试项目

4.1 SNGraph 一点、向量基本运算二直线（线段、射线）直线（线段、射线）用起点、方向（单位向量）、线段长度表示。包括如下功能：  点是否在直线上。  假定点在直线上，点到直线起点的有向距离。如果点在直线上，点到直线距离为n。如果n>=0，则点在射线上；如果(n>=0)&&(n <= 线段长度) ，则点在线段上。  两直线是否平行或重合。  两直线是否重合。  两直线是否垂直。  两直线交点。  两非平行直线距离。  求垂足。三平面通过过平面一点和方向（单位矢量）表示平面。包括如下功能：  点到平面的有向距离。通过平面标准法向量和距离，可以求垂足；通过点到平面的距离的正负，可以看出多个点是否在同侧；如果点到平面的距离为0，则点在平面上，否则不在平面上。  直线是否在平面上  平面和直线的交点通过调用其他功能可以实现的功能：  平面的法向量平行于直线，则平面和直线垂直  平面的法向量垂直于直线，则平面和直线平行  平面的法向量平行（垂直）则平面平行(垂直)  平行平面的距离等于平面任意一点到另一平面的距离四矩阵包括以下功能：  初始化为单位矩阵。  为向x,y,z方向缩放建立矩阵。  为任意方向缩放建立矩阵。投影平面，可以通过向平面法线方向缩放0实现。平面镜像，可以通过向平面法线方向缩放-1实现。  为对一个点镜像建立矩阵。  为对一条直线镜像建立矩阵。  为对一条对称轴旋转建立矩阵。  求对应行列式的值。  求逆矩阵。  求转置矩阵。  左乘。  求对应行列式的代数余子式。  常见运算符。 4.2 SN 封装了许多基础的功能。一接口  读写锁。二避免依赖其它类库有些类经常用于库间接口，所以需要避免依赖其它类库。  字符串类、函数，比如：宽字符、多字符间的转换。  时间类。  数组的封装。三其它  将错误信息记录到全局变量中，应用场景：构造函数和析构函数中throw会引起不可预料的问题。  安全缓存，额外开辟若干个字节的空间，并初始化为一个特定值，如果不越界，这些值不会改变。  智能指针，为了将关联降为依赖。CAutoPtr<C> m_pC代替C m_c，头文件中不需要引用C类的头文件。只需要声明C类，在源文件中引用C类的头文件。  MD5。  RSA。  SHA。  考虑溢出的加减法。比如：int型的10亿加20亿，-10亿减20亿。  通过表名、列名、某些列的值生成sql语句。  安全指针和防野指针类。防野指针类：在构造函数中将状态初始为已初始化，在析构函数中将状态设置为已释放。安全指针在使用时之前判断防野指针类释放是“已初始化”，否则抛出异常。  将有参数的函数统一成没参数返回值类型void的仿函数。  遍历文件夹的文件和子文件夹。  随机数和排列组合。  系列化和反系列化。将对象和变量转化成二进制，并将二进制转回变量和对象。  拆分，如字符串。 4.3 SNMFC 一网络功能  网络基本功能：如获取本机IP，通过域名获取IP，IE版本。  HTML对话框的封装类。  用于服务端的，带“回调类”的绑定监听类，利用IO完成端口。  用于客户端的，带“回调类”连接类，利用select模式完成，可以指定是否开启新线程。连接时，可以指定超时时间，默认5秒。如果直接调用系统的connect，超时时间是75秒。  能够自动处理“粘包”、“拆包”的二进制解析类。  安全套接字的辅助类，如：设置发送、连接超时。  比较服务端的某个文件夹和客户端的某个文件夹，并更新那些md5不同的文件。二多线程  用临界区实现的线程锁，和线程读写锁。  窗口辅助类。  开启一个线程并调用一个函数。  开启一个线程并循环调用一个函数。  支持多线程的日志。  启动一个线程，等待若干秒后，Post或Send一个消息后，结束线程。三界面  三态树控件。  列表框扩展类和函数。  树控件的扩展。  组合框的扩展。  关于窗口功能的封装。比如：从左到右依次排列子窗口，排不下则下一行。可以指定行间距。页眉和页脚是行间距的一半。  位图的加载和显示。四其它  Ini文件。  数组封装类。  获取硬件信息，如网卡。  文件或文件夹的常用功能。  注册表的扩展。 4.4 SNSTL  数组（向量）扩展。  用于多线程的向量。  JSON解析。  集合的扩展。  映射的扩展。  指针向量，可以存派生类。  指针映射，可以存派生类。 4.5 其它库  UnitTest，本机单元测试项目，对整个库的重要功能进行单元测试。  SNBCG，著名界面库的扩展，几乎没使用。  SNPicture，图形图像的处理（如转换bmp格式），几乎没使用。  SNMath，数学及数据结构库，几乎没使用。