Rock_N_Roll_-CSDN博客

转载 C++ 顺序容器基础知识总结

转载自：http://www.cnblogs.com/QG-whz/p/5152963.html正文0.前言本文简单地总结了STL的顺序容器的知识点。文中并不涉及具体的实现技巧，对于细节的东西也没有提及。一来不同的标准库有着不同的实现，二来关于具体实现《STL源码剖析》已经展示得全面细致。所以本文仅仅是对容器基础知识的归纳。至于容器提供的接口与使用实例，建议查取

2017-09-22 15:58:39 479

转载 c++继承中的内存布局

c++继承中的内存布局（转）今天在网上看到了一篇写得非常好的文章，是有关c++类继承内存布局的。看了之后获益良多，现在转在我自己的博客里面，作为以后复习之用。——谈VC++对象模型（美）简.格雷程化译译者前言一个C++程序员，想要进一步提升技术水平的话，应该多了解一些语言的语意细节。对于使用VC++的程序员来说，还应该了解一些VC++对于C++的

2017-09-22 10:43:57 498

前言最近刷到剑指offer 50题，树中两个结点的公共祖先，感觉这类题目对于不同性质的树会有不同的解法，而且也比较综合，在此就总结一下这类型的题目。树为二叉搜索树二叉搜索树的概念只要大家学过数据结构应该都是清楚的，也就是排序过的树。对于树上的每一个结点，其左子树的结点都小于父结点，其右子树的结点都大于父结点。那么我们解这道题的基本思想如下：1）从根结点开始遍历，让其分别和输入的两个结点做比较。 2

2017-09-05 10:16:24 554

原创数据结构-树的回顾

前言笔试当中经常会遇到关于二叉树或者其他关于树的数据结构相关的题，如最近在腾讯的笔试有一道题如下，一颗二叉树中有3个叶子结点，8个度为1的结点，求总结点的数。其实这道题很简单，如果知道在二叉树当中，只存在度为0，1，2这三种结点，且度为0的结点等于度为2的结点+1，即n0=n2+1,那这道题就是so easy了。所以基础知识在此时不言而喻，所以痛定思痛，本文总结一下有关树相关的知识点。树的一些基本概

2017-09-03 17:07:16 851

原创面试总结之拥塞控制与流量控制

前言：拥塞控制和流量控制分别是什么概念？流量控制的过程，分别解决什么问题？解答：首先需要明确这两个概念从手段上都是通过遏制发送方，但使用它们其实是出于不同的目的。流量控制应用在如下场景：一条TCP连接的双方主机都为该连接设置了接收缓存。当该TCP连接收到正确按序的字节后，它就将数据放入接受缓存。相关联的应用进程会从该缓存中读取数据，但不一定是立即去读数据，可能现在接收方应用正在忙于其他的服务。那么如

2017-09-02 11:13:54 1630

原创网易笔试题-疯狂的队列

题目小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,请计算出这些

2017-08-31 18:11:40 640

原创网易笔试题-堆棋子

