判断链表是否存在环型链表问题
判断一个链表是否存在环例如下面这个链表就存在一个环
例如N>N>N>N>N>N就是一个有环的链表环的开始结点是N这里有一个比较简单的解法
设置两个指针pp每次循环p向前走一步p向前走两步直到p碰到NULL指针或者两个指针相等结束循环如果两个指针相等则说明存在环
struct link
{
int data;
link* next;
};
bool IsLoop(link* head)
{
link* p=head *p = head;
if (head ==NULL || head>next ==NULL)
{
return false;
}
do{
p= p>next;
p = p>next>next;
} while(p &#;&#; p>next &#;&#; p!=p);
if(p == p)
return true;
else
return false;
}
链表反转的问题
单向链表的反转是一个经常被问到的一个面试题也是一个非常基础的问题
例如一个链表是这样的 >>>> 通过反转后成为>>>>最容易想到的方法遍历一遍链表利用一个辅助指针存储遍历过程中当前指针指向的下一个元素然后将当前节点元素的指针反转后利用已经存储的指针往后面继续遍历源代码如下
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* plinka*&#; head)
{
if(p == NULL || p>next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p>nexthead);
tmp>next = p;
return p;
}
}
判断两个数组中是否存在相同的数字的问题
给定两个排好序的数组怎样高效得判断这两个数组中存在相同的数字？
这个问题首先想到的是一个O(nlogn)的算法就是任意挑选一个数组遍历这个数组的所有元素遍历过程中在另一个数组中对第一个数组中的每个元素进行binary search用C++实现代码如下
bool findcommon(int a[]int sizeint b[]int size)
{
int i;
for(i=;i;i++)
{
int start=end=sizemid;
while(start<=end)
{
mid=(start+end)/;
if(a[i]==b[mid])
return true;
else if (a[i] end=mid;
else
start=mid+;
}
}
return false;
}
后来发现有一个 O(n)算法因为两个数组都是排好序的所以只要一次遍历就行了首先设两个下标分别初始化为两个数组的起始地址依次向前推进推进的规则是比较两个数组中的数字小的那个数组的下标向前推进一步直到任何一个数组的下标到达数组末尾时如果这时还没碰到相同的数字说明数组中没有相同的数字
bool findcommon(int a[] int size int b[] int size)
{
int i=j=;
while(i &#;&#; j)
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
j++;
if(a[i] i++;
}
return false;
}
最大子序列问题
给定一整数序列A A An （可能有负数）求A~An的一个子序列Ai~Aj使得Ai到Aj的和最大
例如整数序列 的最大子序列的和为
对于这个问题最简单也是最容易想到的那就是穷举所有子序列的方法利用三重循环依次求出所有子序列的和然后取最大的那个当然算法复杂度会达到O(n^)显然这种方法不是最优的下面给出一个算法复杂度为O(n)的线性算法实现算法的来源于Programming Pearls一书 在给出线性算法之前先来看一个对穷举算法进行优化的算法它的算法复杂度为O(n^)其实这个算法只是对对穷举算法稍微做了一些修改其实子序列的和我们并不需要每次都重新计算一遍假设Sum(i j)是A[i] A[j]的和那么Sum(i j+) = Sum(i j) + A[j+]利用这一个递推我们就可以得到下面这个算法
int max_sub(int a[]int size)
{
int ijvmax=a[];
for(i=;i {
v=;
for(j=i;j {
v=v+a[j];//Sum(i j+) = Sum(i j) + A[j+]
if(v>max)
max=v;
}
}
return max;
}
那怎样才能达到线性复杂度呢？这里运用动态规划的思想先看一下源代码实现
int max_sub(int a[] int size)
{
int imax=temp_sum=;
for(i=;i {
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<)
temp_sum=;
}
return max;
}
按单词反转字符串的问题
并不是简单的字符串反转而是按给定字符串里的单词将字符串倒转过来就是说字符串里面的单词还是保持原来的顺序这里的每个单词用空格分开
例如Here is
经过反转后变为
is Here
如果只是简单的将所有字符串翻转的话可以遍历字符串将第一个字符和最后一个交换第二个和倒数第二个交换依次循环其实按照单词反转的话可以在第一遍遍历的基础上再遍历一遍字符串对每一个单词再反转一次这样每个单词又恢复了原来的顺序
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+];
strcpy(restrstr);
int ij;
for(i=j=len;ij)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
int k=;
while(k {
i=j=k;
while(restr[j]!= &#;&#; restr[j]!= )
j++;
k=j+;
j;
for(;ij)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
}
return restr;
}
如果考虑空间和时间的优化的话当然可以将上面代码里两个字符串交换部分改为异或实现
例如将
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
改为
restr[i]^=restr[j];
restr[j]^=restr[i];
restr[i]^=restr[j];
删除数组中重复的数字问题
一个动态长度可变的数字序列以数字为结束标志要求将重复的数字用一个数字代替
例如将数组 转变成 问题比较简单要注意的是这个数组是动态的所以避免麻烦我还是用了STL的vector
#include
#include
using namespace std;
//remove the duplicated numbers in an intger array the array was end with ;
//eg &#;>
void static remove_duplicated(int a[] vector&#; _st)
{
_stpush_back(a[]);
for(int i=;_st[_stsize()]!=;i++)
{
if(a[i]!=a[i])
_stpush_back(a[i]);
}
}
当然如果可以改变原来的数组的话可以不用STL仅需要指针操作就可以了下面这个程序将修改原来数组的内容
void static remove_duplicated(int a[])
{
if(a[]== || a==NULL)
return;
int insert=current=;
while(a[current]!=)
{
if(a[current]!=a[current])
{
a[insert]=a[current];
insert++;
current++;
}
else
current++;
}
a[insert]=;
}
如何判断一棵二叉树是否是平衡二叉树问题
判断一个二叉排序树是否是平衡二叉树 解决方案根据平衡二叉树的定义如果任意节点的左右子树的深度相差不超过那这棵树就是平衡二叉树
首先编写一个计算二叉树深度的函数利用递归实现
template
static int Depth(BSTreeNode* pbs)
{
if (pbs==NULL)
return ;
else
{
int ld = Depth(pbs>left);
int rd = Depth(pbs>right);
return + (ld >rd ? ld : rd);
}
}
下面是利用递归判断左右子树的深度是否相差来判断是否是平衡二叉树的函数
template
static bool isBalance(BSTreeNode* pbs)
{
if (pbs==NULL)
return true;
int dis = Depth(pbs>left) &#; Depth(pbs>right);
if (dis> || dis< )
return false;
else
return isBalance(pbs>left) &#;&#; isBalance(pbs>right);
}
