三道简单的算法题(C++)
好久没有做算法题了,重温几个简单的算法题。
第一题:求子数组的最大和
这是一道很常见的算法题,很多人都能很快的写出算法,但很多人都不能写得完全正确,问题主要出在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)
&nb
补充:软件开发 , C++ ,