SUKEPP-CSDN博客

原创进程调度01_操作系统类型

1. 操作系统类型Reference1.1. 单道批处理系统当 CPU 进行计算操作的时候，外部设备空闲；当外部设备进行 I/O 操作的时候，CPU 空闲。CPU 和外部设备是完全串行的工作状态。1.2. 多道批处理系统为了解决单道批处理系统存在的忙闲不均的问题，就出现了多道批处理系统。一次从磁带或磁盘上同时装入多个用户作业到内存中，使这多个作业同时处于运行状态。当该系统对计算硬件具有一...

2020-04-11 09:15:44 160 1

原创算法分析03：排序算法

1. 排序算法分类基于选择的排序算法基于选择的排序算法选择排序（Selection Sort）堆排序（Heap Sort）：将元素全部存储与最大（最小）堆中，再依次取出即可实现基于交换的排序冒泡排序（Bubble Sort）快速排序（Quick Sort）快速排序的实现分为三个步骤：选择基准值（Pivot）分割操作（Partition）递归...

2020-03-28 08:24:16 124

原创算法分析02：动态规划

1. 定义动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。2. 适用情况最优子结构大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结...

2020-03-28 08:17:12 156

原创算法分析01：分治

1. 定义将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），递归的求解这些子问题（Conquer），然后再合并（Combine）这些子问题的解来建立原问题的解。2. 基本过程Divide：将问题的规模变小Conquer：递归的处理小规模问题（只需递归调用即可）Combine：将小规模问题的解合并为原始问题的解3. 分治与动态规划的关系StevenSun2014 ...

2020-03-28 08:02:04 111

原创数据结构分析01：线性表

1. Linked List1.1. 哨兵问题链表的插入或者删除操作存在邻居依赖问题对于单向链表，插入或者删除操作需要依赖前驱结点或者后继结点依赖前驱节点的原因该情况下实现相关操作需要修改前驱结点的 next 变量，如果没有前驱哨兵的话，这样会导致插入首结点与插入其余结点时代码实现不一致，因为首结点没有前驱结点，从而增加了代码复杂度。所以此时需要加入前驱哨兵。依赖后继节点的...

2020-03-28 07:53:28 175

原创剑指offer题23_从上往下打印二叉树

一.题目：从上往下打印二叉树的每个结点，同一层的节点按照从左到右的顺序打印。二.分析：通过STL中的deque实现（两端都可以进出的队列）三.答案：void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot) { if (!pTreeRoot) { return; } std::

2018-02-27 17:41:36 115

一.题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。二.分析：总结压入弹出规律：如果下一个弹出的数字刚好是栈顶元素，那么直接弹出；如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数都压入了栈仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。三.答案：bool IsPopO

2018-02-12 16:39:02 139

原创剑指offer题21_包含min函数的栈

一.题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min，push及pop的时间复杂度都是O(1)。二.分析：在面试时，很多应聘者都止步于添加一个变量保存最小元素的思路。其实只要举个例子多做几次入栈，出栈的操作就能看出问题，并能想到最小元素用另外的辅助栈保存。三.答案：template <template T> void StackWithMin<T>:

2018-02-08 17:01:37 136

原创剑指offer题20_顺时针打印矩阵

一.题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。二.分析：当我们遇到一个复杂的问题，可以用图形来帮助我们思考。1.我们可以用一个循环来打印矩阵，每一次打印矩阵中的一个圈。2.下一步分析循环结束的条件。我们可以分析出，让循环继续的条件是column > startX * 2并且rows > startY * 2。三.答案：void printMatrixClockwisely(

2018-02-07 17:02:14 135

原创线程间同步机制02_互斥锁

一.定义：另一种用在多线程程序中的同步访问机制是使用互斥锁。它允许程序员锁住某个对象，使得每次只能有一个线程访问它。二.使用机制：1.pthread_mutex_init函数：（1）功能：初始化互斥量（2）原型：int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *

2018-02-05 19:08:48 176

原创剑指offer题19_二叉树的镜像

一.题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。二叉树结点的定义如下：struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};二.分析：需要尝试通过举例画图，然后可以总结出求一棵树镜像

2018-02-05 18:43:26 145

原创线程间同步机制01_信号量

一.定义：信号量是一个特殊类型的变量，它可以被增加或者减少，但对其的关键访问被保证是原子操作，即使在一个多线程程序中也是如此。我们将介绍一种最简单的信号量——二进制信号量，它只有0和1两种值。还有一种更通用的信号量——计数信号量，他可以有更大的取值范围。二.信号量使用机制：1.sem_init函数：（1）功能：这个函数初始化由sem指向的信号量对象，设置它的共享选项，并给它一个初始的整数值。

2018-02-03 18:20:17 217

原创剑指offer题18_树的子结构

一.题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树的子结构如下：struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;}二.分析：我们可以分成两步：1.第一步在树A中找到和树B的根结点的值一样

