max=temp_sum; else if(temp_sum<0) temp_sum=0; }
return max; }
5. 按单词反转字符串的问题
并不是简单的字符串反转，而是按给定字符串里的单词将字符串倒转过来，就是说字符串里面的单词还是保持原来的顺序，这里的每个单词用空格分开。 例如：Here is www.fishksy.com.cn 经过反转后变为：
www.fishksy.com.cn is Here
如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。这样每个单词又恢复了原来的顺序。 char* reverse_word(const char* str) {
int len = strlen(str); char* restr = new char[len+1]; strcpy(restr,str); int i,j;
for(i=0,j=len-1;i { char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp;
} int k=0; while(k { i=j=k;
while(restr[j]!=' ' && restr[j]!='' ) j++; k=j+1; j--; for(;i {
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]; 6. 删除数组中重复的数字问题
一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替。 例如：将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成1,2,7,1,5,0 问题比较简单，要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的vector。 #include #include
using namespace std;
//remove the duplicated numbers in an intger array, the array was end with 0; //e.g. 1,1,1,2,2,5,4,4,4,4,1,0 —>1,2,5,4,1,0 void static remove_duplicated(int a[], vector& _st) {
_st.push_back(a[0]);
for(int i=1;_st[_st.size()-1]!=0;i++) {
if(a[i-1]!=a[i]) _st.push_back(a[i]); } }
当然如果可以改变原来的数组的话，可以不用STL，仅需要指针操作就可以了。下面这个程序将修改原来数组的内容。
void static remove_duplicated2(int a[]) {
if(a[0]==0 || a==NULL) return;
int insert=1,current=1; while(a[current]!=0) {
if(a[current]!=a[current-1]) {
a[insert]=a[current]; insert++; current++; } else current++; }
a[insert]=0; }
7. 如何判断一棵二叉树是否是平衡二叉树问题
判断一个二叉排序树是否是平衡二叉树 解决方案：根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。 首先编写一个计算二叉树深度的函数，利用递归实现。 template
static int Depth(BSTreeNode* 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
static bool isBalance(BSTreeNode* 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); } 第五部分
微软的22道数据结构算法面试题(含答案) 1、反转一个链表。循环算法。 1 List reverse(List l) { 2 if(!l) return l; 3 list cur = l.next;
互联网IT公司面试指导手册
