Doraemon's Blog

题目 click here 题解传统快速排序12345678910111213141516void quickSort(int a[], int l, int r) { if(l >= r) return ; int bas = a[l]; int i = l, j = r; while(i < j) { while(i < j && a[j] >= bas) j --; a[i] = a[j]; while(i < j && a[i] <= bas) i ++; a[j] = a[i]; } a[i] = bas; quickSort(a, l, i-1); quickSort(a, i+1, r);} Hack数据1严格单调有序的数组 时间复杂度会退化为O(n2) 解决方案：随机化数组或者随机取基准值（而非第一个） 12int id = l + rand() % (r - l + 1);int bas = a[id]; Hack数据2所有数据都相等的数组 ...

红黑树就是满足以下特性的二叉树 所有节点只有红色和黑色 红色节点的孩子都是黑色（红色节点不能相邻） 黑色节点到任意叶子节点的简单路径上经过的黑色节点数量相同 叶子节点不存储值，而且叶子节点都是黑色的 满足这样特性的二叉树高度一定不超过2log(n+1) 下面是证明 如果把红色节点全部删掉，把下面的剩下的所有节点都连接在一起，那么新产生的树就是一颗每个节点最多有四个子节点的树，计算高度可以采用满四叉树的高度来近似计算，即log(n)，而把删除的红色节点加上就是2倍 红黑树相较于AVL，其查找效率略低一点，而插入删除效率高出AVL很多，所以当插入删除操作很多时可以使用红黑树

什么是高并发高并发指通过设计保证系统能够同时并行处理很多请求，是分布式系统非常重要的概念 评价分布式系统性能的指标有： 响应时间：系统对请求做出响应的时间。 吞吐量：单位时间内处理的请求数量。 QPS（和吞吐量基本没啥区别）：每秒响应请求数。 并发用户数：同时承载正常使用系统功能的用户数量。 水平扩容和垂直扩容那么如何实现高并发呢？ 上图都是实现高并发的方法，而这里只介绍水平扩容和垂直扩容 垂直扩容这是过去一直在使用并且可以马上见效的方法，但是缺点也很致命，垂直扩容有两种方案 提升单机硬件配置 例如：增加CPU核数如32核，升级更好的网卡如万兆，升级更好的硬盘如SSD，扩充硬盘容量如2T，扩充系统内存如128G； 改善单机架构 例如：使用Cache来减少IO次数，使用异步来增加单服务吞吐量，使用无锁数据结构来减少响应时间； 但是这种方式势必会受到科技的限制，性能有极限，如果想突破这种极限，实现线性上升，就需要水平扩容 水平扩容增加服务器数量，把请求尽量均匀地分配到各个服务器上，这也是分布式系统的目标。 举个例子，通常一个域名绑定一个IP，而一个IP对应一个服务器，当 ...

题目链接 click here 题解此题目是寻找两个数组组合为一个数组后的中位数，我们知道两个数组的长度，中位数是组合后的数组第几个数字我们是知道的，问题就转化为了寻找组合后数组的第k个数字，要求时间复杂度在log(n)，明显是二分，但是二分什么呢？一般都是二分两个数组，但这道题不同，需要二分的是k，对于两个数组而言，比较两个数组的第k/2个数字，小的一方前k/2个数字都不会是中位数，可以直接排除，从而快速缩小范围 123456789101112131415161718192021222324252627282930313233class Solution { public: double find(int k, vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); int id1 = 0, id2 = 0; while(true) { ...

程序运行截图倒计时 闹钟设置界面 闹钟弹窗提示+提示音 源码 gitee源码链接 软件打包

功能三个模型都是用来判断是否有被监听的socket状态发生改变（读写和异常） select首先介绍一下fd_set这个数组，这其实是一个类图，其中每一位表示一个socketfd，哪一位是1表示这一位对应的socket就是被监听的，有三种需要监听的状态，所以就有三个数组，分别是readset，writeset、exceptset，分别监听读写和异常 select原型： 12int select(int maxfd, fd_set* readset, fd_set* writeset, fd_set* exceptset, const struct timeval* timeout);> maxfd表示监听的最大fd（给定了范围） 三种状态的数组 timeout表示超时时间，当timeout是NULL表示select只有监听到状态发生变化才会结束否则被阻塞，timeout是0表示select非阻塞，立刻返回，timeout>0（数据结构内部有int）表示过一定时间后若还未检测到状态变化就结束 返回值为状态变化的fd数量，若返回-1表示错误 原理select采用轮询的方 ...

运行截图向右分屏 多分屏 全屏显示 介绍实现了一个类似vscode和matlab的标签页显示分屏效果，支持鼠标拖拽分屏、全屏显示，可自适应调整大小，程序把要显示的Widget独立出来，可随时替换为其他的用户自定义Widget，例如3d模型、二维画图等 存在的问题 加载图片会非常卡，猜测是paintEvent频繁调用而每次绘制图片复杂度高导致 分屏不能等分分屏，应该不难实现 源码 gitee源码

我们写程序时，都会搭建相关的环境，比如写了一个web，使用了tomcat、nginx等，现在想要把程序部署到云服务器或者在其他电脑上运行，就需要重新部署一遍环境，尤其是项目开源后，上手成本大。 docker介绍Docker 是一个开源的应用容器引擎，基于 Go 语言 并遵从 Apache2.0 协议开源。 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中，然后发布到任何流行的 Linux 机器上，也可以实现虚拟化。 容器是完全使用沙箱机制，相互之间不会有任何接口（类似 iPhone 的 app）,更重要的是容器性能开销极低。 （来源于菜鸟教程） 安装docker依赖于linux内核，因此在windows系统中需要安装Hyper-V（类似于 VMWare 或 VirtualBox）或者WSL，然后进入docker desktop官网下载安装程序，双击运行即可。安装完成后可以在虚拟机中运行命令docker —version检查是否成功安装。 镜像和容器的区别Docker 中镜像（Image）和容器（Container）是两个核心概念，它们有以下主要区别： 定 ...

explicit 作用: 防止隐式类型转换 1234567891011121314151617class Complex { private: double real, imag; public: Complex(){ } Complex(double _r, double _i): real(_r), imag(_i) { }};int main(){ Complex t = { 1, 2};} 以上代码不会报错，因为t = {1, 2}这里发生了隐式类型转换，将{1, 2}转化为了Complex(1, 2)，产生了一个匿名对象，然后把匿名对象赋值给t(这种赋值只是简单的值拷贝操作，假如存在指针，这种操作有浅拷贝的隐患) 但如果在构造函数前面加上explicit关键字，以上代码无法通过编译，因为explicit不允许隐式类型转换，等号右边的类型与左边的类型不符，则编译失败

706. 设计哈希映射处理冲突方法采用链表法，利用list 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class MyHashMap { public: vector<list<pair<int, int>>> data; static const int base = 769; static int hash(int x) { return x % base; } MyHashMap(): data(base) { } void put(int key, int value) { for(auto it = data[hash(key)].begin(); it != data[hash(key)].end(); it + ...