多线程
概要线程：进程内的执行单元，拥有自己的栈、寄存器、程序计数器，但与同一进程的其他线程共享地址空间 目的：并发执行以提高吞吐、利用多核、改善响应性、表达并发逻辑。 线程实现层次内核线程：由OS内核调度。线程创建/切换开销大，但能利用多核。 用户级线程：由用户态库调度，切换快但不能利用多个CPU（除非映射到内核线程）。 混合模型：库把用户线程映射到多个内核线程。 线程生命周期创建、可运行、运行、阻塞/等待、终止 主要同步原语（及用途）互斥锁（Mutex/Lock）：保护临界区，确保同时只有一个线程访问共享资源 自旋锁（Spinlock）：短期等待适用，忙等而不阻塞内核调度 读写锁（RWLock）：允许多个读者并行、写者独占。适合读多写少的场景 信号量（Semaphore）：计数资源控制 条件变量（Condition Variable）：线程A等待某条件，线程B改变条件并通知 屏障（Barrier）：多线程在屏障处同步，全部到达后继续 原子操作（Atomic）：无需锁的原子读写/更新 内存栅栏/屏障（Memory Barrier）：强制...
LeetCode Question Solve Trip
1.Two SumDescription of the problem 双循环遍历 时间复杂度：O(n2)O(n^2)O(n2) 空间复杂度：O(1)O(1)O(1) 12345678910111213141516class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>ans; for(int i=0;i<nums.size()-1;i++){ for(int j=i+1;j<nums.size();j++){ if(nums[i]+nums[j]==target){ ans.push_back(i); ans.push_back(j); break; ...
Go常见函数
删除字符串首尾所有的空白字符(包括空格、制表符、换行符) strings.TrimSpace(s) 12345678910111213package mainimport ( "fmt" "strings")func main() { s := "Hello World " // 末尾有空格 result := strings.TrimSpace(s) fmt.Printf("[%s]\n", result)} 删除字符串右边的空格 strings.TrimRight(s,” “) 1234s := " Hello World "res := strings.TrimRight(s, " ")fmt.Printf("[%s]\n", res) 删除字符串开头的空格 strings.TrimLeft(s,” “) 1234s := " Hello Wo...
Go命令行操作
123456789101112131415161718192021222324252627282930313233343536373839404142434445go version//检查Go是否安装go env//查看环境配置mkdir myapp//新建文件夹cd myappgo mod init myapp//初始化模块go list -m all//查看依赖go get -u github.com/gin-gonic/gin//更新依赖go run main.go//运行程序go build//生成可执行文件go build -o server.exe main.go//编译并指定输出文件名server.exe//执行二进制文件(Windows)go list//查看当前包依赖go mod tidy//下载依赖包go test//测试go test -v//带详细输出的测试go doc fmt//查看包文档go doc fmt.Println//查看函数文档go get <pkg>//下载依赖包go install//编译并安装包到GOBINgo clean...
TCP中何时会出现RST(reset)报文?
什么是TCP RST报文?RST报文段是TCP协议中的一个控制标志位，代表： 连接出现异常，立即中断当前连接 也就是说，RST=强制断开连接它不经过四次挥手，而是直接告诉对方：别再发了，这个连接无效 RST报文是TCP协议中用来终止一个连接的报文。当一个TCP连接出现异常时，比如主机崩溃、网络中断、连接超时等，TCP会向另一端发送一个RST报文来终止连接。 RST报文的常见触发时机我们可以分为三大类：无效连接、异常关闭、应用层拒绝 对方不存在的连接场景：收到非预期的TCP报文 服务器端口没在监听(没有listen()) 客户端乱发了一个SYN以外的数据包 收到数据的连接在本地不存在(比如已经被关闭) 常见原因： 程序没启动，端口没监听 应用崩溃，socket已释放 收到过期的包(老连接的残余包) 非正常关闭连接时场景：进程提前关闭socket，但仍有数据到达 应用层超时关闭，但对方还在发包 系统异常断开连接(如kill进程) 应用层主动拒绝连接(listen拒绝)场景：服务器正在运行，但明确拒绝连接 例如： 防火墙策略拒绝某个源IP 内核backlog...
两个进程间需要交换大量数据时，有哪些合适的进程间通信手段？
共享内存(首选)两个进程通过mmap、shmget/shmat或POSIXshm_open共享一块物理内存。常用于数据库缓冲区、视频播放器编解码和渲染器之间。 优点： 直接在同一块内存区读写，不需要内核反复拷贝，最快。 特别适合大文件传输、大矩阵/图像/音视频流 缺点： 需要额外同步机制(信号量/互斥锁/自旋锁)来保证读写有序 内存映射文件两个进程通过mmap将同一文件映射到自己的虚拟地址空间。常用于日志文件共享、大规模只读数据加载 优点： 适合大文件共享，只在缺页时才加载，减少不必要的拷贝 在文件系统支持下可实现持久化 缺点： 需要磁盘I/O(虽然有页缓存优化) 管道数据通过内核缓冲区传输，单向流式通信。常用于命令行进程链ls | grep | sort 优点： 简单，使用方便 缺点： 内核态到用户态有拷贝，效率远低于共享内存 缓冲区有限，不适合超大数据 嵌套字(Socket,本地Unix Domain Socket)两个进程通过socketpair或AF_UNIX通信。常用于Nginx、数据库客户端与服...
质数查找算法
朴素判断查找。。。略 埃拉托斯特尼筛法(埃式筛,Sieve of Eratosthenes)核心思想从小到大标记合数，未被标记的就是质数 实现竞赛常用范围n<=1e7 123456789101112131415161718192021const int N=1e7;bool isPrime[N+1];vector<int>primes;void sieve(int n){ fill(isPrime,isPrime+n+1,true); isPrime[0]=isPrime[1]=false; for(int i=2;i*i<=n;++i){ if(isPrime[i]){ for(int j=i*i;j<=n;j+=i){ isPrime[j]=false; } } } for(int i=2;i<=n;++i){ if(...
位运算
常见用途 用整型得每一位表示集合/状态(状态压缩/子集枚举) 用异或解决[成对出现]类问题、前缀异或或计数子数组异或 用lowbit在树状数组、枚举子集优化中快速操作 用bitset做超快的背包/集合操作，常把o(n*S /word)变成非常快的位并行 用位技巧做常数优化、逻辑判断(奇偶、是否是2的幂等) tips12345678// 记得：对于超过 31 位的位运算用 1LL 或 1ULLint test = (mask & (1 << k)); // 测试第 k 位 (0-indexed)mask |= (1 << k); // 将第 k 位置 1mask &= ~(1 << k); // 将第 k 位清 0mask ^= (1 << k); // 切换（toggle）第 k 位int lowbit = mask & -mask; // 取最低位 1（lowbit），m...
排序算法有哪些，哪些是稳定的排序算法
常见排序算法及稳定性 排序算法 平均时间复杂度 最坏情况 稳定性 适用场景 冒泡排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) 稳定 小数据量，教学 选择排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) 不稳定 小数据量 插入排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) 稳定 小数据量，几乎有序 希尔排序 O(nlognO(n lognO(nlogn~n2)n^2)n2) O(n2)O(n^2)O(n2) 不稳定 中小规模数据 归并排序 O(nlogn)O(n logn)O(nlogn) O(nlogn)O(n logn)O(nlogn) 稳定 大数据量，链表排序 快速排序 O(nlogn)O(n logn)O(nlogn) O(n2)O(n^2)O(n2) 不稳定 大数据量，数组排序 堆排序 O(nlogn)O(n logn)O(nlogn) O(nlogn)O(n logn)O(nlogn) 不稳定 大数据量，数组排序 计数排序 O(n+k)O(n+k)O(n+...
红黑树与AVL树的区别
定义 定义 平衡方法 AVL树 一种严格自平衡二叉搜索树(BST) 节点的左右子树高度差<=1 红黑树 一种弱平衡的自平衡BST 节点染色(红/黑)，保证从根到叶子每条路径黑色节点数量相同，并不严格要求高度差<=1 平衡策略 AVL树 高度严格平衡 插入/删除节点后，如果高度差>1，需要通过单旋转或双旋转来恢复平衡 优点：查找/删除效率非常高，平均复杂度O(logn) 红黑树 高度弱平衡(通过颜色约束维持) 每条从根到叶子的路径黑色节点数相同(黑高相等)，并不能有两个连续红色节点 插入/删除时通过变色+左右旋转调整 优点：插入/删除效率较稳定，旋转次数少 性能对比 性能指标 AVL树 红黑树 查找 高速，平均O(logn)，比红黑树略快 较快，O(logn)，查找略慢于AVL树 插入/删除 平衡严格，旋转次数多->相对慢 平衡较松，旋转次数少->插入/删除快 空间开销 每个节点存储高度信息 每个节点存储颜色信息...