1.求第k大的数？ 借助快排思想时间复杂度可以优化到O(n); 快排就是把数组分为比key(某个值)大和比key小的两堆，然后在分治。key的下标为i; 再求第k大的数时，我们可以把大值放到左边，在求出一个下标i后，如果i < K 就计算i左边的，如果i > k 就计算i右边的，直到i==k; 2.

一. 消息队列 为什么使用消息队列 消息队列是分布式系统中重要组件，使用场景很多，比较核心的有3个：解耦，异步消息，流量削峰。 解耦： 这样一个场景：A系统发送数据到B，C，D三个系统，通过接口调用发送。如果E系统也要这个数据，而C系统现在不需要了，这样A系统负责人就需要做很多操作.... 在这个场景中，A系统和其他各种系统严重耦合，A系统产生一条比较关键的数据，很多系统都需要A将这个数据发送过来。A系统要考虑BCDE等系统挂掉怎么办：要不要重发，要不要把消息存起来... 如果使用消息队列，A系统产生一条数据，发送到消息队列中，那个系统需要就自己去消息队列中取。如果新系统需要数据，直接去消...

结构体内存对齐 意义是减少cpu读取的次数，提高效率。 指针与引用的区别？ 定义和性质不同 指针是一个变量，存储的是一个地址，指向内存的一个存储单元 引用时变量的一个别名，与原来的变量实质上时一个东西 指针可以是多级的，引用只有一级 引用在定义的时候必须初始化，指针可以不初始化 指针初始化之后还可以在改变，引用不可以 自增运算意义不同 指针和引用作为函数参数时，指针需要检查是否为空，引用不需要 堆和栈的区别？ 堆和栈实际上是操作系统对进程占用空间的两种管理方式。 管理方式不同 栈由操作系统自动分配释放，无需手动控制； 堆的申请与释放工作由程序员控制，容易产生内存泄漏 ...

计算机网络 1. TCP/UDP问题 1.如何确定一个TCP连接 TCP四元组可唯一确定一个TCP连接。四元组中包含： 源地址，源端口，目标地址，目标端口。 源地址和目标地址的字段(32位)在ip头部中，作用：通过IP协议发送报文到目标主机。 源端口和目标端口的字段(16位)在TCP头部中，作用：告诉TCP协议应该把报文发送给哪个进程。 2.TCP最大连接数量 客户端IP数量 * 客户端端口数量 对于IPV4：客户端最大IP数量位2的32次方，客户端端口数量为2的16次放，即服务器单机最大连接数量约为2的48次方。 但服务器最大并发TCP连接数量...

git status git stash git diff git stash apply 多人开发同一分支： 切换到fix_bug分支 git checkout fix_bug 修改bug 提交代码 git stash git pull git stash pop // 可能有冲突，合并代码 git add . git commit -m '修复bug' git push // 如需多次提交，重复上述提交代码命令即可

1.go mod tidy 遇到大型文件，会爆问题，这个时候可以用另一个命令：GIT_LFS_SKIP_SMUDGE=1 go mod download -x -json。这个不要在编译器的终端运行，在命令行中运行。

placement new 是重载operator new的一个标准，全局的版本，他不能被自定义的版本代替(不像普通的opertor new和opertor delete能够被替换成用户自定的版本)。 原型： void *operator new(size_t, void *p)throw() return { p;} 区分关键字： new, operator new, placement new new和delete操作符：对堆中的内存进行申请的释放， 这两个是不能被重载的； 而要实现不同的内存分配行为，需要重载operator new， 而不是...

写个倍增LCA二叉树倍增按照2的次幂来增加， 即1, 2, 4, 8... 首先我们先预处理出每个节点2^j级祖先 用f[i][j] 表示i节点的2^j级祖先查询时从大向小跳，即按照8, 4, 2, 1来；具体:先把两个节点提到同一高度，在统一开始跳。一直跳到父亲节点相同，即为最近公共祖先。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * ...

#include <iostream> #include <algorithm> #include <stdlib.h> #include <vector> using namespace std; typedef long long LL; int matrix[1010][1010]; vector<int> res; void solve(){ int n, m; std::cin >> n >> m; for (int i = 0 ; i < ...

题目链接 题意： 给一个nn的棋盘， 棋盘上有m个障碍，要求用12的多米诺骨牌进行掩盖。且任意两张骨牌都不重叠，障碍上不能有骨牌。 思路： 1*2的骨牌且骨牌不能有重叠，这个性质很容易想到二分图。 怎样建这个图呢？ 将棋盘上的点提出来， 每个点与它相邻的四个点进行连边操作，这样见图就完成了 建图似乎有点麻烦，那就简化一下，我们将每个点与它的相邻上边和左边的点连边，至于他的右边和下边的点，在后面的连边操作中都加进去， 这样就可以不重不漏了. 建图完成就是求二分图最他匹配板子了没什么好说的了 代码： #include <iostream> #include <algorit...

Tree Partition 题意: 给一棵树,n个点n-1条边,没给点都有点权。要求剪掉k-1条边形成由k颗树组成的森林。树的权值为中所有点权之和问：怎样剪使得树的权值的最大值最小, 大小为多少？ 解题： 看到“最大值最小”这类词, 先是想到了二分，二分出权值，再根据权值对树进行剪边操作，觉得可行就继续操作: 二分出权值mid； 在树中由下向上进行操作，每个节点记录节点及其儿子权值和,如果当前节点权值>mid,让当前节点由大到小减去其儿子节点直到当前节点<=mid,没见一次计数(count)加1 如果操作完后count > k - 1 说明mid小 增大mid继续操作2...

K.Color Graph 题意： 给一个无向图n个点m条边，给一些边涂红色。要求红色边不能有奇环.求能染红的最多的边。 解题： 题目中讲到了奇环， 这很容易往二分图上想。 定理：一个无向图是二分图，当且仅当图中不存在奇环 接下里就是找是二分图的最多的边。我们一般是分两个集合进行操作，在这个题中由于n最大值为16，所以我们可以用二进制进行枚举对n个点进行分集合操作。判断相连的两个点是否在一个集合中不在答案就++，最后求出所有情况下的最大值即为答案。 废话说多了上代码 #include <iostream> #include <algorithm> #include &...

石头剪刀布 解题： 求最高分由于输了不扣分所以肯定是能赢就赢，求出赢最多的次数，肯定就是min(a1, b2) + min(b1, c2) + min(c1, a2);再次基础上求出平局最多即为所求：这里就是用他们原来的减去赢了的，在取对应位置最小值min(a2 - min(c1, a2),a1 - min(a1, b2)) + min(b2 - min(a1, b2),b1 - min(b1, c2)) + min(c2 - min(b1, c2),c1 - min(c1, a2)); #include <iostream> #include <algorithm&gt...