Category Archives: algorithms

Python正则表达

正则表达式的常用操作符 操作符 说明 示例 . 表示任何单个字符 [] 字符集, 对单个字符给出取值范围 [abc]表示a,b,c, [a-z]表示a到z单个字符 [^ ] 非字符集, 对单个字符给出排除范围 [^abc]表示非a或b或c的单个字符 * 前一个字符0次或无限次扩展 abc*表示ab, abc, abcc等 + 前一个字符1次或无限次扩展 abc+表示abc, abcc, abccc等 ? 前一个字符0次或1次扩展 abc?表示ab, abc | 左右表达式任意一个 abc|def表示abc或def {m} 扩展前一个字符m次 ab{2}c表示abbc {m,n} 扩展前一个字符m到n次(含n) ab{1,2}c表示abc, abbc … Continue reading

Posted in algorithms | Leave a comment

关于C指针的各种用法的具体值分析

在学习堆漏洞方面的知识时,会遇到各种指针,用于修改内存中的值,一直很混淆,因此在此进行了一个小实验,对C语言中指针的各种用法,具体值如何,做了一个比较详尽的实验。虽然花费了很长时间,但是很好地提高了对指针的理解。 #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define malloc_size 0x80 uint64_t *chunk0_ptr; uint64_t *chunk1_ptr; int main(){ chunk0_ptr = (uint64_t*)malloc(malloc_size);//chunk a chunk1_ptr = (uint64_t*)malloc(malloc_size);//chunk b printf(“&chunk0_ptr = %p\n”, &chunk0_ptr); printf(“&chunk1_ptr = %p\n”, &chunk1_ptr); printf(“结论: &p 为 p 在bss段(全局变量在bss段,局部变量在栈上) 的存储地址,且指针长度为4bytes\n”); printf(“chunk0_ptr = … Continue reading

Posted in algorithms | Leave a comment

求朋友关系中的朋友圈数量

题目描述 给出10W条人和人之间的朋友关系,求出这些朋友关系中有多少个朋友圈(如A-B、B-C、D-E、E-F,这4对关系中存在两个朋友圈),并给出算法的时间复杂度。 解答 这道题实际上考察的是”并查集”这一数据结构. 对于这类问题, 看似并不复杂, 但数据量极大, 如果用正常的数据结构来描述的话, 往往空间上过大, 计算机无法承受, 即使在空间上勉强通过, 运行的时间复杂度也极高. 只能用并查集来描述 并查集的主要操作 初始化 把每个点所在的集合初始化为自身. 通常来说, 这个步骤在每次使用该数据结构时只需要执行一次, 无论何种方式实现, 时间复杂度均为O(n) 查找 查找元素所在的集合, 即根节点 合并 将两个元素所在的集合合并为一个集合. 通常来说, 在合并之前, 应先判断两个元素是否属于同一集合, 这可用上面的”查找”操作来实现. 因此, 对于题目中的朋友圈关系, A-B, B-C, D-E, E-F.我们的算法过程如下: start => (A)(B)(C)(D)(E)(F) A-B => … Continue reading

Posted in algorithms | Leave a comment