- 博客(362)
- 收藏
- 关注
RSS订阅
原创 经典排序算法实现和总结
算法分类非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。算法复杂度:稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本...
2018-12-22 00:26:25
450
原创 Docker学习笔记(二) 使用Docker镜像和仓库
11.2记列出镜像：sudo docker images : 查看主机可用镜像拉取镜像：sudo docker pull fedora : 拉取fedora系列镜像到本地sudo docker pull fedora:20 : 只拉取指定标签的镜像(fedora:20)sudo docker images fedora : 查看fedora镜像的内容查找...
2019-11-04 23:40:37
774
原创 Docker学习笔记(一) Docker入门 ——Docker容器的基本操作
11.1记linux docker相关命令：查看docker状态： systemctl status docker 启动docker：systemctl start docker 停止docker：systemctl stop dockerdocker相关命令：运行第一个容器：sudo docker run -i -t ubuntu /bin/bash-i 开启标准...
2019-11-02 00:02:24
693
原创 秋招总结(四)-海量数据处理问题归纳
TOP N问题1.如何在海量数据中找出重复最多一个通过hash映射为小文件 通过hash_map统计各个小文件重读最多的并记录次数 对每个小文件重复最多的进行建立大根堆2.上亿有重数据，统计最多前N个 内存存不下 通过hash映射为小文件 通过hash_map统计各个小文件重读最多的并记录次数 对每个小文件重复最多的进行建立...
2019-09-20 00:17:25
778
原创 秋招总结(三)-操作系统归纳
1.进程和线程的区别 根本区别：进程是资源分配最小单位，线程是程序执行的最小单位； 开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。 内存方面：进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址...
2019-09-20 00:17:15
744
1
原创 秋招总结(二)-计算机网络归纳
1.网络编程一般步骤：TCP：服务端： socket->bind->listen->accept->recv/send->close 客户端：socket->connect->send/recv->closeUDP:服务端：socket->bind->recvfrom/sendto->close 客户端：socket-...
2019-09-20 00:17:05
858
原创 秋招总结(一)-C++归纳
STL相关：https://github.com/huihut/interview/tree/master/STL1.static关键字隐藏: static的全局变量和函数会对其它源文件隐藏 生命周期延长:被修饰的变量位于静态存储区, 对于静态局部变量,生命周期为整个程序而并非函数作用域 修饰类成员(静态成员变量和静态成员函数),静态成员变量和静态成员函数不属于任何对象,所有类实...
2019-09-20 00:16:56
1035
1
原创 Ping的工作原理
PING的工作流程我们以下面一个网络为例：有 A、B、C、D 四台机子，一台路由 RA，子网掩码均为 255.255.255.0，默认路由为 192.168.0.11.在同一网段内在主机 A 上运行“Ping 192.168.0.5”后，都发生了些什么呢? 首先，Ping 命令会构建一个 固定格式的 ICMP 请求数据包， 然后由 ICMP 协议将这个数据包连同地址“192.168....
2019-04-15 13:41:53
325
转载 局域网内和局域网间的通信(交换机与路由器)
交换机和路由器区别交换机主要是用于组建局域网，而路由器则是负责让主机连接外网。局域网间通信例子1： PC1与PC2通信时，在PC1电脑中，应用层产生数据交给传输层；传输层进行数据的分段，使数据的大小适合在网络上传递，根据应用层不同软件产生的数据，选择不同协议栈进行封装TCP或UDP,再进行不同服务端口号的封装（例...
2019-04-10 18:54:46
4539
原创 剑指offer：二叉树的下一个结点
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。AC C++ Solution:class Solution {public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode == NULL)...
2019-04-06 16:24:53
163
原创 剑指offer: 丑数
题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。AC C++ Solution:每个丑数都是前面的丑数乘以2,3,5得到的，所以此题可以通过动态规划解决！相当于维持三个队列class Solution {public: in...
2019-04-05 19:05:33
203
原创 剑指offer:二叉搜索树与双向链表
题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。解题思路：对于二叉搜索树，中序遍历的即是一个有序的序列，所以进行中序遍历从而构造一个有序的链表。class Solution {public: void inorder(TreeNode* cur, TreeNode*& pre) { ...
2019-04-04 11:13:38
229
原创 剑指offer: 按之字形顺序打印二叉树
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解题思路：利用一个双端队列，一个方向标志，当本行是从左往右遍历时，将其子节点按 左节点 右节点 的顺序先后加入到队列头；当本行是从右往左遍历时，将其子节点按 右节点 左节点 的顺序先后加入到队列尾；class Soluti...
2019-04-02 14:39:38
205
原创 剑指offer:把二叉树打印成多行
题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。解题思路：二叉树层次遍历, 利用一个队列，每层之间用一个NULL分割开，当遇到NULL则代表当前层已遍历完AC C++ Solution:class Solution {public: vector<vector<int> > Print(TreeNode*...
2019-04-02 13:35:26
159
原创 剑指offer: 二叉搜索树的后序遍历序列
题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。解题思路：对于BST的后序序列，最后一个元素即为根节点, 根节点的左子树为数组前段,右子树为数组后段；AC C++ Solution:class Solution {public: /* 对于BST的后序序列，最后一个...
2019-04-02 13:10:53
195
原创 剑指offer: 二叉搜索树的第K个节点
题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。解题思路：对于二叉搜索树，中序遍历即使从小到大的排序，同时用一个变量记录，当遍历到第k个的时候就返回。class Solution {public: TreeNode* KthNode(TreeNode* pRoot, in...
2019-04-02 12:57:12
199
1
原创 剑指offer: 滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,...
2019-04-02 12:45:52
168
原创 剑指offer: 机器人的运动范围
题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？解题思路：用一个二维数组记录每...
2019-04-02 12:42:46
258
原创 剑指offer:最小的k个数
题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。思路：使用C++中的mutiset容器(可包含重复元素)，multiset是有序的，使用greater<T>,使multiset呈递减趋势。 建堆的时候，默认是大根堆，第三个参数用greater<T>会变成小根堆； ...
2019-03-30 18:16:59
185
转载 数据库系统原理: 并发控制之悲观锁与乐观锁
1. 并发控制在多线程环境下，为了保证线程安全，需要使用并发控制。 数据库管理系统中有事务的概念，它是一组操作，并且满足 ACID 特性。一个事务可以看成一组任务，而任务是由线程驱动的，因此事务也可以并发地执行。并发执行多个事务时，为了保证每个事务都具有 ACID 特性，也同样需要使用并发控制。 ...
2019-03-25 09:31:48
412
原创 数据库系统原理: 封锁 (封锁粒度、封锁类型、封锁协议)
封锁封锁粒度MySQL 中提供了两种封锁粒度：行级锁以及表级锁。应该尽量只锁定需要修改的那部分数据，而不是所有的资源。锁定的数据量越少，发生锁争用的可能就越小，系统的并发程度就越高。但是加锁需要消耗资源，锁的各种操作（包括获取锁、释放锁、以及检查锁状态）都会增加系统开销。因此封锁粒度越小，系统开销就越大。在选择封锁粒度时，需要在锁开销和并发程度之间做一个权衡。封锁...
2019-03-24 23:42:24
3558
1
原创 LeetCode 300.Longest Increasing Subsequence (最长上升子序列)
题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是[2,3,7,101]，它的长度是 4。说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为O(n2) 。进阶:你能将算法的时间复杂度降低到O(nlogn) ...
2019-03-20 22:24:18
152
原创 LeetCode 239.Sliding Window Maximum (滑动窗口最大值)
题目描述：给定一个数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口k内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值---...
2019-03-19 23:04:31
212
原创 MySQL中键(key)和索引(index)的区别
key和index区别mysql的key和index多少有点令人迷惑，这实际上考察对数据库体系结构的了解的。 1.key 是数据库的物理结构，它包含两层意义，一是约束（偏重于约束和规范数据库的结构完整性），二是索引（辅助查询用的）。包括primary key, unique key, foreign key 等。 primary key 有两个作用，一是约束作用（constrain...
2019-03-14 15:12:46
16831
1
原创 为什么建立TCP连接需要三次握手，为什么断开TCP连接需要四次握手，TIME_WAIT状态的意义
为什么建立TCP连接需要三次握手？原因：为了应对网络中存在的延迟的重复数组的问题 (已失效的连接请求报文段)例子：client 发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达 server。本来这是一个早已失效的报文段。但 server 收到此失效的连接请求报文段后，就误认为是 client 再次发出的一个新的连接请求。于...
2019-02-19 17:40:32
2156
原创 C/C++ 字节对齐问题
字节对齐的原因 为了提高 CPU 的存储速度，编译器会对 struct 和 union的存储进行优化，即进行字节对齐。对齐方式 对于 struct 或 union 中的 struct 或者 union 来说，它们的字节对齐标准就是它的所有成员中字节数最大的数据的字节数。一般情况下 C/C++ 的变量所占用的字节数 char: 1字节； ...
2019-02-19 11:53:39
385
原创 C++中static关键字的作用
1.先来介绍它的第一条也是最重要的一条：隐藏。（static函数，static变量均可）当同时编译多个文件时，所有未加static前缀的全局变量和函数都具有全局可见性。举例来说明。同时编译两个源文件，一个是a.c，另一个是main.c。//a.cchar a = 'A'; // global variablevoid msg(){ printf("Hello\n");...
2019-02-19 00:22:47
504
原创 数据库系统原理:事务的特性,并发一致性问题以及隔离级别
事务概念事务指的是满足 ACID 特性的一组操作，可以通过 Commit 提交一个事务，也可以使用 Rollback 进行回滚。 ACID1. 原子性（Atomicity）事务被视为不可分割的最小单元，事务的所有操作要么全部提交成功，要么全部失败回滚。回滚可以用回滚日志来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。2. 一致性（C...
2019-02-12 22:35:09
695
原创 动画: 什么是散列表? (Hash Table 哈希表)
本文来自算法爱好者! (部分详细介绍)散列表散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。散列函数散列函数，顾名思义，它是一个函数。如果把它定义成hash(key...
2019-02-11 22:30:26
836
转载 扫码登录是如何实现的？
网页版微信刚推出时，无数人被它的登录方式惊艳了一下，不需要输入用户名密码，打开手机微信扫一扫，便自动登录。从原理上讲，二维码只能是一段文本的编码，如何用它实现快捷登录的呢？打开网页版微信，可以看到如下的页面：微信扫码界面如果你用我查查、支付宝、新浪微博等软件扫码二维码，你会发现此二维码解析出来是如下的网址：https://login.weixin.qq.com/l/obsbQ...
2019-01-30 21:41:18
1279
原创 操作系统之内存管理
虚拟内存虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失...
2019-01-29 22:14:37
708
原创 操作系统之死锁
死锁产生的必要条件 互斥：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。 占有和等待：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。...
2019-01-28 15:34:45
236
原创 操作系统之进程管理:进程通信
进程通信进程同步与进程通信很容易混淆，它们的区别在于：进程同步：控制多个进程按一定顺序执行； 进程通信：进程间传输信息。进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。1. 无名管道无名管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。#include &l...
2019-01-28 15:19:48
1053
原创 操作系统之进程管理:进程同步
进程同步1. 临界区对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。// entry section// critical section;// exit section 2. 同步与互斥同步：多个进程按一定顺序执行； 互斥：多个进程在同一时刻只有一个进程能进入临界区。 3. 信号量信号量（Se...
2019-01-28 14:18:41
364
原创 操作系统之进程管理:进程调度算法
进程调度算法不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。 1.批处理系统批处理系统，又名批处理操作系统。批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。这种采用批量处理作业技术的操作系统称为批处理操作系统。批处理操作系统分为单道批处理系统和多道批处理系统。批处理操作系统不具有交互性，它是为了提高CPU的利用率而提出的一种操作系统...
2019-01-11 19:42:05
1447
原创 手写函数:strlen(), strcpy(), strstr(), strcat(), strcmp(), memcpy()
strlen()函数功能：计算给定字符串的（unsigned int型）长度，不包括'\0'在内 实现:int strlen(const char *str) { assert(str != NULL); int len = 0; while( (*str++) != '\0') len++; return len;} strcpy()函数功能:...
2019-01-08 19:12:02
1813
2
原创 STL中内存池的实现
STL里的内存池实现STL内存分配分为一级分配器和二级分配器，一级分配器就是采用malloc分配内存，二级分配器采用内存池。二级分配器设计的非常巧妙，分别给8k，16k,..., 128k等比较小的内存片都维持一个空闲链表，每个链表的头节点由一个数组来维护。需要分配内存时从合适大小的链表中取一块下来。假设需要分配一块10K的内存，那么就找到最小的大于等于10k的块，也就是16K，从16K的...
2019-01-06 00:53:44
3987
4
原创 C++内存管理
在C++中内存分为5个区，分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。堆：堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。栈: ：局部变量，函数参数等存储在该区，由编译器自动分配和释放。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放...
2019-01-05 17:28:31
305
原创 剑指offer:删除链表中重复的节点
题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5AC C++ Solution:class Solution {public: ListNode* deleteDuplicates(List...
2019-01-05 10:01:25
168
原创 剑指offer:链表中环的入口结点
题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 AC C++ Solution:解题思路：还是使用两个指针，一个fast，每次移动两步；一个slow，每次移动一步。 a b start ------->-------->meeting (k)...
2019-01-05 10:01:19
158
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人