suanfa.txt

包括字符串反转

字符串反转
给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：
输入： 第一个字符串: "This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn"
子串: "zhuxinquan"
输出： "nc/moc.zhuxinquan.www//:ptth :etis esenihC s'zhuxinquan si sihT"
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：

#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//reverse the string 's1' except the substring 'token'.
const char* reverse(const char* s1, const char* token)
{
	assert(s1 && token);
	stack<char> stack1;
	const char* ptoken = token, *head = s1, *rear = s1;
	while (*head != '\0')
	{
		while(*head!= '\0' && *ptoken == *head)
		{
			ptoken++;
			head++;
		}
		if(*ptoken == '\0')//contain the token
		{
			const char* p;
			for(p=head-1;p>=rear;p--)
				stack1.push(*p);

			ptoken = token;
			rear = head;
		}
		else
		{
			stack1.push(*rear);
			head=++rear;
			ptoken = token;
		}
	}
	char * return_v = new char[strlen(s1)+1];
	int i=0;
	while(!stack1.empty())
	{
		return_v[i++] = stack1.top();
		stack1.pop();
	}
	return_v[i]='\0';
	return return_v;
}
int main(int argc, char* argv[])
{
	
	cout<<"This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn\n";
	cout<<reverse("This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn","zhuxinquan");
	return 0;
}
链表反转

单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {
     int data;
     linka* next;
};

void reverse(linka*& head)
{
     if(head ==NULL)
          return;
     linka*pre, *cur, *ne;
     pre=head;
     cur=head->next;
     while(cur)
     {
          ne = cur->next;
          cur->next = pre;
          pre = cur;
          cur = ne;
     }
     head->next = NULL;
     head = pre;
}

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*& head)
{
     if(p == NULL || p->next == NULL)
     {
          head=p;
          return p;
     }
     else
     {
          linka* tmp = reverse(p->next,head);
          tmp->next = p;
          return p;
     }
}
判断两个数组中是否存在相同的数字

给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：

bool findcommon(int a[],int size1,int b[],int size2)
{
     int i;
     for(i=0;i<size1;i++)
     {
          int start=0,end=size2-1,mid;
          while(start<=end)
          {
               mid=(start+end)/2;
               if(a[i]==b[mid])
                    return true;
               else if (a[i]<b[mid])
                    end=mid-1;
               else
                    start=mid+1;
          }
     }
     return false;
}

后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

bool findcommon2(int a[], int size1, int b[], int size2)
{
     int i=0,j=0;
     while(i<size1 && j<size2)
     {
          if(a[i]==b[j])
               return true;
          if(a[i]>b[j])
               j++;
          if(a[i]<b[j])
               i++;
     }
     return false;
}

判断链表是否存在环

问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5

这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link {
    int data;
    link* next;
};

bool IsLoop(link* head)
{
    link* p1=head, *p2 = head;
	if (head ==NULL || head->next ==NULL) {
		return false;
	}
    do{
        p1= p1->next;
        p2 = p2->next->next;
    } while(p2 && p2->next && p1!=p2);     
	if(p1 == p2)
		return true;
	else
		return false;
}

找出单向链表的中间结点
设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。

link* mid(link* head)
{
	link* p1,*p2;
	p1=p2=head;
	if(head==NULL || head->next==NULL)
		return head;
	do {
		p1=p1->next;
		p2=p2->next->next;
	} while(p2 && p2->next);
	return p1;
}
如何判断一棵二叉树是否是平衡二叉树
解决方案：
根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
首先编写一个计算二叉树深度的函数，利用递归实现。

template<typename T>
static int Depth(BSTreeNode<T>* pbs)
{
	if (pbs==NULL)
		return 0;
	else
	{
		int ld = Depth(pbs->left);
		int rd = Depth(pbs->right);
		return 1 + (ld >rd ? ld : rd);
	}
}

下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：

template<typename T>
static bool isBalance(BSTreeNode<T>* pbs)
{
	if (pbs==NULL) 
		return true;
	int dis = Depth(pbs->left) - Depth(pbs->right);
	if (dis>1 || dis<-1 )
		return false;
	else
		return isBalance(pbs->left) && isBalance(pbs->right);
}
strstr()的简单实现
strstr(s1,s2)是一个经常用的函数，他的作用就是在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。
下面是这个函数的一个简单实现：

static const char* _strstr(const char* s1, const char* s2)
{
     assert(s2 && s1);
     const char* p=s1, *r=s2;
     while(*p!='\0')
     {
          while(*p++==*r++);
          if(*r=='\0')
               return p;
          else
          {
               r=s2;
               p=++s1;
          }
     }
     return NULL;
}