Sort Index

插入类排序:

插入排序       最好O(n)   最坏O(n^2)   空间O(1)
*希尔排序     最好O(n^1.3)   最坏O(n^2)   空间O(1)

选择类排序:

*选择排序    最好O(n^2)   最坏O(n^2)   空间O(1)
*堆排序        最好O(nlogn)   最坏O(nlogn)   空间O(1)

交换类排序:

冒泡排序     最好O(n)   最坏O(n^2)   空间O(1)
*快速排序     最好O(nlogn)   最坏O(n^2)   空间O(logn)~O(n)

归并类排序:

归并排序     最好O(nlogn)   最坏O(nlogn)   空间O(n)

非基于比较的排序:

基数排序
桶排序
计数排序

带*号为不稳定排序
从最好情况看,冒泡和直接插入排序更好;
从最坏情况看,堆排序和归并又强过快速排序和其他简单排序;
从稳定性看,归并排序好;
从空间看,堆排序O(1),若对内存使用量在乎,归并和快排就不太好。

 

面试题—树

  1. 二叉树的深度
    题目:输入一颗二叉树的根节点,求该树的深度。从根节点到叶节点一次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
    分析:如果只有根节点,深度为1.如果只有左子树,那么树的深度是左子树深度+1;如果有左子树和右子树,则就是两者深度的最大值再加1.递归很容易实现。 Continue reading

面试题—查找和排序

如果面试题要求在排序的数组(或者部分排序的数组)中查找一个数字或者统计某个数字出现的次数,都可以尝试用二分查找算法。如果需要在O(1)时间内查找某一元素,则考虑哈希表结构,其缺点是需要额外的空间来实现。

  1. 旋转数组的最小数字(二分查找)
    题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. Continue reading

面试题–数组和字符串

  1. 消除字符串中的重复字符
    题目:不使用额外缓冲。注意:一两个变量使用OK的,但是复制整个数组就不行。
    分析:如果不使用额外缓冲,则对每个字符串判断是否为重复字符,如果是重复字符跳过,非重复字符记录。O(n^2).
    三个指针,tail指向未含重复字符的字符串的下一位,i做全遍历,j只遍历0-tail指向的已有统计字符。 Continue reading

面试题—栈和队列

  1. 包含min函数的栈
    题目:定义栈的数据结构,在其中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push和pop的时间复杂度都是O(1)。
    分析:使用一个辅助栈来存入当前栈的最小值,适当改进后不用重复插入辅助栈相同的数据。插入的值小于等于min,s2就push,弹出的值就是min,s2就pop。 Continue reading

memset,memcpy,strcpy

strcpy

char *strcpy( char *dest, const char *src );

dest-pointer to the byte string to copy to
src-pointer to the null-terminated byte string to copy from

Copies the byte string pointed to by src to byte string pointed to by dest.If the strings overlap, the behavior is undefined.

ps.src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串,返回指向dest的指针。strcpy 就只能拷贝字符串,它遇到’\0’就结束拷贝,不会拷贝’\0’。例如: Continue reading

构造和析构函数浅析

一题简单的构造、析构函数题

#include <iostream>
using namespace std;

struct BaseClass
{
	char ch;
	BaseClass():ch('a') {cout<<ch<<"1";}
	~BaseClass()		{cout<<ch<<"2";}
};

struct MyClass:public BaseClass
{
	MyClass()			{cout<<ch<<"3";}
	~MyClass()			{cout<<ch<<"4";}
};

int main(void)
{
	MyClass x1;
	x1.ch='b';
	MyClass x2;
	x2.ch='c';
	return 0;
}

——出自人人网2011实习生招聘试题

输出结果:a1a3a1a3c4c2b4b2

构造函数(Constructor)由编译器在定义对象时调用,传递到构造函数的第一个参数是this指针,也就是调用这一函数的对象的地址,但是该this指针指向一个没有被初始化的内存块,构造函数的作用就是正确的初始化该内存块。
析构函数(Destructor )在当对象超出它的作用域时由编译器自动调用。析构函数不需要任何参数。 Continue reading

Processes and Threads 入门

进程

进程是对正在运行程序的一个抽象。一个进程就是一个正在执行程序的实例,包括程序计数器、寄存器和变量的当前值。从概念上说,每个进程拥有它自己的虚拟 CPU(实际真正的CPU在个进程之间来回切换)。各个进程有自己的内存空间、数据栈等,所以只能使用进程间通讯(interprocess communication,IPC),而不能直接共享信息。
进程是系统进行资源分配和调度的一个独立单位。

多进程

最直观的就是一个个pid,官方的说法就:进程是程序在计算机上的一次执行活动。一次main函数执行就是一个进程。
linux下创建子进程的调用是fork()。fork的作用是根据一个现有的进程复制出一个新进程,原来的进程称为父进程,新进程称为子进程。 Continue reading