题目小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.输入描述:输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数第二行为n个棋子的横坐标x[i

2017-08-31 18:07:50 1148

原创 LeetCode 66. Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.You may assume the integer do not contain any leading zero, except the number 0 itself.The digits are st

2017-08-28 11:39:16 226

原创 LeetCode 43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.Note:The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9.Bo

2017-08-28 11:21:27 219

原创 LeetCode 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it

2017-08-28 10:11:00 196

原创面试总结之守护进程，僵尸进程和孤儿进程

前言请说说你对守护进程，僵尸进程和孤儿进程的理解解答孤儿进程与僵尸进程：在linux当中，子进程是由父进程创建的，子进程再创建新的进程。子进程的结束和父进程的运行是一个异步的过程，即父进程永远无法预测子进程到底什么时候结束。unix系统提供了一种机制可以让父进程获得子进程结束时的状态信息，也就是说在每个进程退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存，但是仍然为其保留一定的信息,

2017-08-26 19:54:21 3086 1

原创从递归到动态规划的代码转换之道

前言昨天看了牛客网直播–左神的算法直播，讲了啊里巴巴的编程题，并由此展开，为我们讲了如何将暴力递归的代码一步一步转换成了动态规划的代码，简直妙哉！在这里我就利用自己有限的智商总结（抄袭）下如何将递归到动态规划的代码转换之道。转换之道直接上题讲解吧!一排有N个位置，一个机器人在最开始停留在P位置，如果P==0位置，下一分钟机器人一定向右移动到1位置；如果P==N-1，下一分钟机器人一定向左移动到N-

2017-08-24 16:00:50 793

原创数组中子数组等于k的最大长度

题目：假定有数组arr[4]={3,1,4,7}, 求出数组中子数组中等于12的最大长度。基本思想创建一个hash表，其key等于数组中遍历过的数的和，其value等于当前遍历的数在数组中的下标。用sum保存遍历过的数的总和，len保存最大长度；依次从数组的开头遍历，如果sum-k的值在hash表中有记录，则len更新为i-map[sum-k]和len的较大值，如果不存在就将{sum,i}加入map

2017-08-24 10:39:37 1070

原创面试总结之time_wait状态产生的原因，危害，如何避免

前言请说说你对TCP连接中time_wait状态的理解解答：先上TCP的状态变迁图1. time_wait状态如何产生？由上面的变迁图，首先调用close()发起主动关闭的一方，在发送最后一个ACK之后会进入time_wait的状态，也就说该发送方会保持2MSL时间之后才会回到初始状态。MSL值得是数据包在网络中的最大生存时间。产生这种结果使得这个TCP连接在2MSL连接等待期间，定义这个连接的

2017-08-23 19:54:15 66963 6

原创求数组中区间中最小数*区间所有数和的最大值

今日头条编程题第二道解答解法一：暴力解法穷举所有数组中所有子数组，并计算所有子数组中最小值*子数组所有数的和，求出其中的最大值即可，代码如下：int enum_method(vector<int> &num) { int n = num.size(); int maxSum = INT_MIN; vector<int> tmp; for (int i = 0; i<n

2017-08-23 17:06:27 8535 2

原创面试总结之select和epoll

前言是否用过 select、epoll，什么是IO多路复用，epoll 水平触发和边缘触发。解答IO多路复用IO多路复用是进程一种预先告知内核的能力，使得内核一旦发现进程指定的一个或多个IO条件就绪，它就通知进程。IO复用应用的场合：（1）当客户处理多个描述字时（一般是交互式输入和网络套接口），必须使用I/O复用。（2）当一个客户同时处理多个套接口时，而这种情况是可能的，但很少出现。（3）如果一个T

2017-08-21 12:12:16 3128 3

原创面试题总结之windows/linux内存管理

前言请说说你对windows/linux内存管理的认识解答内存管理的必要性出现在早期的计算机系统当中，程序是直接运行在物理内存中，每一个程序都能直接访问物理地址。如果这个系统只运行一个程序的话，并且这个程序所需的内存不要超过该机器的物理内存就不会出现问题。但是如今的系统都是支持多任务和多进程的，那么这时我们就要考虑如何将系统内有限的物理内存及时有效的分配给多个程序了，这就是内存管理的基本概念。顾名思

2017-08-20 23:09:48 5293

原创面试题总结之快速排序

前言你说你熟悉常用的数据结构和算法，谈谈快速排序算法吧。解答首先先给出快速排序的基本思想：（1）先从数列中选择一个数作为基准数（2）将序列分成两个区间，小于步骤（1）基准数的放在左区间，大于基准数的放在右区间。（3）对步骤（2）分出的左右区间重复第二步，直到各区间只有一个数。（递归）代码如下：class QuickSort {public: int* quickSort(int

2017-08-20 10:19:04 10002

原创面试题总结之程序编译过程

前言请讲一下linux如何源文件逐步编译成可执行文件。解答首先先上图对编译的整个过程有个感性的认识，然后再逐步分析各个过程。以hello.c 程序为例# include <stdio.h>main{ printf("hello\n");}一个.c源程序需要经过预处理器生成.i文件，再经过编译器生成.s文件，再经过汇编器生成可重定位目标文件.o文件，再与其他.o文件经过链接器生成最终的

2017-08-19 23:59:47 4098

原创面试题总结之TCP报头

前言听说你熟悉TCP/IP协议，请讲下TCP的报头。解答TCP报文一般有20个字节。 1.16位的源端口号加上16位的目的端口号，这两个值加上IP首部中的源端IP地址和目的端IP地址，用于多路复用或多路分解来自或送至上层应用的数据。 2. 32位的序列号，其用来标识从TCP发送方向TCP接收端发送的数据字节流，它表示该报文段首字节的字节流编号。 3. 32位的确认序号标识发送确认一段所期望收到

2017-08-19 23:44:15 877

原创单链表判环判相交综合题

题目给定两个单链表的头节点head1和head2，单链表可能有环，也可能无环。如何判断两个链表是否相交？相交的话返回相交的第一个节点，不想交的话返回NULL。要求：如果链表1的长度为N，链表2的长度为M，时间复杂度O（N+M）,额外空间复杂度O（1）。分析：首先我们先判定两个链表是否有环，如果只有其中一个链表有环，一个链表无环，那证明这两个链表不会相交。然后再分成都有环和无环情况分别分析。都无环

2017-08-17 21:13:50 290 1

原创滑动窗口变形题-最大值减去最小值小于等于num的子数组

题目：基本思想：解法1:最先想到的方法是遍历所有的子数组，然后对每一个子数组分别求出最大值和最小值，然后判断两者之差是否小于num即可。代码如下：int getNumEnum(vector<int> arr,int num){ if(arr.empty()) return 0; int res; vector<int> tmp; for(int i

2017-08-17 16:28:06 959

原创求最大子矩阵的大小（Maximal Rectangle）

题目：Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.For example, given the following matrix:1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0R

2017-08-16 23:53:58 6482

原创数据对齐那些事

前言目前的操作系统主要有32位和64位，也就是说机器字长是32位和64位。在计算硬件底层，CPU是按一个传送单位（32/64位）进行存取，而且是按字节进行编址。数据对齐指的是计算机系统对基本数据类型合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K（2，4，8）的倍数。为什么要进行对数据对齐，我们可以看看下面的例子：假设在一个32位的系统中，有int i; short k; doubl

2017-08-14 22:44:05 5367

原创二叉树的深度以及判断二叉树是否为平衡二叉树

二叉树的深度题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。基本思想：我们假定Tree的节点个数为GetTreeNodeNum()，其左子树为LeftTree，右子树为RightTree。那么求Tree的深度有以下几种情况：GetTreeNodeNum()==1&&LeftTree==NULL&&RightTre

2017-08-10 16:53:30 296

原创连续子数组的最大和及其拓展

题目输入一个整形数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）.基本思想：利用动态规划求解，递归公式如下，其中f(i)表示以第i个数字结尾的子数组的最大和。公式意义如下：如果当以第i-1个数字结尾的子数组中所有数字的和小于0，则如果把这个负数与第i个数累加，则得到的结果比第i个数本身还要小，那么这时应该更新f(i)为第i个数字

2017-08-10 11:12:19 237

原创从1到n整数中1出现的次数

题目：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。解法一：暴力解法：遍历从1到n的整数，判断每个整数1的个数，再相加。时间复杂度为O（n*logn）。int N

2017-08-08 11:25:54 279

原创复制链表的复制

题目：/*struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { }};*/输入一个复杂链表（每个节点中有节点值，以及两个指针，

2017-08-05 23:03:39 651

原创深入理解计算机系统之数据的表示与存储

前言在编写程序的时候，不同数据类型进行转换和计算的时候总是可能出现各种各样奇怪的bug,所以深入的了解计算机系统中数据的表示与存储有利于我们编写高效与健壮的计算机程序，本文主要总结计算机系统中整数，浮点数的表示和存储。真值与补码的相互转换真值指的就是现实当中的正负数，而补码是计算机中表示真值的一种编码方式，也就是0/1编码的序列。补码与真值的关系如下：　其中n表示机器的字长，X是真值。求真值的补

2017-08-02 18:10:22 1860

原创顺时针打印矩阵

前言最近在刷剑指offer，碰到一道题如下：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.剑指offer里的解法比较难懂，但看了牛客网有人对这题的解法我觉得很棒，特此在这里分享一

2017-08-01 21:39:52 165

原创数字追赶--搜狐笔试题

题目如下：//下面的for循环分别循环了几次。1.unsigned short i,j;for(i=0, j=2; i!=j; i+=5, j+=7){}2.unsigned short i,j;for(i=3,j=7;i!=j;i+=3,j+=7){}分析：题目1：unsigned short 可以表示为2的16次方个数，其数的范围为0到2的16次方-1，在题目1中，j比i大2，

2017-07-31 17:33:39 222

原创二进制中1的个数及其拓展

前言判断二进制中1的个数可以变形出很多道算法题，本文主要是总结位运算还有相关位运算的算法题。左移和右移对于m<<n，左移运算符对于正负数都是将最左边的n位丢弃，同时在最右边补上n个0。如：00010101<<2 = 01010100。而对于右移运算符，需要考虑二进制数的有无符号性。如果数字是一个无符号数，那么就用0填补最左边的n位。如果数字是一个有符号数，那么就用数字的符号位填补最左边的n位

2017-07-26 11:18:27 477

原创由重建二叉树算法题到临时对象不能绑定到非 const 的左值引用

前言最近再刷剑指offer,在将一个临时变量传给一个引用的时候，出现了non-const lvalue reference to type 'vector<[...]>' cannot bind to a temporary of type 'vector<[...]>'的错误，意思就是不能将临时对象绑定到非const的左值的引用，那么在这里就总结一下这道算法题，const引用的用法。const总结

2017-07-25 20:13:15 874

原创深入理解虚函数

前言在C++中，在基类中被声明为virtual并在在一个或多个派生类中被重新定义的成员函数就是虚函数。基本格式如下：virtual (return_type) (func_name) (arg) {function body;}我们可以通过指向派生类的基类指针或引用来调用派生类中同名覆盖的成员函数。如下代码：class A{ public: virtual void pri

2017-07-20 12:40:00 284

原创深入理解extern "C" 的使用

前言最近用到了动态库的函数dlsym函数，其作用是返回指定符号函数的地址。详见深入理解Linux动态库和静态库http://blog.csdn.net/u013616945/article/details/75151418但由于动态库文件是C++写的，如果函数不加extern “C” 符号的话，在编译的时候回提示找不到dlsym函数指定符号的函数。下面就总结extern “C”的使用。C++

2017-07-18 21:28:23 2178

原创链表中环的入口结点

题目：一个链表中包含环，请找出该链表的环的入口结点。解法一：定义指针P1和P2指向链表的头结点。假设链表中的环有n个结点，指针P1先在链表走n步，然后两个指针已相同的速度前进。因为P1总是比P2多走n个结点，但进入环之后，当两个指针相遇时，则为环的入口结点。代码如下：class Solution {public: ListNode* EntryNodeOfLoop(ListNode*

2017-07-18 18:38:12 272

原创删除链表的重复结点

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。方法一：从头遍历整个链表，如果当前节点与下一个节点值相同，那么就把两个节点删除。为了不使链表断开，需要另外一个节点指向当前遍历节点的上一个节点（preNode），把preNode与后面不重复的第一个节点相连。代码如下：

2017-07-18 11:53:17 713

原创深入理解Linux静态库与动态库

前言最近在写一个小型的http服务器，为了能够提供网页的动态内容，开始接触linux静态库和动态库的概念。之后又看了《深入理解计算机系统》的第七章–链接，在此对于linux静态库和动态库做一个总结。为什么需要库定义程序一般需要经过预处理，编译，汇编和链接将我们编写ASII文本程序变成可执行的目标文件（.out）。然而在实际开发中，有许多模块是反复复用的，如printf函数，scanf函数等，故所有的

2017-07-15 12:20:41 618

原创 realloc函数用法

函数原型：void *realloc(void *ptr, size_t size);功能：重新分配大小为size的一块内存，返回内存地址ptr。函数源码流程图：使用方法：/* realloc example: rememb-o-matic */#include <stdio.h> /* printf, scanf, puts */#include <stdlib.h> /

2017-07-14 20:45:20 951

转载 C语言中巧用正则表达式 regex_t

标准的C和C++都不支持正则表达式，但有一些函数库可以辅助C/C++程序员完成这一功能，其中最著名的当数Philip Hazel的Perl-Compatible Regular Expression库，许多Linux发行版本都带有这个函数库。C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror()，一般分为三个步骤，如下所示：C语言中使用正则表

2017-07-13 19:54:20 425

mars第一季到第五季源码

空空如也