eriol
- 浏览: 400763 次
- 性别:
- 来自: 上海
-
最新评论
-
handong1587：
代码有一处错.query函数最后一行return的应该是:re ...
RMQ -
yuandong0828：
简洁的特别透彻细致，多谢，
虚函数、虚指针和虚表 -
adam_zs：
谢谢分享！
括号匹配问题 -
hongloumengyanzxw：
good[b][/b]
dup和dup2函数 -
chriszeng87：
最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种 ...
判断两个链表是否相交
文章列表
Write Through (完全写入)
CPU向cache写入数据时，同时向memory也写一份，使cache和memory的数据保持一致。优点是简单，缺点是每次都要访问memory，速度比较慢。
Write Back (回写)
CPU更新cache时，只是把更新的cache区标记一下，并不同步更新memory。只是在cache区要被新进入的数据取代时，才更新 memory。这样做的原因是考虑到很多时候cache存入的是中间结果，没有必要同步更新memory。优点是CPU执行的效率提高，缺点是实现起来技术比较复杂。
区别
完全写入（W ...
通常情况下core dump包含了程序运行时的内存，寄存器状态，堆栈指针，内存管理信息等。可以理解为把程序工作的当前状态存储成一个文件。许多程序和操作系统出错时会自动生成一个core文件。
core dump又叫核心转储，当程序运行过程中发生异常，程序异常退出时，由操作系统把程序当前的内存状况存储在一个core文件中。
如何使用core文件?
gdb -c core文件路径 [应用程序的路径]
进去后输入where回车，就可以显示程序在哪一行当掉的，在哪个函数中。
coredump可以用在很多场合，使用Linux,或者solaris的人可能都有过 ...
1. x86实模式介绍
x86体系的处理器刚开始时只有20根地址线，寻址寄存器是16位。我们知道16位的寄存器可以访问64K的地址空间，如果程序要想访问大于64K的内存，就需要把内存分段，每段64K，用段地址+偏移量的方式来访问，这样使20根地址线全用上，最大的寻址空间就可以到1M字节，这在当时已经是非常大的内存空间了。
2. 实模式的问题与保护模式的出现
事实上，实模式将整个物理内存看成分段的区域，程序代码和数据位于不同区域，系统程序和用户程序并没有区别对待，而且每一个指针都是指向实际的物理地址。这样一来，用户程序的一个指针如果指向了系统程序区域或其他用户程序区域，并修改了 ...
题目 ：
给出两个链表的头指针，比如h1，h2，判断这两个链表是否相交。
扩展：
(1) 如果链表可能有环呢？ (2) 如何求出两个相交链表的相交的第一个节点。
如果链表没有环
假设两个链表没有环，如果它们相交，那么它们的最后一个元素必定相同。
public boolean isConNLoop(ListNode h1, ListNode h2) {
if (h1 == null || h2 == null)
return false;
ListNode n1 = h1;
ListNode n2 = h2;
while (n ...
有些时候，我们需要从一个方法中返回多个值。那么在Java中该怎么实现呢？
在Java中，你无法控制参数传递的方式，Java中所有的参数传递都是按值传递：
简单类型，将参数的值传递给函数；
对象类型，将参数的地址传递给函数。
正因为传递对象类型参数时，你传递的是对象的地址，或者叫引用（reference），这时函数就可以改变该地址上的那个对象。所以，如果你要修改某个地址上的值（或者说，要向这个地址返回一个值），那么将它按对象类型传递都可以了。但需要注意的是，Java不能让这个传递给函数的参数指向另一个地址，原因是，参数的地址是复制给函数中的局部变量的，函数一结束， ...
题目：输入一个正数n，输出所有和为n连续正整数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
解法1
因为整数序列是有序的，可以设立两个游标begin和end，通过判区间[begin,end]的和是否为N来得到这个序列。如果区间和大于n，begin往前移动，如果小于n，end往前移动，等于就输出这个区间。时间复杂度是0(n)。
public void find(int n) {
if (n > 0 && ((n & n-1) ...
作为通常的原则，如果一个类定义了虚函数，那么它的析构函数就应当是virtual的。因为定义了虚函数则隐含着：这个类会被继承，并且会通过基类的指针指向子类对象，从而得到多态性。这个类可能会被继承，并且会通过基类 ...
dup和dup2也是两个非常有用的调用，它们的作用都是用来复制一个文件的描述符。它们经常用来重定向进程的stdin、stdout和stderr。这两个函数的原形如下：
#include <unistd.h>
int dup( int oldfd );
int dup2( int oldfd, int targetfd );
...
循环引用
引用计数是一种便利的内存管理机制，但它有一个很大的缺点，那就是不能管理循环引用的对象。一个简单的例子如下：
#include <string>
#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
class parent;
class children;
typedef boost::shared_ptr<parent> parent_ptr;
typedef b ...
最近项目中使用boost库的智能指针，感觉智能指针还是蛮强大的，在此贴出自己学习过程中编写的测试代码，以供其他想了解boost智能指针的朋友参考，有讲得不正确之处欢迎指出讨论。当然，使用boost智能指针首先要编译boost库，具体方法可以网上查询，在此不再赘述。
智能指针能够使C++的开发简单化，主要是它能够自动管理内存的释放，而且能够做更多的事情，即使用智能指针，则可以再代码中new了之后不用delete，智能指针自己会帮助你管理内存资源的释放。
Boost库的智能指针有很多种，下面通过示例代码来说明其中shared_ptr的使用方法。
// test ...
当类中有指针成员时，一般有两种方式来管理指针成员：一是采用值型的方式管理，每个类对象都保留一份指针指向的对象的拷贝；另一种更优雅的方式是使用智能指针，从而实现指针指向的对象的共享。
智能指针(smart pointer)的一种通用实现技术是使用引用计数(reference count)。智能指针类将一个计数器与类指向的对象相关联，引用计数跟踪该类有多少个对象共享同一指针。
每次创建类的新对象时，初始化指针并将引用计数置为1；当对象作为另一对象的副本而创建时，拷贝构造函数拷贝指针并增加与之相应的引用计数；对一个对象进行赋值时，赋值操作符减少左操作数所指对象的 ...
1. 概述
并查集（Disjoint set或者Union-find set）是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
2. 基本操作
并查集是一种非常简单的数据结构，它主要涉及两个基本操作，分别为：
合并 ...
在多道程序系统中，同时有多个进程并发运行，共享系统资源，从而提高了系统资源利用率，提高了系统的处理能力。但是，若对资源的管理、分配和使用不当，则会产生死锁或是饥饿。
所谓死锁是指在多道程序系统中，一组进程中的每一个进程都无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。
饥饿是指系统不能保证某个进程的等待时间上界，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。
下面我们就来分别讨论一下死锁与饥饿各自的特点。
死锁
产生死锁的原 ...
回调函数(callback)与仿函数(functor)很多时候从用途上来看很相似，以致于我们经常将它们相提并论。例如：
inline bool compare(int a, int b)
{
return a > b;
}
struct comparer {
bool operator()(int a, int b) const {
return a > b;
}
};
void main()
{
std::vector<int> vec, vec2;
std::sort(vec.begin( ...
引入
平常，我们用堆最常见的就是随机地加入元素，随机地取最大值或最小值。这些基本的操作C++中的priority_queue和set都能很好的完成，而且C++中还有一个make_heap，效率较前面2个会更高。而且前面提到的STL都是采用红黑树实现的，很具有稳定性。
上面的堆虽然使用简单，但功能上还是有些局限。比如前面提到的堆都只能实现删除最值并没有办法删除指定的值。而且一般STL中的堆都是采用数据存储的，但父亲节点和儿子节点需要交换时，我们需要拷贝所存储的整个数据单元，但数据单元较大时，拷贝的效率就低了。因此，这里介绍一中堆变种，在堆中引入了映射。
定义 ...