aaronlanni的博客

原创 控制台版本的flyappybird

首先展示一下游戏的效果图在这个小游戏中，最重要的是能够实现游戏界面的刷新以及对每次输入之时隐藏光标的位置，从而防止当键盘控制小鸟位置的移动之时，从而使得屏幕出现刷新的情况1、实现对屏幕的刷新使用的是win32中的一个函数，他是win32自带的库函数，能够实现对图形化界面的操作void gotoxy(int x, int y){ HANDLE handle = GetStdHa...

原创 【剑指offer】孩子们的游戏

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下...

原创 【剑指offer】二叉搜索树的后序遍历序列

【题目描述】输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，如果是，则输出YES，不是输出NO，假设你的二叉搜索树的结点各不相同。有关什么是二叉搜索树，请移步：https://blog.csdn.net/aaronlanni/article/details/79180890由此可以看出，将一个二叉搜索树转换为一个后序遍历的序列，其根结点会将这个序列分为两部分，一部分比根节...

原创 【剑指offer】将二叉树打印为多行

题目描述：从上到下按层打印二叉树，同一层结点从左至右输出，每一层输出一行题目解答：将二叉树从上打印，并且将其同一层的结点进行输出，此种题目，首先我们想到的就是层序遍历，将每一个结点保存在一个队列中，然后使用队列中的元素作为分割，如果这一层的结点输出完成，则将其直接push到一个vector中，从而实现了每一层只有一行，具体描述如图所示代码如下所示：/*struct TreeNo...

原创 add-two-numbers

【题目描述】 You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return ...

原创 【LeetCode】convert-sorted-list-to-binary-search-tree

题目描述：Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 即将一个有序链表转换为一个平衡的二叉搜索树，即AVL树 思路：找到这个有序链表的中间结点，从而划分出左右两个部分，将中间结点作为根节点，从而分别建立出这个根结点的左右...

原创 【LeetCode】reord_list

题目描述：Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→… You must do this in-place without altering the nodes’ values. For example, Given{1,2,3,4}, reo...

原创 复杂链表的复制

问：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 解答：对于复杂链表，一般形式会在next域的基础上增加一个random域，这个指针会指向任意的结点，当然，其也可以指向空指针域，其一般结点的构造形式为： 因此在对复杂链表进...

原创 数据库初始

一、基本概念 1、什么是数据库 文件存储的缺点文件的安全性问题文件不利于查询和对数据的管理文件不利于存放海量数据文件在程序中控制不方便 数据库：高效的存储和处理数据的介质(介质主要是两种：磁盘和内存） 磁盘型数据库：mysql 内存型数据库：Redis 2、理想的数据库的特征充足的容量—-主要用于海量数据的存储足够的安全和审核—-数据的安全存储，防止不安全行为的发生，同...

原创 有关UDP与TCP

有关TCP的连接释放问题，请见上一篇文章 https://blog.csdn.net/aaronlanni/article/details/80644709（TCP的三次握手与四次挥手） 一、UDP协议 （一）概述 1、特点 a：UDP是无连接的，减少了开销和发送数据之前的时延。 b：UDP尽最大努力交付 c：UDP面向报文：应用层交给UDP多长的报文，UDP照样发送，即一次发送一个...

原创 DNS域名解析

1、概念 是因特网使用的命名系统，用来把便于人们使用的机器名字转化为IP地址，在域名结构中，会出现十分重要的“.” 在因特网中，将其设计为一个联机分布式数据库系统，并采用客户服务器方式。 域名到IP地址的解析如下所示：当某一个应用进程需要把主机名解析为IP地址时，该应用进程就调用解析程序，并成为DNS的一个客户，把待解析的域名放在DNS的请求报文中，以UDP用户数据报方式发给本地域名服务器（...

原创 三次握手与四次挥手

运输连接有三个阶段：连接建立、数据传送、连接释放 TCP在链接建立的过程中要解决三个问题 1）要使双方都能够确知对方的存在 2）要允许双方协商一些参数（如最大窗口值，是否使用窗口扩大选项和时间戳选项以及服务质量等） 3）能够对运输实体资源（如缓存大小、连接表中的项目等）进行分配 主动发起连接建立的应用进程叫做客户、而被动等待连接建立的应用进程叫做服务器 服务端状态转化: [CLO...

原创 计算机网络

一、计算机的发展 1、计算机网络的功能 a、连通性：使得上网用户之间可以交换信息 b、共享：共享资源 2、因特网的概述 网络：由若干结点和连接着这些结点的链路组成，网络中的结点可以是计算机、集线器、路由器、交换机等，（互联网是“网络中的网络”，将网络与网络通过路由器连接在一起） 因特网（Internet）：世界上最大的网络，网络是将许多计算机连接在一起，而因特网是将许多网络连接在一起 ...

原创 线程死锁

一、什么是死锁 例如系统中只有一台扫描机与刻录机，现在，两个进程都准备扫描文档并且将其刻录到CD上，在某一时刻，进程P1占用扫描机，进程P2占用刻录机，后来P1又去请求刻录机但是因为他被分配给P2从而获得不了这个资源，相同原理，P2请求扫描机也不能获得这个资源，而双方都希望对方先释放其占用的资源，但他们都因为不能获得所需资源去继续运行，从而无法释放自己占用的资源，因此双方就一直处于这种僵持的状态...

原创 守护进程

有关会话与进程组的概念，请参考上篇文章进程间关系 https://blog.csdn.net/aaronlanni/article/details/80184460 一、基本概念 1、守护进程也称精灵进程（Daemon），是运行在后台的一种特殊进程。不受用户登录与注销的影响，只要机器不关机，则 一直存在。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。守护进程是一种很有用的...

原创 【数据结构】位图

一、基本概念 在存储数据之时，如果按照其原数据类型存储数据，如果要存取大量数据之时，有可能会由于数据元素个数较多且类型较大，不能一次性存储，而采用位图，将极大的解决这个问题。 位图是利用数组，将数组下标与元素一一对应，将元素所在的这个比特位的状态改为存在，则可以表明这个元素的状态即可。 主要表示为如下： 二、代码实现#include<iostream>using ...

原创 【数据结构】哈希开散列

原创 哈希闭散列实现

在上一篇文章中，我们已经对哈希的基础有了一个大概的认识，但是对其实现还没有做具体的解释，在这篇文章中，我们将对这一部分做出一个详细的解释。 有关哈希基础， 请参考上篇https://blog.csdn.net/aaronlanni/article/details/79701843 一、实现静态的哈希表 下面，将给出静态实现：//静态#define MAX_SIZE 10t...

原创 进程间关系

（一）进程组 每个进程除了有一个进程ID之外，还属于一个进程组。进程组是一个或多个进程的集合。通常，它们与同一作业相关联，可以接收来自同一终端的各种信号。每个进程组有一个唯一的进程组ID。每个进程组都可以有一个组长进程。组长进程的标识是其进程组ID等于其进程ID。 组长进程可以创建一个进程组，创建该组中的进程，然后终止。只要在某个进程组中一个进程存在，则该进程组就存在，这与其组长进程是否终止无关...

原创 【数据结构】排序算法之计数排序与基数排序

一、计数排序 很好理解，就是对应每个数我们统计每个数字出现的次数，然后用一个直接定址的哈希表来存放数据，在通过遍历这个哈希表，进而就可以排好序了 如下所示： 代码实现如下所示：void CountSort(int *array, int size){ assert(array || size < 0); int minData = array[0]; ...

原创 【数据结构】排序算法之归并排序

基本思想：将待排序的元素序列分成两个等长的子序列，再将子序列划分子序列，直到子序列中只有一个元素就不用在对子序列继续进行划分，将划分的每个区块，进行排序，然后再将其归并到一个序列中，直到将所有的子序列归并完成之后，则这个序列就完成了排序。 1、基本思想如下所示： 经过上面的划分，从而可以看出经过划分与归并，使得元素就有序。 但是要使得两个区间的元素能归并到一个区间中，如果只是将一个元素搬...

原创 【数据结构】之交换排序

一、冒泡排序 第1趟：依次比较相邻两个数据元素(i = 0,1,2,…, n-2),若array[i]>array[i+1],则交换两个元素，否则不交换，这样数值最大的数据元素将被防止在a[n-1]中； 第2趟：数据个数减1，即数据元素个数为n-1，操作方式和1类似，排完之后数据序列中的次大元素保存在array[n-2]中； 当n-1趟结束时，排序结束。 实现代码如下所示：...

原创 算法分析神奇之时间复杂度、空间复杂度、稳定性

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

原创 【数据结构】排序算法之选择排序

一、选择排序——最差的排序算法 在选择排序中，假定我们需要升序，因此在每次排序中，需要找到最大的元素，将其放在最后，在每一次的循环中，都是将最大的元素放在最后，因此对于数据较多的数组，循环的次数将与数组中元素的个数一致，因此，在对于这种数组进行排序时，将十分的浪费时间。 有关选择排序的思路，如下所示： （一）方式一，默认数组中最后一个元素最大，如下图所示： 代码如下所示：void ...

原创 【数据结构】排序算法之插入排序

一、排序概念 1、概念 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 2、排序分类 3、各种算法的性...

原创 【Linux】多线程初识

一、线程概念 1、线程引入 假设有一个mp3程序，他的主要任务是从内存中读取文件，对文件进行解压，最后再将这个文件播放出来，因此他需要三个步骤，才能完成这一个任务，如果将其放在一个进程中，有可能造成在读以及解压过程比较慢，当这边的文件已经播放完成，但是那边还没有读取或者解压完成，将会造成CPU的长时间等待，或者 有可能造成文件播放杂乱，因此有的人就提出以下两种方法： 方法一：分别由三个进程，控

原创 【数据结构】并查集

一、基本概念 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。在一些有N个元素的集合应用问题中，通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。 1、概

原创 Linux信号集

在上一篇文章中，我们已经介绍了Linux中有关进程信号的一些基础知识，现在，我们再来看一下在一个进程中，如何阻塞信号，以及如何在内核中捕捉信号。 Linux信号概念https://blog.csdn.net/aaronlanni/article/details/79794665 一、阻塞信号 1、信号与其相关概念 实际执行信号的处理动作称为信号递达(Delivery)信号从产生到递达之间

原创 Linux进程信号

一、信号的概念 要了解进程信号，首先要对进程的概念做一个简单的了解，要知道这一部分，请参考上一篇文章，进程概念。https://blog.csdn.net/aaronlanni/article/details/79774496 1、信号的基本概念 信号（signal）是linux进程通讯中的一种方式。 信号从软件层次上看是对中断机制的一种模拟。一个进程收到信号时的处理方式与CPU收到中断请...

原创 进程控制

一、进程创建 在进程概念那一章节，我们已经了解到了基本的进程创建的方式，现在我们在对其做一个回顾与总结。 1、fork函数创建子进程 （1）fork的概念 在一个已经存在的进程中创建一个新进程，原进程为父进程，新进程为子进程 。其中，子进程完全以父进程为模板进行创建，将父进程的数据结构拷贝给子进程，对于子进程的数据进行写时拷贝。 现在，我们再来认识一下fork#include &lt...

原创 VIM的使用以及Makefile的编写

一、有关vi与vim 1、概念 - vi编辑器是所有Unix及Linux系统下标准的编辑器，他就相当于windows系统中的记事本一样，它的强大不逊色于任何最新的文本编辑器。他是我们使用Linux系统不能缺少的工具。由于对Unix及Linux系统的任何版本，vi编辑器是完全相同的，学会它后，我们将会在Linux的世界里畅行无阻。 - vim 具有程序编辑的能力，可以以字体颜色辨别语法的正...

原创 进程概念

一、计算机结构 在要了解进程之前，需要先对计算的组成有一个大概的了解，这对于我们理解进程，有着很大的帮助。 在现在的计算机中，大多采用冯诺伊曼体系结构，在冯诺伊曼中，主要有以下几个部件。 这里需要注意一下几点： - 这⾥里的存储器指的是内存 - 不考虑缓存情况，这⾥里的CPU能且只能对内存进⾏行读写，不能访问外设(输⼊入或输出设备) - 外设(输⼊入或输出设备)要输⼊入或者输...

原创 哈希

在前面我们已经学到很多在一个结构中查找一个元素，不同的结构的方法不同且实现时的时间复杂度与空间复杂度都有不同，但是但部分的查找都是经过比较，从而找出自己要查找的主要元素。由此我们就想，有没有一种方法不通过比较，从而快速的找到需要的数据，因此，在这里我们就提出了哈希查找，利用存储位置并按照此位置进行存放元素，从而极大的实现了我们的查找效率。下面我们将对哈希查找展开来讲。 目前我们了解到的查找主要有以

原创 基础IO

一、C语言中的IO 在学习C语言之时，已经对IO函数有了一个基本的认识，了解到了他们是对文件做一些相关的操作，从而使得我们可以对文件进行一系列的操作，例如打开文件fopen，关闭文件fclose，往文件中写东西fwrite，从文件中读取内容fread，等等…… 从上面的这些内容可知，对文件的操作也是需要一定的步骤，从而才能正确的实现我们的要求，下面来看一下C语言中文件操作函数的具体做法FILE

原创 Linux基本命令

一、Linux基本命令 （一）基础 1、Linux命令的组成部分* 命令字* 命令选项参数（“选项”）* 命令操作参数（“参数”）2、相对路径与绝对路径 相对路径：从当前工作目录开始表达的路径形式 绝对路径：从根目录”/”开始表达的路径形式 3、查看机器的ip地址 ifconfig：inent后面为ip地址 在Xshell中使用ssh+ip地址连接到终端 （二）Linux命令

原创 【数据结构】数据结构之AVL树

一、AVL树的来源 AVL树是一种搜索树，但在搜索效率上，容易形成单支树的情形，因此在查找元素相当于在顺序表中搜索元素，效率低下。

原创 使用两个队列实现一个栈，使用两个栈实现一个队列

一、栈与队列的特点 （一）栈 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。不含任何元素的栈称为空 栈，栈又称为后进先出的线性表。 栈的特点：后进先出(LIFO) （二）队列 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作 的特殊线性表。进行插入操作的一端称为队尾，通常称为入队列；进行删除操作的

原创 二叉树面试题之三

对于二叉树的其他操作，参考前面两篇文章http://blog.csdn.net/aaronlanni/article/details/78698559 http://blog.csdn.net/aaronlanni/article/details/79317946 今天，在介绍一下二叉树中一些其他的内容，详情请看下面 一、判断一个结点是否在二叉树中 在此处，判断一个结点是否在二叉树中，利用结...

原创 二叉树的面试题之判断树

在前面，已经介绍过了，有关二叉树中的一些基本操作，如果大家对这些还不是十分熟悉，可以参考上一篇文章，有关二叉树的遍历方式：http://blog.csdn.net/aaronlanni/article/details/78698559 今天，主要介绍一些二叉树中，常见的一些操作： 一、判断一棵树是否是完全二叉树 完全二叉树：如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同，...

原创 查找一个字符串中第一个只出现两次的字符

问题描述 查找一个字符串中第一个只出现两次的字符。例如：“abcdefabcdefabc”中第一个只出现两次的为“d”，要求时间复杂度为O(1),空间复杂度为O(1) 解决思路 1、建立一个Hash表，用来存储每一个字符出现的次数，即一个字符的大小：256（无符号类型） 2、对Hash表中的每一个的字符进行初始化 3、存储数组中每个字符出现的次数，将其保存在Hash表中 4、从数组的起