好久沒有做算法題了，重溫幾個簡單的算法題。
第一題：求子數組的最大和
這是一道很常見的算法題，很多人都能很快的寫出算法，但很多人都不能寫得完全正確，問題主要出在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;
}
結果截圖：
作者 陳太漢
