三道简单算法题(一)-阿里云开发者社区

三道简单算法题(一)

2017-12-13 1231

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

好久没有做算法题了，重温几个简单的算法题。
第一题：求子数组的最大和
这是一道很常见的算法题，很多人都能很快的写出算法，但很多人都不能写得完全正确，问题主要出在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;
}