镜子的知识栈 Tsuki's stack

最短路 单源最短路 所有边权都是正数 朴素 Dijkstra算法 O(n^2) 遍历所有点 Dijkstra堆优化算法 O(mlogn) 遍历所有最短点并更新相连的所有边 存在负权边 Bellman-Ford O(nm) 遍历所有边, 更新点. 可求限定边的最短路问题 SPFA 一般O(m) 最坏O(mn) 多源汇最短路 Floyd算法 O(n^3) 源点: 起点 汇点: 重点 Dijkstra求最短路12345678910111213141516171819202122232425262728293031323334int nint g[N][N]; //邻接矩阵存储边int dist[N]; //点n到源点的距离bool st[N]; //是否遍历过int dijkstra(){ // 初始化所有点到源点的距离为无穷大,且第一个点到源点的距离为0(自己本身就是源点) memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 所有的点都遍历一次 ...

引入很多时候我们会在使用数组的时候找中间位置 比如常见的算法 二分查找 归并排序 快速排序(某些实现) 我们一拍脑袋写出来的基本都是 (l + r) / 2 其中有几个问题需要我们时刻注意到 区间我们在写一些算法的时候, 要注意自己写的区间是闭区间还是一个开区间 列如我们定义一个数组a[10] 包含10个int类型的元素数组下标 0-9 在STL中, 很多库函数实现范围的确定都是一个开区间 例如 ve.begin(),ve.end() 假如我们要对一个vector排序的话一般会这样写 如果用开区间去表示一个数组,那么l = 0, r = 10 反之闭区间为 l = 0, r = 9 首先确定区间才能确定我们 (l + r) / 2 表达式求出来的结果是哪一个下标 偶数个元素的数组需要注意这里直接得出结论 闭区间 (l + r) / 2 的结果为中间偏左边的元素 开区间 (l + r) / 2 的结果为中间偏右边的元素 所以如果要相应的在闭区间和开区间求另外一边的元素的话, 要相应的 +1或者 -1

123std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); 取消stdio的绑定

快速排序我们先来模拟一下快速排序的流程 先寻找一个基值 将大于这个值的数放在它后面,小于的放在前面 递归调用前后两个已经分好的区间重新快排 GIF如下 实现过程 (y总方法)1234567891011121314151617181920212223242526272829303132333435// 闭区间使用右指针作为分界点void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1; int x = q[l + r >> 1]; // 有可能取到左边界 while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); // 以j为分界点递归 ...

前缀和前缀和的含义每个人对前缀和的含义理解不一样 已知一个前缀和数组sum 下标数字表示的含义为原数组前n个数的和。 例如： 1234source[10] = {1,2,3,4,5,6,7,8,9,10};sum[0] = 0 //含义为原数组前0个数的和，所以为0 sum[1] = 1 //含义为原数组前1个数的和，所以为1 sum[2] = 3 //含义为原数组前2个数的和，所以为3 前缀和下标和原数组下标不是一一对应 主要应用：用前缀和求区间我们常用前缀和求区间的公式为sum[r] - sum[l - 1] 在区间[l,r]上表示从l到r之间的和。 sum[r]表示前r个数的和，sum[l-1]表示前l-1个数的和，我们减去之后就是区间[l,r] 前缀和构建构建前缀和需要特殊处理sum[0]其次sum[i] = sum[i-1]+source[i-1]每一项都是前一项加上一个新的数。 1234sum[0] = 0;for(int i = 1;i <= n;i++){ sum[i] = sum[i - 1] + source[i - 1 ...

buffer操作显示buffer列表 :files :buffers :ls buffer切换操作 指令 含义 :bp[revious] 上一个缓冲区 :bn[ext] 下一个缓冲区 :bf[irst] 到第一个缓冲区 :bl[ast] 到最后一个缓冲区 :buffer Nubmer/File_name 指定缓冲区 :ball 编辑所有缓冲区 :badd add.txt 增加一个缓冲区 :bdelete add.txt 删除一个缓冲区 :bufdo %s/pattern/replace/ge | update 多buffer查找替换 vim窗口操作基本操作 指令 含义 :{number}split {file} 把屏幕分解成两个窗口并把光标置于上面的窗口中 :new 打开窗口编辑一个新文件 :close 关 闭 窗 口 :only 关 闭 所 有 其 它 窗 口 CTRL-W + 扩大窗口 CTRL-W - 缩小窗口 {height}CTRL-W _ 设置为指定的 ...

My coding record in vacationDecember#10 76. 最小覆盖子串 567. 字符串的排列 438. 找到字符串中所有字母异位词 滑动窗口+哈希表 #11 187. 重复的DNA序列 34. 在排序数组中查找元素的第一个和最后一个位置 704. 二分查找 滑动哈希窗口 代码过于粗心，debug浪费太多时间。写代码过程中不够严谨。 #12 528. 按权重随机选择 VScode配置task和launch (没有解决数值相同情况，不会用优先级队列) 前缀和数组下标[0]本质是占位符，搜索不应该包含0 前缀和数组偏移位 #13 870. 优势洗牌 316. 去除重复字母 67. 二进制求和 面试题67. 把字符串转换成整数（解决不了整型溢出问题 less和greater仿函数在map中的使用 去重字母使用哈希表要注意字母重复出现情况 #14 1629. 按键持续时间最长的键 2273. 移除字母异位词后的结果数组 计算哈希值时，如何避免哈希冲突 #15 1491. 去掉最低工资和最高工资后的工资平均值 1974. 使用 ...

VS code C++ 程序调试重定向linux下的重定向符号输入重定向到文件 1program < file 输出重定向到文件 1program > file VSC设置launch.json无论是直接在program直接写重定向符还是参数里写，都无效 123{ "args": ["<", "input.txt"]} 正确的打开方式1234567{ "setupCommands": [ { "text": "settings set target.input-path ${workspaceFolder}/input" } ]} 以上的命令其实就是在lldb启动时执行的lldb命令，将input文件重定向到程序中。

VScode配置task和launch支持C++11刚开始使用VScode一般都是使用默认的task和lunch配置去执行代码或者debug，一旦修改了相关目录或者改动一些参数，就会不停的提醒XXX文件不存在或者一些奇怪错误。今天就专门花时间研究了一下task和lunch怎么用 因为task和launch都是使用json编写，并且是用来启动编译器，所以需要一些 预备知识 编译器相关参数 json语法 Task的配置task就是你当前要执行的任务，如果不手动配置，vs会自动配置当前环境的编译任务 初次创建文件或者目录后，按下 F1键盘 会自动生成launch和task文件 默认task如下 12345678910111213141516171819202122232425{ "tasks": [ { "type": "cppbuild", "label": "C/C++: g++ build active fil ...

滑动哈希窗口滑动窗口是一个特殊的双指针技巧，分别有左指针和右指针，在一个串上形成一个窗口。右指针向前移动窗口添加一个字符，左指针向前移动窗口删除一个字符。以此来判断窗口内的内容和模式串的内容是否相等。 我们建立一个哈希表，用来存储窗口内的内容 常见的代码结构如下 12345678while(主串结束条件){// r++// 哈希表内添加字符while(窗口满足条件){ // l++ // 哈希表减去一个字符 }}