← 全部文章

分类

技术札记

85 篇文章

【CCF-CSP】202203-2. 出行计划

题目内容 【CCF-CSP】202203-2. 出行计划 思路分析 方法一：普通法（仅能获得70分） 思路 先将出行计划（进入场所时刻、需要C时刻内的核酸）依次存入数组中，然后根据所查询的做核酸的时刻，依次计算出各个出行计划是否在time_min和time_max的区间内（即核酸有效期），其中： time_min...

6 分钟
技术札记
#差分 #CCF-CSP

[网络领域顶会追踪系列#12][NSDI'22]背压流量控制

Backpressure Flow Control 背景 随着时延敏感型流量、更大（fatter）的链路和非常突发的流的增长，数据中心网络中高效的拥塞控制变得越来越具有挑战性。 挑战 DCTCP和DCQCN等广泛部署的算法，在很多可信场景中远远没有达到最优值，特别是对于尾部延迟来说。许多操作员通过让他们的网络运行...

4 分钟
技术札记
#网络领域顶会追踪 #计算机网络 #论文阅读 #NSDI

python subprocess模块学习笔记

subprocess介绍 参考：Python官方文档：subprocess — Subprocess management subprocess模块用于执行命令行命令。官方推荐的使用方法是使用模块中的run()方法，更高级的方法可以使用下层的Popen()方法。 subprocess.run() 运行参数描述的命...

3 分钟
技术札记
#python #编程语言

Vxlan学习笔记---概念与实践

先导---Overlay网络 Overlay网络是一种灵活的叠加虚拟网络。 为什么需要Overlay网络？ 移动性 - 跟踪边缘设备连接的主机 伸缩性 - 减少核心网络状态，网络边缘分布式和分区处理 多租户 - 共享网络资源 灵活性/可编程 - 减少维护节点数量 使用Overlay网络可按需在底层承载网络上快速部...

7 分钟
技术札记
#vxlan #overlay #计算机网络

【leetcode】33. 搜索旋转排序数组

题目内容 33. 搜索旋转排序数组 思路分析 本题是一道二分查找的进阶题目。 参考资料：官方题解 方法一：二分查找 做这道题目需要意识到一个性质：在搜索范围是旋转排序数组的情况下，二分的结果是左右两半有一半是有序的，有一半是乱序的。 而判断哪一部分乱序的方法为判断nums[0]和nums[mid]的大小： 若nu...

6 分钟
技术札记
#二分查找 #数组 #算法

【leetcode】35. 搜索插入位置

题目内容 搜索插入位置 思路分析 本题其实就是C++的lower_bound函数的弱化版。 方法一：C++ STL 直接调lower_bound函数。 方法二：自己实现 直接按照模板来写，不同之处是如果没找到target的话需要返回插入的位置（left指针）。 代码 #include <vector>...

2 分钟
技术札记
#二分查找 #数组 #算法

【leetcode】278. 第一个错误的版本

题目内容 278. 第一个错误的版本 思路分析 本题是一道二分查找题目，掌握二分查找的写法后写起来比较简单。关于二分查找的写法可以见我写了首诗，让你闭着眼睛也能写对二分搜索，可以说讲的非常清楚。 方法一：找左侧边界的二分查找 基本上按模板来就行，和模板不同的是本题的查找只有是和不是两种状态，而非平时的大于/小于/...

3 分钟
技术札记
#二分查找 #数组 #算法

快速选择算法

资料 基于快排的快速选择算法 快速排序亲兄弟：快速选择算法 快速选择-维基百科，自由的百科全书 解读 快速选择其实是快排的变种，快排的思想就是以pivot为枢轴，交换两边的数字，交换完毕的最终效果是pivot左边都小于等于pivot，右边都大于pivot。设pivot的下标为p，则说明找到了数组中第p大元素。 若...

3 分钟
技术札记
#快速选择 #算法

【leetcode】215. 数组中的第K个最大元素

题目内容 215. 数组中的第K个最大元素 思路分析 【方法一】参考资料--快速排序亲兄弟：快速选择算法 【方法一】力扣官方题解 方法一：快速选择 本题是快速选择的经典使用场景，就是在学习快速选择的过程中来顺便学习此题。 关于快速选择的学习笔记详见：快速选择算法 此外，快速选择也可以通过C++的nth_eleme...

5 分钟
技术札记
#快速选择 #二叉堆 #数组 #算法

【leetcode】376. 摆动序列

题目内容 376. 摆动序列 思路分析 方法一：贪心 参考资料1 参考资料2 参考资料3 贪心策略：只选极值点，而忽略中间的所有点。 可以贪的原因：只选极值点，可以增大后续元素被选中为摆动序列的概率。详见参考资料2和3中的图。 实际实现时，只需记录极值点的个数。可以按照参考资料1，默认最右端有一个极值点，最左端（...

3 分钟
技术札记
#贪心 #动态规划 #数组 #算法

【leetcode】283. 移动零

题目内容 283. 移动零 思路分析 参考资料1 参考资料2 本题和75. 颜色分类思想差不多。 方法一：双指针两次遍历 可以设置ptr指针，用来指示按原本的顺序排列的非0数。 第一次遍历：遇到非0数则对nums[ptr]赋nums[i]，同时将ptr+1。 第二次遍历：第一次遍历后，ptr以前的区域为按原本顺序...

4 分钟
技术札记
#双指针 #数组 #算法

【leetcode】75. 颜色分类

题目内容 75. 颜色分类 思路分析 参考资料 方法一：单指针 可以采用一个单指针ptr，来表征“头部区域”的范围。遍历两遍数组： 第一遍：遇到0则将0放进“头部区域”，即交换nums[i]和nums[ptr]，并将ptr+1； 第二遍：遇到1则将1放进“头部区域”，即交换nums[i]和nums[ptr]，并将...

4 分钟
技术札记
#双指针 #排序 #数组 #算法

【leetcode】88. 合并两个有序数组

题目内容 88. 合并两个有序数组 思路分析 参考资料 方法一：插入排序 看到本题，自己想的解法是进行插入排序。 与正常的插入排序一样，都是二分查找+插入的思路。只不过本题有一点点不同：数组一中用0预留出了数组二的位置，因此 数组一整体相当于不是有序的，如[1, 2, 3, 0, 0, 0]。不可以直接在begi...

7 分钟
技术札记
#插入排序 #快速排序 #双指针 #数组 #算法

【leetcode】228. 汇总区间

题目内容 228. 汇总区间 思路分析 本题的算法感觉就是个自然而然的算法，也没有什么技巧。但是自己写的代码好蠢，还分各种情况讨论。答案的代码又精简，又把所有的情况考虑进去了。向答案学习。 方法一：一次遍历 参考资料 本题目在以下两个情况下会产生新区间： 遍历到最后一个数，必须得输出一个新区间 数字不连续，即nu...

3 分钟
技术札记
#数组 #算法

【leetcode】152. 乘积最大子数组

题目内容 152. 乘积最大子数组 思路分析 方法一：动态规划 本题与53. 最大子序和类似，但是本题是乘法运算，因此nums[i]的最大乘积不一定依赖于前一个数字（如[-1, 2, -3, 4]）。因此需要利用以下关系来进行动态规划： 当前最大值 = max(上一个数的最大值*当前数, 上一个数的最小值*当前数...

2 分钟
技术札记
#动态规划 #数组 #算法

【leetcode】238. 除自身以外数组的乘积

题目内容 238. 除自身以外数组的乘积 思路分析 按理说比较容易想到的一个O(n)的解是把所有数乘起来，然后除以nums[i]。然而该方法遇到0会失效，且题目不允许用除法。最重要的是我连这种方法都想不到... 方法一：左右乘积列表 可以维护两个乘积列表left_multi和right_multi，该列表的第i个...

4 分钟
技术札记
#左右乘积列表 #数组 #算法

【leetcode】209. 长度最小的子数组

题目内容 209. 长度最小的子数组 思路分析 参考资料 方法一：前缀和+二分查找 由于题目所给的数组元素都是正整数，且要找到满足≥target的子序列。 因此，设题目所给数组的大小为n，可以创建一个大小为n+1的数组sums，其第i个元素为前i个数字的和，则问题转换为： ​ 对于指定的下标i，求满足sums[j...

6 分钟
技术札记
#前缀和 #二分查找 #滑动窗口 #双指针 #数组 #算法

【leetcode】53. 最大子序和

题目内容 53. 最大子序和 思路分析 本题比较简单，可使用动态规划完成 方法一：动态规划 最大子序列和有以下特征： nums[i]的最大子序列和等于max(nums[i-1]的最大子序列和加nums[i], nums[i]) 因此nums[i]可利用nums[i-1]的计算结果，即可进行动态规划。 使用动态规划...

3 分钟
技术札记
#动态规划 #数组 #算法

【leetcode】295. 数据流的中位数

题目内容 295. 数据流的中位数 思路分析 参考资料 方法一：两个堆 此方法十分巧妙，这里直接上个来自这里的图： 其实就是利用中位数是最中间的数字的特点，将数字按大小分为个数相等的两部分（或数字较小的部分元素个数可以比数字较大的部分多1）： bigger_nums：较大的一部分数字，它是一个堆顶为最小值的堆； ...

8 分钟
技术札记
#优先队列 #二叉堆 #插入排序 #二分搜索树 #multiset #数组 #算法

【leetcode】239. 滑动窗口最大值

题目内容 239. 滑动窗口最大值 思路分析 参考资料 方法一：优先队列 似乎这种最大值问题比较容易想到优先队列这种数据类型，优先队列可以维护一个最大或最小值，一般是由二叉堆实现的。关于二叉堆我专门写了一篇学习笔记。 优先队列可以自动帮我们得出前i个数的最大值，然而这个题目是个窗口问题，因此每次判断队列的最大值的...

6 分钟
技术札记
#优先队列 #二叉堆 #单调队列 #数组 #算法

二叉堆学习

参考资料 漫画：什么是二叉堆？（修正版） 二叉堆(binary heap)的insert和build 时间复杂度分析 二叉堆-wiki 优先队列-wiki 漫画：什么是优先队列？ 数据结构 - 优先队列与二叉堆 二叉堆及堆排序 堆排序-wiki 堆排序的时间复杂度 定义 二叉堆是一种满二叉树，分为最大堆和最小堆。...

6 分钟
技术札记
#二叉堆 #优先队列 #数据结构

【leetcode】57. 插入区间

题目内容 插入区间 思路分析 本题需要首先搞清楚题目的意思，一旦插入的区间与原本的区间有交集，就需要合并。 解题的核心在于考虑清楚插入区间与所遍历的区间的关系，以及考虑清楚所遇到的各种情况。 方法一：模拟 参考资料 设i_l、i_r为当前正在遍历区间的左右端点值，n_l、n_r为插入区间的左右端点值。则可以确定的...

5 分钟
技术札记
#模拟 #数组 #算法

【leetcode】287. 寻找重复数

题目内容 287. 寻找重复数 思路分析 本题由于二分查找的条件劝退，一连拖了好几天，拖的有点恶心了，就只好留了些坑把这个题先跳过了。 本题主要是要求使用O(n)的时间复杂度和O(1)的空间复杂度，这个要求卡死了很多解法。 除了这里用的二分法以外，常见的另一种方法还有快慢指针法，见方法二-参考资料一。 方法一：基...

5 分钟
技术札记
#基数排序 #二分法 #快慢指针 #Floyd 判圈算法 #数组 #算法

【leetcode】164. 最大间距

题目内容 164. 最大间距 思路分析 本题仍然是一道排序题，题目的核心是对数字进行排序，排好序后就很简单了。而题目要求使用线性时空间复杂度，因此不能使用基于比较的排序方法。 解法参考资料 方法一：基数排序 基数排序资料 基数排序是一种非比较的排序方式，可以实现O(n)的时空复杂度排序。目前为止见过的另一种基于非...

6 分钟
技术札记
#基数排序 #桶算法 #数组 #算法

【leetcode】42. 接雨水

题目内容 42. 接雨水 思路分析 本题的总体思路为从第二个柱子起，判断每个柱子左右两边柱子的最大高度，然后max(0, min(左右两边的最大高度)-当前柱子高度)即为当前柱子可以装的水量。 方法一：动态规划 参考资料（其中的解法3） 利用当前柱子及其左边所有柱子的最大高度max_left_height=max...

6 分钟
技术札记
#动态规划 #双指针 #数组 #算法

【leetcode】128. 最长连续序列

题目内容 128. 最长连续序列 思路分析 本题一上来的考虑是排序然后数一下连续的个数，但做出来以后发现会超时。正确的思路是使用哈希 方法一：排序（超时） 使用快排对数组进行排序，然后数连续的个数。 方法二：哈希 参考资料 内层循环： 将每个数num哈希存储（这里使用C++的unorderd_set，查找的时间复...

6 分钟
技术札记
#快速排序 #哈希 #数组 #算法

【leetcode】334. 递增的三元子序列

题目内容 334. 递增的三元子序列 思路分析 本题比较简单（没怎么思考，直接看的答案） 方法一：脑筋急转弯 设置两个变量small=INT_MAX和mid=INT_MAX，依次遍历数组，若小于等于small则更新small，若小于等于mid则更新mid。 注意一定要加上等于号的限制，等于号能保证遇到相等情况时能...

2 分钟
技术札记
#脑筋急转弯 #数组 #算法

【leetcode】289. 生命游戏

题目内容 289. 生命游戏 思路分析 感觉本题最大的难点在于游戏规则，代码里很大一部分都是为了去描述游戏规则。其次如何把空间优化到O(1)也比较难想，本题的状态法就比较巧妙。 方法一：复制数组法 为避免新状态造成老状态的误判，直接将结果存至新的数组中。这样做一个很显然的缺点是很费空间，但是是可以通过的。 方法二...

6 分钟
技术札记
#状态法 #数组 #算法

【C++Primer笔记】1. 第一章 开始

前言 本笔记的目的为记录下读《C++ Primer》时一些需要注意和不懂的点，便于巩固和温习，不然可能看完了就忘了。 本节知识点 main函数 通常程序的返回值为0代表成功，返回值为1代表失败。 main函数的返回值必须为int。 输入输出 输入输出有关的： 库：iostream； 类型：istream和ostr...

6 分钟
技术札记
#输入输出 #命名空间 #C++

【leetcode】11. 盛最多水的容器

题目内容 11. 盛最多水的容器 思路分析 看到本题目时，表示没有什么头绪，就只好暴力法硬刚，结果超时了... 看了各个题解，几乎全用的双指针法，其中感觉“缩小搜索空间”的这个说法深得我意，特别是那个表格图，感觉讲得非常非常清晰。 首先要明确的是，设下标为i和j，则此时容器的容积为(j - i) * min(he...

6 分钟
技术札记
#双指针 #数组 #算法

【leetcode】309. 最佳买卖股票时机含冷冻期

题目内容 309. 最佳买卖股票时机含冷冻期 思路分析 本题也是股票系列的一道题目。题目中提到： 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 看到状态这个词就很明显的想到动态规划了（外加股票系列本来就动态规划用的多），虽然最后用的状态不是这个... 本题是自己定了状态仔细推导以后发现不对劲，又...

8 分钟
技术札记
#动态规划 #数组 #算法

【leetcode】188. 买卖股票的最佳时机4

题目内容 188.买卖股票的最佳时机4 思路分析 本题是123. 买卖股票的最佳时机3 的更一般化，可直接由股票问题3的题解改编而来。 方法：动态规划 和股票问题3类似，使用一个大小为2k的数组cash来存储每一天的状态，令j为0,2,4,6...，则下标为j的元素代表某天买过j/2 + 1次，卖过j/2次；下标...

5 分钟
技术札记
#动态规划 #数组 #算法

【leetcode】123. 买卖股票的最佳时机3

题目内容 123. 买卖股票的最佳时机3 思路分析 本题使用了动态规划的方法，状态比较多，比较难想到。 方法一：动态规划 参考链接1，参考链接2 每天交易完成后有5种状态： -1 不曾交易过 0 买过一次 1 买过一次，卖过一次 2 买过两次，卖过一次 3 买过两次，卖过两次 因为状态-1不会对现金产生影响，因此...

9 分钟
技术札记
#动态规划 #数组 #算法

【leetcode】122. 买卖股票的最佳时机2

题目内容 122. 买卖股票的最佳时机2 思路分析 本题是股票系列的第二题，似乎一共有五六道题，做完以后就可以去炒股发家致富了🤣。 本题共有三种思路，拟人（方法一）、动态规划（方法二和三）和贪心（方法四）。其中方法一感觉也可以叫贪心。 感觉拟人和贪心比较容易想到，而动态规划，特别是二维动态规划，思路从何而来？感觉...

10 分钟
技术札记
#动态规划 #拟人 #贪心 #数组 #算法

【leetcode】121. 买卖股票的最佳时机

题目内容 121. 买卖股票的最佳时机 思路分析 本题看起来很简单，但是自己做就是怎么都做不出来...自闭ing😶 本题共有两种思路，动态规划（方法一和方法二）和单调栈（方法三）。 方法一：动态规划 参考链接 选用动态规划的原因： 包含了重叠的子问题，买入和卖出股票的最佳时机是由之前的状态决定的，而之前的状态又是...

10 分钟
技术札记
#动态规划 #拟人 #单调栈 #数组 #算法

【leetcode】45. 跳跃游戏 II

题目内容 45. 跳跃游戏 II 思路分析 本题难度为困难，是55. 跳跃游戏的plus版。55题是让判断是否能到达，使用了贪心算法（尽量跳的远）。 第一眼看到这个题时，算法课学艺不精的我，打算用动态规划来做，感觉应该有可以重复利用的子问题，结果栈溢出，不断地迭代而不退出，翻车了.... 本题的正确解法应该为贪心...

5 分钟
技术札记
#贪心 #数组 #算法

【leetcode】55. 跳跃游戏

题目内容 55. 跳跃游戏 思路分析 一开始看到题目的时候，没什么思路，感觉可能要用动态规划，就直接去看了答案。看了答案感觉还是挺简单的，虽然说是贪心，但是没感觉贪心在哪了，只感觉是一种“聪明人”的做法。 翻评论的时候看到一句话 属于贪心，每一步都贪婪的计算最远到达位置。 那就勉强算贪心吧~ 具体思路如下： 维护...

3 分钟
技术札记
#贪心 #数组 #算法

【leetcode】217. 存在重复元素

题目内容 217. 存在重复元素 思路分析 本题是一道调节心态题（做完我又觉得我行了😂） 主要思路为使用一个set来记录每个数字出现的次数，当发现有数字的出现次数大于1时，则证明存在重复元素，返回true；遍历完数组还未返回，则证明不存在重复元素，返回false。 另外，看题目的评论区有人说 来了，来了。面试经典...

3 分钟
技术札记
#哈希表 #数组 #算法

influx db max-series-per-database错误

环境 influx版本：1.8 使用docker容器化的influx 问题描述 如图，默认的最大series数是100W，如果再对一个新的series进行写入，则会出现错误。 相关资料 官方错误解释 Max-series-per-database limit exceeded 1000000, error que...

2 分钟
技术札记
#influxdb #数据库