Rogn

2020年3月25日

摘要：题目：设计一个算法发现一个数组中和为指定值的所有数对。数组是无序的且值可能重复。分析：有一种方式是排序+双指针。另一种是先用map统计，再在map中查找target-num。这里可以使用unordered_map（也就是哈希），时间复杂度是O(n). vector<vector<int>> p 阅读全文

posted @ 2020-03-25 22:16 Rogn 阅读(725) 评论(0) 推荐(0)

map底层为什么要用红黑树实现

摘要：红黑树的特点红黑树是二叉查找树，但在每个节点增加一个存储为表示节点的颜色，可以是红色或黑色（非红即黑），通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长两倍。因此，它是一种弱平衡二叉树，相对于严格的AVL树来说，它的旋转次数少，所以对于查找、插入、删除较阅读全文

posted @ 2020-03-25 11:44 Rogn 阅读(5931) 评论(0) 推荐(0)

I/O复用

摘要： select/poll/epoll 都是 I/O 多路复用的具体实现，select 出现的最早，之后是 poll，再是 epoll。 select int select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, stru 阅读全文

posted @ 2020-03-25 09:20 Rogn 阅读(193) 评论(0) 推荐(0)

五大IO模型

摘要：一个输入操作通常包括两个阶段：等待数据准备好从内核向进程复制数据对于一个套接字上的输入操作，第一步通常涉及等待数据从网络中到达。当所等待数据到达时，它被复制到内核中的某个缓冲区。第二步就是把数据从内核缓冲区复制到应用进程缓冲区。 Unix 有五种 I/O 模型：阻塞式 I/O 非阻塞式 I/ 阅读全文

posted @ 2020-03-25 09:01 Rogn 阅读(485) 评论(0) 推荐(0)

2020年3月24日

打印二叉树的右视图

摘要：解法一：BFS+记录dep深度如果某节点dep小于下一个节点，说明该节点是本层的最右节点。如果该节点弹出后队列为空，同样该节点也是最右节点。 vector<int> rightSideView(TreeNode* root) { if(root == NULL) return vector<int 阅读全文

posted @ 2020-03-24 23:22 Rogn 阅读(916) 评论(0) 推荐(0)

数据库的三大范式

摘要：转载自：Ruthless-数据据设计三大范式三个范式：第一范式：所有的属性都不能再分割第二范式：所有的非主属性都完全依赖于每个候选键，而不能只是候选键中的一部分（消除部分函数依赖）第三范式：非主属性不传递依赖于候选键（消除传递依赖）我们这样定义范式有什么作用呢？第一范式第一范式是最基本阅读全文

posted @ 2020-03-24 22:11 Rogn 阅读(534) 评论(0) 推荐(0)

SQL 中left join、right join、inner join的区别

摘要：三个join的含义： left join（左联接）：返回左表中的所有记录和右表中的联接字段相等的记录。 right join（右联接）：返回右表中的所有记录和左表中的联接字段相等的记录。 inner join（等值联接）：只返回两个表中联接字段相等的记录。下面将以atable、btable为例进行阅读全文

posted @ 2020-03-24 21:18 Rogn 阅读(486) 评论(0) 推荐(0)

2020年3月23日

一文解决 4 道「搜索旋转排序数组」题

摘要：转载自：leetcode题解区-一文解决 4 道「搜索旋转排序数组」题本文涉及 4 道「搜索旋转排序数组」题： LeetCode 33 题：搜索旋转排序数组 LeetCode 81 题：搜索旋转排序数组-ii LeetCode 153 题：寻找旋转排序数组中的最小值 LeetCode 154 题：阅读全文

posted @ 2020-03-23 16:52 Rogn 阅读(2666) 评论(2) 推荐(0)

leetcode41-缺失的第一个正数

摘要：题目：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。要求时间复杂度O(n)、空间复杂度O(1) 分析：首先想到用个vis数组，数组开多大呢，需要根据数的范围（其实只需要开n的大小，因为我们不需要关心小于1和大于n的数）但是这样需要额外的空间，不符合题意。于是想着能不能将原数组当作vi 阅读全文

posted @ 2020-03-23 12:02 Rogn 阅读(278) 评论(0) 推荐(0)

微信网页版扫码登陆的原理

摘要：网页版微信刚推出时，无数人被它的登录方式惊艳了一下，不需要输入用户名密码，打开手机微信扫一扫，便自动登录。从原理上讲，二维码只能是一段文本的编码，如何用它实现快捷登录的呢？简易版（不涉及具体技术）打开微信网页版，会出现一个二维码，用非微信的扫码工具扫码，你会发现此二维码解析出来是类似如下的网址：阅读全文

posted @ 2020-03-23 09:42 Rogn 阅读(1315) 评论(0) 推荐(0)

公告