2018-02-03 17:26:12 130

原创进程间通信05_套接字

一.定义：套接字（socket）是一种通信机制，凭借这种机制，客户/服务器系统的开发工作既可以在本地单机上进行，也可以跨网络进行。套接字的创建和使用与管道是有区别的，因为套接字明确地将客户和服务器区分开来。套接字机制可以实现多个客户连接到一个服务器。二.套接字属性：套接字的特性由是三个属性确定，它们是：1.域（domain）：指定套接字通信中使用的网络介质。（1

2018-02-02 19:19:17 312

原创剑指offer题17_合并两个排序的链表

一.题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。链表结点定义如下：struct ListNode { int m_nValue; ListNode* m_pNext;};二.分析：1.当我们得到两个链表中的值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，因此合并的步骤和之前步骤是一样的。这就是典

2018-02-02 18:12:08 141

原创进程间通信机制04_消息队列

一.定义：消息队列与命名管道有许多类似之处，但少了在打开和关闭管道时的复杂性。但使用消息队列并未解决我们在使用命名管道时遇到的问题，比如管道满时的阻塞问题。与命名管道相比，消息队列的优势在于，它独立于发送和接收进程而存在，这消除了在同步命名管道的打开和关闭时可能产生的一些困难。二.消息队列机制：1.msgget函数：（1）功能：创建和访问一个消息队列。（2）原型：

2018-02-01 19:09:50 346

原创剑指offer题16_反转链表

一.题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点，链表结点定义如下：typedef struct ListNode { int m_nValue; struct ListNode* m_pNext;} ListNode;二.分析：以这道题为例，我们至少应该想到几类测试用例对代码进行功能测试。 1.输入的链表头结点是

2018-02-01 18:20:28 106

原创进程间通信机制03_共享内存

