攒点经验，发个g店面常见题

题目来自
http://www.mitbbs.com/article_t1/JobHunting/32575573_32575627_1.html

我写的版本稍有不同，保证a0>=a1<=a2>=a3 and so on

假设一开始保证a0>=a1, 考虑a2的时候，可能有
1) case 1: a2<a1
2) case 2: a2>=a1 and a2<a0
3) case 3: a2>=a0

case 2 and 3 无所谓，case 1的话只需考虑swap a1, a2,就可以满足条件了，依次类推，只需在不满足的时候swap尾端的两个值，不是很理解原Po主说不让swap

code 如下

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

void sortWave(int A[], int n)
//this function sort the array in the following way
// e.g., A={1,2,3,4,5,6}
//       ->{2,1,4,3,6,5}

{
        if(n<=1)
        return;
       
        if(A[0]<A[1])
                swap(A[0],A[1]);
       
        bool flag=true;
       
        for(int i=2;i<n;i++)
        {
                if((flag && A[i-1]>A[i])||(!flag && A[i-1]<A[i]))
                swap(A[i-1],A[i]);
               
                flag=!flag;
        }
       
        cout<<endl;
}

bool testWaveSort(int A[], int n)
{
        sortWave(A,n);
        bool flag=true;
        for(int i=1;i<n;i++)
        {
                if((flag && A[i-1]<A[i])||(!flag && A[i-1]>A[i]))
                return false;
               
                flag=!flag;
        }
        return true;
}
int main() {
        // your code goes here
        int A[0];
        if(testWaveSort(A,0))
        cout<<"test 0 succeed"<<endl;
        else
        cout<<"test 0 failed"<<endl;
       
        for(int i=0;i<500;i++)
        {
                int n=rand()%10;
                //cout<<n<<endl;
                int B[n];
                for(int j=0;j<n;j++)
                {
                B[j]=rand()%100;
                //cout<<B[j]<<" ";
                }
                //cout<<endl;
               
                if(testWaveSort(B,n))
                cout<<"test "<<i<<" succeed"<<endl;
                else
                {
                        cout<<"test "<<i<<" failed"<<endl;
                        for(int j=0;j<n;j++)
                        cout<<B[j]<<" ";
                }
        }
        return 0;
}


发帖赚点经验

面试前一天晚上才看到，今天面谷歌就遇上了，谢楼主