当前位置:编程学习 > C/C++ >>

三道简单的算法题(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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,