一.定义：它允许两个不相关的进程访问同一段逻辑内存。共享内存是两个正在运行的进程之间传递数据的一种非常有效的方式。虽然X/Open标准并没有对它做出要求，但大多数共享内存的具体实现，都把由不同进程之间共享的内存安排为同一段物理内存。二.共享内存使用机制：1.shmget函数：（1）定义：通过shmget函数来创建共享内存。（2）原型：int shmget(key_t

2018-01-31 19:14:37 232

原创剑指offer题15_链表中倒数第k个结点

一.题目：输入一个链表，输出该链表中倒数第k个结点。链表定义如下：typedef struct ListNode { int m_nValue; struct ListNode* m_pNext;} ListNode;二.分析：功能之外还需要考虑代码的鲁棒性，其中考虑如下三点：1.若输入的头指针为空指针，不能引起程序崩溃。 2.若输入的链表的结点总数小于k，

2018-01-31 17:55:56 131

原创进程间通信机制02_管道

一.管道的定义：当从一个进程连接数据流到另一个进程时，我们使用术语“管道”。我们通常是把一个进程的输出管道连接到另一个进程的输入。二.管道的分类及特点：1.匿名管道：（1）它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。（2）它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。（3）它可以看成是一种特殊的文件，对于它的读写也可以

2018-01-30 14:40:28 186

原创剑指offer题14_调整数组顺序使奇数位于偶数前面

一.题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。二.分析：只完成基本功能的解法，仅适用于初级程序员，需要考虑可扩展性的方法才行，我们需要把整个函数解耦成两部分：一个是判断数字应该在数组前半部分还是后半部分；二是拆分数组的操作。三.答案：#include <stdio.h>bool isEven(int n) {

2018-01-29 16:36:21 113

原创进程间通信机制01_信号量

一.信号量的定义：它是一个特殊变量，只允许对它进行等待（wait）和发送信号（signal）这两种操作。最简单的信号量是只能取值0和1的变量，即二进制信号量。可以取多个正整数值的信号量被称为通用信号量。二.linux信号量机制：1.semget函数：（1）原型：int semget(key_t key, int num_sems, int sem_flags);（2

2018-01-26 19:32:22 276

原创剑指offer题13_在O(1)时间内删除链表结点

一.题目：给定单向链表的头指针和一个结点指针，给定一个函数在O(1)时间删除该结点。链表结点与函数定义如下：二.分析：共需考虑三种情况： 1.首先考虑的是并不是一定需要得到被删除结点的前一个结点，如果我们把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除即可。 2.如果需要删除的结点位于链表的尾部，那我们还是需要顺序遍历链表。 3.如果链表只有一个结点

2018-01-26 19:07:30 128

原创剑指offer题11_数值的整数次方

一.题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。二.分析：1.注意代码的规范性和完整性。（1）需要考虑指数是负数的情况；（2）需要考虑底数为0且指数为负数的情况；（3）考虑到0的0次方是没有意义的，结果为0或1均可。 2.乘方函数的实现上，可以底数循环乘法，但是效

2018-01-19 15:10:32 168

原创剑指offer题10_二进制中1的个数

一.题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成1001，有2位是1。因此如果输入9，该函数输出2。二.分析：1.可能引起死循环的解法：判断输入的整数最右一位是否为1，然后循环右移，但是问题是如果输入的整数是一个负数，那么循环右移就会变成死循环。 2.常规解法：将输入的整数不进行右移，而是将1进行循环左移进行判断。 3.能给面试官带来惊喜的解法：思

2018-01-18 16:52:06 114

原创剑指offer题9_斐波那契数列

一.题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契（Fibonacci）数列定义如下：二.分析：有三种解题方法： 1.基于递归的解法虽然直观，但时间效率很低，实际软件开发中不会用这种方法，也不可能得到面试官的青睐。 2.把递归的算法用循环实现，提高时间效率。 3.把求斐波那契数列转换成求矩阵的乘方，有创意，但不实用。三.答案：

2018-01-17 18:38:56 105

原创剑指offer题8_旋转数组的最小数字

一.题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5 }的一个旋转，该数组的最小值为1。二.分析：1.本题给出的数组在一定程度上是排序的，因此我们可以尝试着用二分查找法的思路来寻找这个最小的元素。 2.按照定义有一个特例：如果把排序数组的前面的0个元

2018-01-16 19:13:57 102

原创剑指offer题7_用两个栈实现队列

