eriol
- 浏览: 400746 次
- 性别:
- 来自: 上海
-
最新评论
-
handong1587：
代码有一处错.query函数最后一行return的应该是:re ...
RMQ -
yuandong0828：
简洁的特别透彻细致，多谢，
虚函数、虚指针和虚表 -
adam_zs：
谢谢分享！
括号匹配问题 -
hongloumengyanzxw：
good[b][/b]
dup和dup2函数 -
chriszeng87：
最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种 ...
判断两个链表是否相交
文章列表
memcpy
声明：void *memcpy(void *dest, const void *src, size_t n)
返回值：返回指向dest的指针。
作用：memcpy()用来拷贝src所指的内存内容前n个字节到dest所指的内存地址上。与strcpy()不同的是，memcpy()会完整的复制n个字节，不会因为遇到字符串结束'\0'而结束。
memccpy
声明：void *memccpy(void *dest, const void *src, int c, size_t n);
返回值：返回指向src中值为c的下一个字节指针。返回值为0表示在src ...
页式内存管理
CPU的页式内存管理单元，负责把一个线性地址，最终翻译为一个物理地址。从管理和效率的角度出发，线性地址被分为以固定长度为单位的组，称为页(page)，例如一个32位的机器，线性地址最大可为4G，可以用4KB为一个页来划分，这页，整个线性地址就被划分为一个totall_page[2^20]的大数组，共有2的20个次方个页。这个大数组我们称之为页目录。目录中的每一个目录项，就是一个地址——对应的页的地址。
另一类“页”，我们称之为物理页，或者是页框、页桢的。是分页单元把所有的物理内存也划分为固定长度的管理单位，它的长度一般与内存页是一一对应的。
这里注意到，这个 ...
逻辑地址如何转换为线性地址
一个逻辑地址由两部份组成，段标识符: 段内偏移量。段标识符是由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节，最后两位涉及权限检查。如 ...
SYN Flood介绍
SYN Flood是当前最流行的DoS（拒绝服务攻击）与DDoS（分布式拒绝服务攻击）的方式之一，这是一种利用TCP协议缺陷，发送大量伪造的TCP连接请求，从而使得被攻击方资源耗尽（CPU满负荷或内存不足）的攻击方式。 ...
逻辑地址 (Logical Address)
是指由程序产生的与段相关的偏移地址部分。
例如，你在进行C语言指针编程中，可以读取指针变量本身值(&操作)，实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址，与绝对物理 ...
给定两个有序的数组，长度分别为m和n，求这两个数组中的第K个元素。
问题分析：
1. 把 A 平均分为前后两个部分，前部分有 x 个元素，后部分有 n-x 个元素（由于 A 是有序的，所以后一部分的所有元素都大于前一部分）。A[x] 为 A 的后一部分中的第一个元素。
2. 同理把 B 也平均分成前后两个部分，前部分有 y 个元素，后部分有 m-y 个元素。B[y] 是 B 的后一部分中的第一个元素。
3. 由于两个数组都是被平均分割的，所以可以近似地认为 x = n/2, y = m/2。这里不妨设 A[x] <= B[y]（如果 A[x] > ...
题目：
在一个迷宫中找距离最长的两个点。
迷宫可以看作是一个无根树，因此，这个问题等价与在一个树形图中找最远的两个节点，也叫做这个图的直径。
迷宫、树形图有个很好的特点：即任意两个节点之间的距离就是这两点之间的最短路径和最长路径，也可以说任意两个节点之间的距离一定的。
其算法为：
任选一点u为起点，对树进行BFS遍历，找出离u最远的点v。然后以v为起点，再进行BFS遍历，找出离v最远的点w。则v到w的路径长度即为树的直径。时间复杂度为O(n)。
原理：设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点。
证明：
如果u 是直径上的点，则v必然 ...
一般调用删除方法都是集合的方法，例如：
List list = new ArrayList();
list.add(...);
list.remove(...);
但是，如果在循环的过程中调用集合的remove()方法，就会导致循环出错，例如：
for(int i=0;i<list.size();i++){
list.remove(...);
}
由于List每次remove一个元素后，其后的元素都会向前移动，此时如果执行i++，则恰好跳过了后面的元素，所以导致了错误。
所以，如果你想在循环语句 ...
题目：已知一链表，每个节点除了有一个指向下一节点的指针外，还有一随机指针指向链表中的任意节点（可能为空，也有可能为自身），请复制一个链表，要求节点的顺序以及节点上的随机指针指向的节点位置和原链表一致。
这个题目有个很巧妙的解法，可以达到O(n)的效率，其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表，然后给复制链表中每个节点的随机指针复制，最后再打断链表恢复原样。
typedef struct Node {
int nData;
Node* pNext;
Node* pRandom;
} Node;
...
有一个有序的数组，将其中的元素都右移X位，这样将该数组变成了一个部分有序的数组。位置0到X以及X+1到n-1是有序的，但是array[X] > array[X+1]。array[X+1]为原先数组的最小值，我们称其为转折点。请找出该X+1。
解题思路：使用二分查找的方法来搜索X+1，时间复杂度为O(logn)。考虑只有一个元素和数组仍然保持有序的特殊情况。
public class BinarySearch {
private int[] array;
public int search(int t) {
int start = 0;
...
闭包(closure)是一个可调用的对象，它记录了一些信息，这些信息来自于创建它的作用域。通过这个定义，可以看出内部类是面向对象的闭包，因为它不仅包含外围类对象(创建内部类的作用域)的信息，还自动拥有一个指向此外围类对象的引用，在此作用域内，内部类有权操作所有的成员，包括private成员。
Java最引人争议的问题之一就是，人们认为Java应该包含某种类似指针的机制，以允许回调(callback)。通过回调，对象能够携带一些信息，这些信息允许它在稍后的某个时刻调用初始的对象。
如果回调是通过指针实现的，那么就只能寄希望于程序员不会误用该指针。然而，您应该已经了解到，Java更小心 ...
对于树的遍历操作，通常使用递归的方式写起来比较简单。但是偶尔也可以尝试一下非递归的写法。
public void preOrder(Node t) {
if (t == null)
return;
Stack<Node> stack = new Stack<Node>();
Stack<Node> remain = new Stack<Node>();
while (true) {
System.out.print((t.value + &quo ...
RMQ英文是Range Maximum(Minimum) Query，是用来求某个区间的最大值/最小值，通常用在查询次数比较大的区间最值问题中。
RMQ的原理是动态规划，利用了倍增的思想。我们用A[1...N]表示一组数，[Li,Ri]表示题目涉及到的查询区间。
设F[i,j]表示从A[i]到A[i + (2^j) - 1]这个范围的最大值，也就是以A[i]为起点的连续2^j个数的最大值。由于元素个数是2^j，可以均分为两部分，每部分有2^(j-1)个数。整个区间的最大值肯定是前半部分的最大值和后半部分最大值的较大者，满足动态规划的最优子结构。
则动归方程为：F[i, j] = max(F ...
求二叉树中任意两个节点的最近公共祖先也称为LCA问题（Lowest Common Ancestor）。
二叉查找树
如果该二叉树是二叉查找树，那么求解LCA十分简单。
基本思想为：从树根开始，该节点的值为t，如果t大于t1和t2，说明t1和t2都位于t的左侧，所以它们的共同祖先必定在t的左子树中，从t.left开始搜索；如果t小于t1和t2，说明t1和t2都位于t的右侧，那么从t.right开始搜索；如果t1<t< t2，说明t1和t2位于t的两侧，那么该节点t为公共祖先。
如果t1是t2的祖先，那么应该返回t1的父节点；同理，如果t2是t1的祖先， ...
Union的概念
“联合”是一种特殊的类，也是一种构造类型的数据结构。在一个“联合”内可以定义多种不同的数据类型， 一个被声明为该“联合”类型的变量中，允许装入该“联合”所定义的任何一种数据，这些数据共享同一段内存，已达到节省空间的目的（还有一个节省空间的类型：位域）。 这是一个非常特殊的地方，也是联合的特征。另外，同struct一样，联合默认访问权限也是公有的，并且，也具有成员函数。
Union和Struct的区别
“联合”与“结构”有一些相似之处。但两者有本质上的不同。在结构中各成员有各自的内存空间， 一个结构变量的总长度是各成员长度之和（空结构除外，同时不考虑 ...