一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 687|回复: 1
收起左侧

[编程题] 攒点经验,发个g店面常见题

[复制链接] |试试Instant~ |关注本帖
nano 发表于 2014-10-8 08:51:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目来自
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;
}


发帖赚点经验

评分

1

查看全部评分

Soviet 发表于 2014-10-23 04:14:53 | 显示全部楼层
面试前一天晚上才看到,今天面谷歌就遇上了,谢楼主
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表