一.题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和队列头部删除结点的功能。template <typename T> class CQueue{public: CQueue(void); ~CQueue(void); void appendTail(const T& node);

2018-01-13 13:57:30 96

原创剑指offer题6_重建二叉树

一.题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出该二叉树并输出它的头结点。二叉树结点的定义如下： struct BinaryTreeNode { int m_nValue;

2018-01-12 11:05:09 125

原创剑指offer题5_从头到尾打印链表

一.题目：输入一个链表的头文件，从尾到头反过来打印出每个节点的值。链表节点定义如下：struct ListNode { int m_nValue; struct ListNode *m_pNext;};二.分析：可从两种思路来解决： 1.迭代 + 栈； 2.递归。三.答案：1.迭代 + 栈：void printLis

2018-01-09 19:29:18 138

原创剑指offer题4_替换空格

一.题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy”，则输出“We%20are%20happy”。二.分析：1.需要向面试官问清楚，是需要在原来字符串上做替换，还是创建新的字符串。若在原来字符串需要保证充足的内存空间。 2.假如是在原来字符串上做替换，思路是从字符串的后面开始复制和替换，需要准备两个指针。规律是，合并两个数组（包括字

2018-01-05 19:35:08 123

原创剑指offer题3_二维数组的查找

一.题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数。二.分析：1.可以从左下角或者右上角进行查询，这样可以保证每一次查询排除一行或者一列。 2.设计完算法，一定要准备测试用例，走一遍，才能确保正确。（1）功能测试（2）特殊输入测试三.答案：

2018-01-04 19:01:16 124

原创剑指offer题1_赋值运算符函数

一.题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数。class CMyString {public: CMyString(char* pData = NULL); CMyString(const CMyString& str); ~CMyString(void);private: char* m_pData;}二.分析：1.是否返回值的类

2018-01-03 19:16:41 292

原创 PX4源码分析8_PX4的sensor校准

一.综述：sensor的校准过程分为两部分，首先需要先通过地面站进行校准设置，然后通过校准数据的更新来获取最新的校准数据。1.校准数据的设置：commander（地面站）经过计算之后通过param_set()来设置校准数据，路径为src/modules/commander下的各个calibration文件，上电后rcS脚本执行sensors start之后会执行commder start来启动com

2017-09-10 16:22:49 3303

原创 PX4源码分析7_添加mavlink自定义消息

一.自定义mavlink消息：根据uorb消息（.msg）自定义mavlink消息。方法为利用mavlink_generator工具在xml文件生成mavlink所需相应的头文件。二.发送自定义mavlink消息：1.添加mavlink相应的头文件和和uorb相应的消息到 mavlink_messages.cpp。 2. 在mavlink_messages.cpp中创建一个新的类，并实现s

2017-08-07 20:04:10 1547

原创 PX4源码分析6_uorb通信机制

一.创建流程：在Firmware/msg下创建msg文件，eg：xxx.msg，内容格式仿照原有msg文件在Firmware/msg/CMakeLists.txt中将对应的msg文件添加，内容格式仿照原有形式二.使用方式：发布端：公告： orb_advertise 发布： orb_publish接收端：订阅： orb_subscribe复制： orb_copy

2017-07-11 16:11:05 1320

原创 PX4源码分析5_PX4启动流程

PX4启动流程，分为4步：1.__start：上电之后程序入口为Firmware/NuttX/nuttx/arch/arm/src/stm32/stm32_start.c中的__start函数，负责stm32芯片的底层初始化，包括是时钟，GPIO等。 2.os_start：__start函数调用Firmware/NuttX/nuttx/sched/os_start.c中的os_start函数，负责

2017-06-29 13:44:04 3060

原创 PX4源码分析4_PX4软件结构

PX4自动驾驶仪软件可分为三大部分：实时操作系统、中间件和飞行控制栈。1.NuttX实时操作系统：提供POSIX-style的用户操作环境，进行底层的任务调度。2.PX4中间件：PX4中间件运行于操作系统之上，提供设备驱动和一个微对象请求代理（micro object request broker，uORB)用于驾驶仪上运行的单个任务之间的异步通信。我的理解是完全可以将它看成为一种进程间通信机制。3

2017-03-05 21:52:21 2239

原创 PX4源码分析3_pixhawk硬件结构

一.参考链接：thunder_fan的博客二.硬件结构：1. 处理器：32位 STM32F427 Cortex M4内核带FPU的主处理器主频168MHZ256KB RAM2MB Flash32位 STM32F103 失控保护协处理器2.传感器：ST的 L3GD20H 16位精度的陀螺仪ST的 LSM303D 14位加速度计和磁力计Invensense的MPU6000的三轴加速计

2017-02-19 15:56:50 2230

原创 PX4源码分析2_QGC地面站的下载和安装

一.基本信息：1.软件系统：Ubuntu 14.04 64bit2.安装包位置：https://www.qgroundcontrol.org/downloads二.下载安装过程：1：下载qgroundcontrol压缩包到官网下载www.qgroundcontrol.org/downloads，下载的压缩包名称是：qgroundcontrol.tar.bz2 。2：解压，按照其压缩的格式选择压

2017-02-11 17:35:00 6576 3

空空如也

空空如也