九章算法答案(上)

1. 实现一个memcpy函数。

//memcpy需要考虑内存重叠问题,memmove不需要考虑
void* memcpy(const void* src,void* dst,size_t size)
{
    assert(src!=NULL && dst!=NULL);
    if(size==0)
        return src;
    char* tmp=src;
    if(dst<=src || (char*)dst>((char*)src+size))//from left to right
    {
        while(size--)
        {
            *(char*)dst++=*(char*)src++;
        }
    }
    else//from right to left
    {
        src+=size-1;
        dst+=size-1;
        while(size--)
        {
            *(char*)dst--=*(char*)src--;
        }
    }
    return (void*)tmp;
}

2. STL中vector的实现原理(衍生:Map/Set的实现原理)

vector即一个对象,含有start,end和finish成员变量,这三个成员变量共同管理着一个堆上的数组空间。start指向数组头,end指向有效元素的尾部,finish指向整个空间的尾部。可以向其中插入,删除,移动元素等。插入时,如果有足够的空余空间,则予以插入;否则开辟一块新的空间(长度是原来2倍),将所有元素移动过去,将以上三个指针指向新的空间并释放原有空间,然后再插入元素即可。

3. 给定N张扑克牌和一个随机函数,设计一个洗牌算法。

假设扑克牌有54张,存放在card数组中。我们要保证的是每张扑克牌被洗过一次后不会被再次洗牌。所以我们可以使变量i从1循环到54,每次从第i张牌到第54张牌中选取一张,与第i张交换。

代码如下:

void shuffle(int card[],size_t n)
{
    srand(time(NULL));//初始化随机数种子
    int i;
    int other;//另一张牌
    for(i=0;i<n;++i)
    {
        other=i+rand()%(n-i);
        std::swap(card[i],card[other]);
    }
}

4. 25匹马,5个跑道,最少比多少次能比出前3名?前5名?

先看选出前3的算法:
组别 第一名 第二名 第三名 第四名 第五名
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

此时A1为所有马中的第一名。同时,红色标注的马被淘汰,因为只能选出3匹,但他们明显进不了前三。

可以看出,选出前3匹马至少需要7场比赛。

选出前5的算法:
组别 第一名 第二名 第三名 第四名 第五名
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

此时A1为所有马中的第一名。同时,红色标注的马被淘汰,因为只能选出5匹,但他们明显进不了前五。

5.进程和线程有什么区别?

另一种答案:

进程和线程具有很多类似的性质,因此人们称线程为轻量级进程,也是CPU调度和分派的基本单元;而传统意义上的进程称为重量级进程,从现代的角度看,它就是指拥有一个线程的进程。如果进程有多个控制线程,它就能同时执行多个任务(并发/并行)。

下面主要从调度、并发性、系统开销、拥有资源等方面对进程和线程进行比较。

调度:在传统的操作系统中,CPU调度和分派的基本单位是进程。而在引入线程的系统中,则把线程作为CPU调度和分派的基本单位,进程则作为资源拥有的基本单位,从而使传统进程的两个属性分开,线程便能够轻装运行,这样可以显著地提高系统的并发性。同一进程中线程切换不会引起进程切换,从而避免了昂贵的系统调用开销。但是在由一个进程中的线程切换到另一个进程中的线程时,依然会引起进程切换。

并发性:在引入线程的操作系统中,不仅进程间可以并发执行,而且在一个进程中的多个线程之间也可以并发送执行,因而使操作系统具有更好的并发性,从而能够有效地使用系统资源和提高系统的吞吐量。例如一个未引入线程的单CPU系统中,若仅设置一个文件服务进程,当它由于某种原因被封锁时,便没有其他文件服务进程来提供服务。在引入线程的系统中,可以在一个文件服务系统中设置多个服务线程。当第一个线程等待是,文件服务进程中第二个线程可以继续运行;当第二个被封锁时,第三个可以继续执行,从而显著提高了文件服务的质量以及系统的吞吐量。

体统开销:不论是引入线程的操作系统,还是传统的操作系统,进程都是拥有系统资源的一个独立单位。一般地说,线程自己不拥有系统资源(也有一点必不可少的资源),但它可以穿访问所隶属进程的资源。亦即一个进程的代码段、数据段以及系统资源(如打开的文件,I/O设备等),可供同一进程的所有其他线程共享。

拥有资源:由于在创建或撤销进程时,系统都要为之分配或回收资源,如内存空间,I/O设备等。因此操作系统所付出的开销将显著大于在创建线程时的开销。类似地,在进行进程切换时,涉及到整个当前进程CPU环境的保存以及新调度进程CPU环境的加载。而线程切换时只需要保存和设置少量寄存器的内容,并不涉及存储器管理方面的操作。可见,进程切换的开销也远远大于线程切合的开销。此外,由于同一进程中多个线程具有相同的地址空间,致使它们之间同步和通信的实现也比较容易。在有的系统中,线程的切换、同步和通信都无需内核的干涉。

6. 100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数?

若内存足够,可将100亿个数进行排序,快排,堆排均可,取其中间数字即可。或者将其构建出一个AVL树或红黑树,取其顶部数字即可。

若内存不足,则可采取分而治之的方法,将100亿个数按其前5位分成32个桶,若还是不足以放入内存就继续分。统计每个桶中数字的个数,就可以知道中位数一定出现在那个桶中,因为桶是按照32位数的前5位分的,桶之间是排好序的。并且还可以知道中位数是这个桶中第几大的数。然后将这个桶中的数字排序即可。

1.请简述智能指针原理,并实现⼀个简单的智能指针。

智能指针即一个对象,可以用来管理其他对象动态分配出来的指针,并在该对象生命期结束时调用其析构函数来释放它。智能指针分为autoptr,scopedptr,sharedptr,weakptr,instrusiveptr,scopedarray,sharedarray等。其中sharedptr使用引用计数的原理。当初始化对象时,将引用计数设为1,增加引用时,对其加1,减少引用时减1.当引用计数减少到0时,自动调用它所管理对象的析构函数来释放该对象。

模拟实现shared_ptr:

template<typename T>
class Shared_ptr {
public:
Shared_ptr(T* ptr=NULL)
:_ptr(ptr)
{
if (_ptr == NULL)
_count = new int(0);
else
_count = new int(1);
}
Shared_ptr(const Shared_ptr<T>&amp; other)
{
_ptr = other._ptr;
_count = other._count;
(*_count)++;
}
Shared_ptr&amp; operator=(const Shared_ptr<T>&amp; other)
{
_release();
_ptr = other._ptr;
_count = other._count;
(*_count)++;
return *this;
}
T&amp; operator*()
{
return *_ptr;
}
T* operator->()
{
retrn _ptr;
}
~Shared_ptr()
{
_release();
}
protected:
void _release()
{
if (--*_count == 0)
{
delete _ptr;
delete _count;
_ptr == NULL;
}
}
private:
T* _ptr;
int* _count;
};

2. 如何处理循环引用问题?

当可能会发生循环引用时,只需要让循环的一方持有弱指针,即weak_ptr即可。

3. 请实现⼀个单例模式的类,要求线程安全。

我的实现:

template<typename T>
class singleton {
public:
T* GetInstance()
{
if (_ptr == NULL)//加锁是个很耗时的过程,先判断可以减少加锁的次数
{
_lock.lock();//加锁
if (_ptr == NULL)
_ptr = new T();
_lock.unlock();//解锁
}
return _ptr;
}
static void DelInstance()
{
_lock.lock();
if (_ptr != NULL)
{
delete _ptr;