- 二叉树的深度
题目：输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点一次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
分析：如果只有根节点，深度为1.如果只有左子树，那么树的深度是左子树深度+1；如果有左子树和右子树，则就是两者深度的最大值再加1.递归很容易实现。 Continue reading
Monthly Archives: August 2012
面试题—查找和排序
如果面试题要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，都可以尝试用二分查找算法。如果需要在O(1)时间内查找某一元素，则考虑哈希表结构，其缺点是需要额外的空间来实现。
- 旋转数组的最小数字（二分查找）
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1. Continue reading
面试题–数组和字符串
- 消除字符串中的重复字符
题目：不使用额外缓冲。注意：一两个变量使用OK的，但是复制整个数组就不行。
分析：如果不使用额外缓冲，则对每个字符串判断是否为重复字符，如果是重复字符跳过，非重复字符记录。O(n^2).
三个指针，tail指向未含重复字符的字符串的下一位，i做全遍历，j只遍历0-tail指向的已有统计字符。 Continue reading
面试题—栈和队列
- 包含min函数的栈
题目：定义栈的数据结构，在其中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push和pop的时间复杂度都是O(1)。
分析：使用一个辅助栈来存入当前栈的最小值，适当改进后不用重复插入辅助栈相同的数据。插入的值小于等于min，s2就push，弹出的值就是min，s2就pop。 Continue reading
面试题–链表
- 从尾到头输出链表
Question：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。
典型的后进先出，可以使用栈实现。 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
进程控制（笔记）
1.获取进程ID
每个进程都有一个唯一的正数进程ID(PID)。
#include <unistd.h> #include <sys/types.h> pid_t getpid(void); //返回进程ID pid_t getppid(void); //返回它的父进程ID
2.创建和终止进程
父进程通过fork函数创建一个新的运行子进程： Continue reading
Processes and Threads 入门
进程
进程是对正在运行程序的一个抽象。一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。从概念上说，每个进程拥有它自己的虚拟 CPU(实际真正的CPU在个进程之间来回切换)。各个进程有自己的内存空间、数据栈等，所以只能使用进程间通讯(interprocess communication,IPC)，而不能直接共享信息。
进程是系统进行资源分配和调度的一个独立单位。
多进程
最直观的就是一个个pid,官方的说法就：进程是程序在计算机上的一次执行活动。一次main函数执行就是一个进程。
linux下创建子进程的调用是fork()。fork的作用是根据一个现有的进程复制出一个新进程，原来的进程称为父进程，新进程称为子进程。 Continue reading