三道簡單算法題(一)

好久沒有做算法題了，重溫幾個(gè)簡單的算法題。
第一題：求子數(shù)組的最大和
這是一道很常見的算法題，很多人都能很快的寫出算法，但很多人都不能寫得完全正確，問題主要出在sum初始化上，
很多錯(cuò)誤的答案將他初始化為0，如果數(shù)組的所有元素都為負(fù)，那么得到的最大最是0，sum要初始化成數(shù)組的第一個(gè)元素。

第二題：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句
這道題在網(wǎng)上也有很多個(gè)版本，有在構(gòu)造函數(shù)中實(shí)現(xiàn)加法，利用兩個(gè)靜態(tài)變量一個(gè)存結(jié)果，一個(gè)存當(dāng)前值，然后創(chuàng)建一個(gè)一維n個(gè)元素的數(shù)組，存結(jié)果的靜態(tài)變量即為所求，
還有的就是用兩個(gè)方法，一個(gè)方法是遞歸的，另一個(gè)值返回常量值0，就是把遞歸中的判斷改成了一個(gè)返回值始終是0的方法。
我要說的是第三者方法：利用模板和關(guān)鍵字inline，編譯后的結(jié)果就是：1+2+...+n，不會生成一堆方法的調(diào)用，因?yàn)閷⒎椒ǘx成了inline。

第三題：輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
這道題主要用上了隊(duì)列的思想，先進(jìn)先出，因?yàn)槲覀兒苋菀讓?shí)現(xiàn)以層的順序?qū)⒍鏄渲械脑夭迦腙?duì)列，
先將根節(jié)點(diǎn)插入隊(duì)列，每個(gè)節(jié)點(diǎn)出隊(duì)列的同時(shí)將其子節(jié)點(diǎn)加入隊(duì)列。打印出隊(duì)列的節(jié)點(diǎn)。

//求子數(shù)組的最大和
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等關(guān)鍵字以及條件判斷語句
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;
}

//第三題：輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
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;
}

結(jié)果截圖：

作者：陳太漢

博客：http://www.rzrgm.cn/hlxs/

posted @ 2012-05-08 14:20 古文觀芷閱讀(7333) 評論(6) 收藏舉報(bào)

刷新頁面返回頂部

三道簡單算法題(一)

公告