- 博客(1944)
- 资源 (4)
- 收藏
- 关注
RSS订阅
原创 请问Pycharm如何实现变量的批量重命名？
Ctrl + R 替换Ctrl + Shift + F 全局查找Ctrl + Shift + R 全局替换
2022-02-15 11:27:27
935
3
原创 Color exploitation in HOG-based traffic sign detection
摘要我们在一个具有挑战性的大规模真实全景图像数据集上研究交通标志检测。核心处理是基于HOG (Histogram of Oriented Gradients)算法，该算法通过在特征向量中加入颜色信息进行扩展。颜色空间的选择对性能有很大的影响，其中我们发现CIELab和YCbCr颜色空间给出了最好的结果。颜色的使用显著提高了检测性能。我们比较了特定算法和HOG算法的性能，并表明HOG在大多数情况下比特定算法的性能高出数十个百分点。此外，我们提出了一种新的迭代支持向量机训练范式来处理背景外观的大变化。这减少
2024-04-12 00:49:46
576
转载 C++的STL（二）
1.构造函数vector():创建一个空vectorvector(int nSize):创建一个vector,元素个数为nSizevector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为tvector(const vector&):复制构造函数vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中2.增加函数void push_back(const T& x):向量尾部增加一个元素X。
2024-03-19 21:38:37
27
转载 C++的STL（一）
STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。
2024-03-19 21:36:39
30
原创 合并 K 个升序链表
请你将所有链表合并到一个升序链表中，返回合并后的链表。给你一个链表数组，每个链表都已经按升序排列。将它们合并到一个有序链表中得到。
2024-02-15 22:50:12
382
原创 实现 Trie (前缀树)
初始化为 O(1)，其余操作为O(|S|)，其中|S|是每次插入或查询的字符串的长度。重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。若搜索到了前缀的末尾，就说明字典树中存在该前缀。数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。对于本题而言，数组长度为 26，即小写英文字母的数量。重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。沿着指针移动到子节点，继续处理下一个字符。沿着指针移动到子节点，继续搜索下一个字符。，其中|T|为所有插入字符串的长度之和，
2024-02-02 16:10:08
952
原创 二叉树的锯齿形层序遍历
空间复杂度：O(N)。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。时间复杂度：O(N)，其中N为二叉树的节点数。每个节点会且仅会被遍历一次。
2024-01-27 13:38:59
495
原创 跳跃游戏 II
在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
2024-01-04 11:16:44
431
原创 买卖股票的最佳时机 IV
由于在所有的 nnn 天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组。这种在同一天之内进行一笔交易的情况，收益为零，它并不会带来额外的收益，因此对最终的答案并不会产生影响，状态转移方程在本质上仍然是正确的。与其余的股票问题类似，我们使用一系列变量存储「买入」的状态，再用一系列变量存储「卖出」的状态，通过动态规划的方法即可解决本题。中的价格而言，进行恰好j笔交易，并且当前手上持有一支股票，这种情况下的最大利润；我们可以考虑将所有的。
2023-12-26 09:09:09
1020
原创 买卖股票的最佳时机
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。时，考虑的是在第i天卖出股票的情况，这样在同一天买入并且卖出收益为零，不会对答案产生影响。
2023-12-25 11:55:20
414
原创 零钱兑换、、
时间复杂度：O(Sn)，其中S是金额，n是面额数。我们一共需要计算O(S)个状态，S为题目所给的总金额。对于每个状态，每次需要枚举n个面额来转移状态，所以一共需要O(Sn)的时间复杂度。则，当 i==0时无法用硬币组成，为 0。代表的是第 jjj 枚硬币的面值，即我们枚举最后一枚硬币面额是。则 F(i)F(i)F(i) 对应的转移方程应为。我们可以看到问题的答案是通过子问题的最优解得到的。为前面能转移过来的状态的最小值加上枚举的硬币数量。你可以认为每种硬币的数量是无限的。所需最少的硬币数量，假设在计算。
2023-12-24 09:31:57
401
原创 单词拆分\\
返回 true 因为 "applepenapple"可以由"apple" "pen" "apple" 拼接成。对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点。的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
2023-12-22 13:28:10
408
原创 打家劫舍\\\
如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃第k间房屋，那么就不能偷窃第k−1间房屋，偷窃总金额为前k−2 间房屋的最高总金额与第。，一夜之内能够偷窃到的最高金额。
2023-12-21 12:24:42
369
原创 回文数、、
对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
2023-12-20 12:59:26
371
原创 Pow(x, n)
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘。举个例子，如果我们要计算。这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个。这是由于递归的函数调用会使用栈空间。由于每次递归都会使得指数减少一半，因此递归的层数为。这些步骤中，我们直接把上一次的结果进行平方，而在。开始，每次直接把上一次的结果进行平方，计算。，算法可以在很快的时间内得到结果。再举一个例子，如果我们要计算。时，我们可以先递归地计算出。根据递归计算的结果，如果。
2023-12-20 12:44:30
392
原创 直线上最多的点数
假设我们当前枚举到点 iii，如果直线同时经过另外两个不同的点 jjj 和 kkk，那么可以发现点 iii 和点 jjj 所连直线的斜率恰等于点 iii 和点 kkk 所连直线的斜率。于是我们可以统计其他所有点与点 iii 所连直线的斜率，出现次数最多的斜率即为经过点数最多的直线的斜率，其经过的点数为该斜率出现的次数加一（点 iii 自身也要被统计）。的情况下，我们总可以用一条直线将所有点串联，此时我们直接返回点的总数量即可；我们可以考虑枚举所有的点，假设直线经过该点时，该直线所能经过的最多的点数。
2023-12-19 12:58:14
414
原创 只出现一次的数字
使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
2023-12-18 13:17:04
437
原创 只出现一次的数字 II
我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。请你找出并返回那个只出现了一次的元素。外，其余每个元素都恰出现。个元素，即需要的空间为。
2023-12-18 13:05:26
386
原创 二进制求和
直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。，除去答案所占用的空间，这里使用了常数个临时变量。，以二进制字符串的形式返回它们的和。
2023-12-17 13:21:00
365
原创 数字范围按位与
最直观的解决方案就是迭代范围内的每个数字，依次执行按位与运算，得到最终的结果，但此方法在 [m,n][m,n][m,n] 范围较大的测试用例中会因超出时间限制而无法通过，因此我们需要另寻他路。我们的想法是将两个数字不断向右移动，直到数字相等，即数字被缩减为它们的公共前缀。在上图的例子中，我们可以发现，对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。鉴于上述问题的陈述，我们的目的是求出两个给定数字的二进制字符串的公共前缀，这里给出的第一个方法是采用位移操作。
2023-12-17 13:09:38
386
原创 数据流的中位数
/ 返回 1.5 ((1 + 2) / 2)当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时，新的中位数将小于等于原来的中位数，因此我们可能需要将。新的中位数将大于等于原来的中位数，因此我们可能需要将。小于等于中位数，我们需要将该数添加到。大于中位数，我们需要将该数添加到。特别地，当累计添加的数的数量为。为累计添加的数的数量。
2023-12-15 13:39:44
456
原创 IPO、、
我们利用大根堆的特性，我们将所有能够投资的项目的利润全部压入到堆中，每次从堆中取出最大值，然后更新手中持有的资本，同时将待选的项目利润进入堆，不断重复上述操作。我们首先将项目按照所需资本的从小到大进行排序，每次进行选择时，假设当前手中持有的资本为。由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。在完成后，你将获得 1 的利润，你的总资本将变为 1。，直到手中的持有的资本无法启动当前的项目为止。
2023-12-14 13:20:49
405
原创 搜索插入位置
的时间内找到是否存在目标值。但这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，那我们还能用二分法么？给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。假设题意是叫你在排序数组中寻找是否存在一个目标值，那么训练有素的读者肯定立马就能想到利用二分法在。，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于。大于数组中的所有数，此时需要插入到数组长度的位置。下文给出的代码是笔者习惯的二分写法，
2023-12-13 13:11:22
371
原创 寻找峰值、
中最大值两侧的元素一定严格小于最大值本身。因此，最大值所在的位置就是一个可行的峰值位置。，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回。或者返回索引 5， 其峰值元素为 6。3 是峰值元素，你的函数应该返回其索引 2。你的函数可以返回索引 1，其峰值元素为 2；峰值元素是指其值严格大于左右相邻值的元素。进行一次遍历，找到最大值对应的位置即可。你必须实现时间复杂度为。的算法来解决此问题。
2023-12-13 12:53:59
349
原创 寻找两个正序数组的中位数
插入数大小如果不在这四个数的范围内，根据大小（小于mid-2或大于mid+1），默认直接插到头部或尾部，在这四个数的范围内则按序插入，4毕竟是常数，按序插入也不会增加复杂度，该操作(参见brief_insert_ascend函数)消耗为O(2x6)=O(1)很巧妙的是，这题只求中位数。对于奇数数组（个数为奇数的数组），保留中间的那个数，中间往左（或往右，根据另一个数组的中位数大小而定）的所有数都可以剪掉，因为不影响中位数。根据裁剪性质得出，数组1能够裁剪的量为1，数组2能够裁剪的量为2，取最小裁剪量为1。
2023-12-12 18:05:36
812
原创 环形子数组的最大和
至此，我们可以使用以上方法求解出环形数组的最大子数组和。特别需要注意的是，本题要求子数组不能为空，我们需要在代码中做出相应的调整。第一种情况的求解方法与求解普通数组的最大子数组和方法完全相同，读者可以参考53号题目的题解：最大子序和。求解普通数组的最大子数组和是求解环形数组的最大子数组和问题的子集。从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3。的最大前缀和，将它们相加更新答案。数组和枚举后缀的时间复杂度为。最多只能包含固定缓冲区。构成最大子数组和的子数组为。构成最大子数组和的子数组为。
2023-12-11 12:22:17
413
原创 最大子数组和
我们只需要遍历一遍数组即可求得答案。数组中的最大值即可。的值是多少，从而让空间复杂度降低到。我们只需要常数空间存放若干变量。，这有点类似「滚动数组」的思想。相关，于是我们可以只用一个变量。因此我们只需要求出每个位置的。的值，用一个循环求出所有。对应的那一段，这取决于。不难给出一个时间复杂度。单独成为一段还是加入。
2023-12-10 12:37:32
347
原创 建立四叉树
如果是，那么这一部分对应的是一个叶节点，我们构造出对应的叶节点并结束递归；如果不是，那么这一部分对应的是一个非叶节点，我们需要将其分成四个部分：行的分界线为。，根据这两条分界线递归地调用 dfs\text{dfs}dfs 函数得到四个部分对应的树，再将它们对应地挂在非叶节点的四个子节点上。，那么说明这一部分包含的元素大部分都是相同的，也就是说，有很大概率在深入递归时遇到元素完全相同的一部分，从而提前结束递归。的数组需要的时间复杂度，那么「判定这一部分是否均为。，即为递归需要使用的栈空间。
2023-12-09 13:00:45
938
原创 将有序数组转换为二叉搜索树
如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。确定平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树，因此可以通过递归的方式创建平衡二叉搜索树。二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。时，平衡二叉搜索树为空。
2023-12-09 12:46:38
386
原创 单词搜索（回溯，清晰图解）
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res。剪枝： 在搜索中，遇到“这条路不可能和目标字符串匹配成功”的情况，例如当前矩阵元素和目标字符不匹配、或此元素已被访问，则应立即返回，从而避免不必要的搜索分支。方案数计算： 设字符串长度为 KKK ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下3种选择，因此方案数的复杂度为。分别为矩阵行列大小，
2023-12-07 12:26:06
912
原创 全排列、、
假设这个位置我们要填10这个数，为了维护数组，我们将2和10交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填。举个简单的例子，假设我们有[2, 5, 8, 9, 10]这5个数要填入，已经填到第3个位置，已经填了[8, 9]两个数，那么这个数组目前为。划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数。为待填的数，回溯的时候交换回来即能完成撤销操作。
2023-12-05 13:14:35
831
原创 电话号码的字母组合
回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。是输入数字的总个数。首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
2023-12-04 13:07:46
371
原创 添加与搜索单词 - 数据结构设计
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配。// 返回 False。// 返回 True。// 返回 True。// 返回 True。
2023-12-02 15:47:53
463
原创 单词搜索II
并且该解法优化的一点在于，当节点为叶子结点时，先检查是否为单词终止字符(因为该叶子结点可能是不断删除叶子以后才变成的叶子结点，其保留的单词可能早就被取走了)，再删除叶子结点。该题性能高的最关键点在于剪枝，在搜索一个单词时，会先遍历一遍该单词中，若单词中出现map中没有的字符，则说明字符矩阵中没有该字符。只要是将字符矩阵生成所有可能单词的前缀树，就会有较多无用分支，就会拉低性能，所以这里就不实现了。不同的是，解3的匹配单词，解4是匹配前缀树的子节点，当节点为单词终止字符时，则将单词存入结果数组中。
2023-12-01 15:13:47
814
原创 蛇梯棋、、
即假设编号为 next 的单元格所在位置为 (r,c)，那么玩家将不会转移到 next 编号的方格，而是转移到 board[r][c] 编号的方格。由于是交替的，我们把行倒着编码（最后一行当成第 0 行，倒数第二行为 1 行，即 r 行的编号变成 n-1-r'），那么偶数行是从左到右，c' = 0+c【从首列0往右数c个位置】；其次，行的排列是倒序的【或者说翻转了】，即原本的 r=0 跑到了 r=n-1，相当于从 n-1 行倒着往回数，因此计算出来的 r' = n - 1 - r；
2023-11-30 11:45:26
957
原创 最小基因变化
进行预处理，找到基因库中的每个基因的合法变换，而不需要像方法一中每次都需要去计算基因的变化序列，我们将每个基因的合法变化关系存储在邻接表。记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库。一次基因变化就意味着这个基因序列中的一个字符发生了变化。基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是。进行预处理，只在合法的基因变化进行搜索即可。默认是有效的，但是它并不一定会出现在基因库中。基因库的长度较小，因此可以直接在对。中，每次基因变化搜索只在。
2023-11-29 14:25:18
395
原创 单词接龙、
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个，所以判断点与点之间的关系，要自己判断是不是差一个字符，如果差一个字符，那就是有链接。然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。以示例1为例，从这个图中可以看出 hit 到 cog的路线，不止一条，有三条，两条是最短的长度为5，一条长度为6。本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！本题只需要求出最短长度就可以了，不用找出路径。
2023-11-28 11:38:25
396
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人