算法题
好久没有做算法题了，重温几个简单的算法题。
第一题：求子数组的最大和
这是一道很常见的算法题，很多人都能很快的写出算法，但很多人都不能写得完全正确，问题主要出在sum初始化上，
很多错误的答案将他初始化为0，如果数组的所有元素都为负，那么得到的最大最是0，sum要初始化成数组的第一个元素。
第二题：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句
这道题在网上也有很多个版本，有在构造函数中实现加法，利用两个静态变量一个存结果，一个存当前值，然后创建一个一维n个元素的数组，存结果的静态变量即为所求，
还有的就是用两个方法，一个方法是递归的，另一个值返回常量值0，就是把递归中的判断改成了一个返回值始终是0的方法。
我要说的是第三者方法：利用模板和关键字inline，编译后的结果就是：1+2+...+n，不会生成一堆方法的调用，因为将方法定义成了inline。
第三题：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
这道题主要用上了队列的思想，先进先出，因为我们很容易实现以层的顺序将二叉树中的元素插入队列，
先将根节点插入队列，每个节点出队列的同时将其子节点加入队列。打印出队列的节点。
// 求子数组的最大和
int maxSum( int * arr, int len)
{
int sum,max;
sum =max=arr[ 0 ];
for ( int i= 1 ;i<len;i++ )
{
if (sum<= 0 )
{
sum = arr[i];
} else {
sum += arr[i];
}
if (sum> max)
{
max = sum;
}
}
return max;
}
// 求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句
template< int n> inline int Sum( int m)
{
return Sum<n- 1 >(m- 1 )+ m;
}
template <> inline int Sum< 1 >( int m)
{
return 1 ;
}
template <> inline int Sum< 0 >( int m)
{
return 0 ;
}
// 第三题：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
class PrintByFloor
{
public :
struct Node
{
int value;
Node * left;
Node * right;
Node( int val):value(val),left(NULL),right(NULL){}
};
PrintByFloor():root( new Node(- 1 )){}
~ PrintByFloor(){
MakeEmpty(root);
}
void Print()
{
if (root== NULL)
{
return ;
}
queue <Node*> queue;
if (root->left!= NULL){
queue.push(root -> left);
} else
{
queue.push(root -> right);
}
while (queue.size())
{
Node * cur= queue.front();
cout <<cur->value<< " \t " ;
if (cur->left!= NULL)
{
queue.push(cur -> left);
}
if (cur->right!= NULL)
{
queue.push(cur -> right);
}
queue.pop();
}
}
Node * Add( int value,Node * t)
{
if (t== NULL)
{
t = new Node(value);
} else if (value<t-> value)
{
if (t->left== NULL)
{
t ->left= new Node(value);
} else {
return Add(value,t-> left);
}
} else if (value>t-> value)
{
if (t->right== NULL)
{
t ->right= new Node(value);
} else {
return Add(value,t-> right);
}
}
return t;
}
Node * Add( int value)
{
return Add(value,root);
}
private :
void MakeEmpty(Node * t)
{
if (t!= NULL)
{
MakeEmpty(t -> left);
MakeEmpty(t -> right);
delete t;
t = NULL;
}
}
Node * root;
};
测试代码如下：
// 测试代码
int main() {
int arr[]={ 1 ,- 3 , 5 , 5 ,- 6 ,- 2 ,- 7 };
int maxValue=maxSum(arr, sizeof (arr)/ sizeof (arr[ 0 ]));
cout <<maxValue<< endl;
{
PrintByFloor floor;
floor.Add( 8 );
floor.Add( 6 );
floor.Add( 5 );
floor.Add( 7 );
floor.Add( 11 );
floor.Add( 9 );
floor.Add( 12 );
floor.Add( 10 );
floor.Add( 3 );
floor.Print();
}
cout << endl;
int sum=Sum< 100 >( 100 );
cout <<sum<< endl;
getchar();
return 0 ;
}
结果截图：
作者： 陈太汉
博客： http://www.cnblogs.com/hlxs/
分类: C/C++ , 算法
标签: 分析 , 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息