精华内容
下载资源
问答
  • 关于荷兰国旗问题

    2018-07-22 10:37:00
    题目大意是给一个长度为n整数序列,然后再给一个数num,然后将小于这个num放在序列前面,等于num放在序列中间,大于num放在序列后面,不要求排序,时间复杂度O(n),空间复杂度O(1)(即不能构造其他数组...

    题目大意是给一个长度为n的整数序列,然后再给一个数num,然后将小于这个num的放在序列前面,等于num的放在序列中间,大于num的放在序列的后面,不要求排序,时间复杂度O(n),空间复杂度O(1)(即不能构造其他数组)

    这里没怎么用到算法的基础,而是运用数据的调配,首先我们在数组的两端放两个指针,一个head,一个end,head前面的是小于num区的数,end后面的是大于num区的数,中间的就是等于num区的数。

    然后遍历数组,如果有小于num的数,就和小于区的下一个元素交换,然后小于区扩大一个,如果有大于num的数,就和大于区的前一个元素进行交换,然后大于区扩大一个,直到循环遍历到大于区为止

     然后贴上代码

    #include<cstdio>
    #include<iostream>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int n,m;
        int a[1000];
        int num;
        cin>>n>>num;
        for(int i=0;i<n;i++) cin>>a[i];
        int head=0,end=n-1;
        for(int i=0;i<=end;){
            if(a[i]<num){
                swap(a[i],a[head++]);
                i++;
            }
            else if(a[i]>num){
                swap(a[i],a[end--]);
            }
            else i++;
        }
        for(int i=0;i<n;i++) cout<<a[i]<<' ';
        return 0;
    }

     

    转载于:https://www.cnblogs.com/maybe96/p/9349322.html

    展开全文
  • 荷兰国旗问题

    2015-08-20 14:29:48
    题目描述 拿破仑席卷欧洲大陆之后,代表自由,平等,博爱竖色三色旗也风靡一时。荷兰国旗就是一面三色旗(只不过是横向),自上而下为红白蓝三色。...该问题本身是关于三色球排序和分类,由荷兰科学家Di

    https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.07.md

    题目描述

    拿破仑席卷欧洲大陆之后,代表自由,平等,博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗(只不过是横向的),自上而下为红白蓝三色。

    该问题本身是关于三色球排序和分类的,由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类,Dijkstra就想象成他母国的国旗,于是问题也就被命名为荷兰旗问题(Dutch National Flag Problem)。

    下面是问题的正规描述: 现有n个红白蓝三种不同颜色的小球,乱序排列在一起,请通过两两交换任意两个球,使得从左至右,依次是一些红球、一些白球、一些蓝球。

    分析与解法

    初看此题,我们貌似除了暴力解决并无好的办法,但联想到我们所熟知的快速排序算法呢?

    我们知道,快速排序依托于一个partition分治过程,在每一趟排序的过程中,选取的主元都会把整个数组排列成一大一小的部分,那我们是否可以借鉴partition过程设定三个指针完成重新排列,使得所有球排列成三个不同颜色的球呢?

    解法一

    通过前面的分析得知,这个问题类似快排中partition过程,只是需要用到三个指针:一个前指针begin,一个中指针current,一个后指针end,current指针遍历整个数组序列,当

    1. current指针所指元素为0时,与begin指针所指的元素交换,而后current++,begin++ ;
    2. current指针所指元素为1时,不做任何交换(即球不动),而后current++ ;
    3. current指针所指元素为2时,与end指针所指的元素交换,而后,current指针不动,end-- 。

    为什么上述第3点中,current指针所指元素为2时,与end指针所指元素交换之后,current指针不能动呢?因为第三步中current指针所指元素与end指针所指元素交换之前,如果end指针之前指的元素是0,那么与current指针所指元素交换之后,current指针此刻所指的元素是0,此时,current指针能动么?不能动,因为如上述第1点所述,如果current指针所指的元素是0,还得与begin指针所指的元素交换。

    ok,说这么多,你可能不甚明了,直接引用下gnuhpc的图,就一目了然了:

    img img

    参考代码如下:

    //引用自gnuhpc  
    while( current<=end )        
    {             
      if( array[current] ==0 )             
       {                 
          swap(array[current],array[begin]);                  
          current++;                  
          begin++;            
       }             
       else if( array[current] == 1 )            
       {                 
          current++;            
       }   
    
       else //When array[current] =2   
       {               
          swap(array[current],array[end]);                
          end--;            
       }      
    }  

    举一反三

    给定一个字符串里面只有"R" "G" "B" 三个字符,请排序,最终结果的顺序是R在前 G中 B在后。

    要求:空间复杂度是O(1),且只能遍历一次字符串。

    展开全文
  • 关于荷兰国旗排序问题可以简化理解将一个数组中数据排序,比如给定一个buffer内部元素有N个0,1,2,buffer内部是无序,如果要求通过一趟扫描,并且不能利用额外空间,进行排序如何解决。 这种问题最直观思想...

    关于荷兰国旗排序问题可以简化理解将一个数组中的数据排序,比如给定一个buffer内部元素有N个0,1,2,buffer内部是无序的,如果要求通过一趟扫描,并且不能利用额外的空间,进行排序如何解决。
    这种问题最直观的思想就是采用多指针策略,元素起始位置一个移动索引A,元素的尾部一个移动索引B,然后一个移动索引C来扫描数组,开始的时候A与C的索引位置形同,如果这个时候C位置是0则与A进行交换,然后A与C索引都进行增加,这一步操作之后我们可以确保A索引位置指针的元素都是0,如果C位置是1则让C进行索引自增,这个时候A的索引位置与C的索引位置是已经产生差别,再次检测C的位置发现是2,这时候需要与B索引的尾部元素交换然后B索引自减,这个时候需要特别关注一点,就是B的元素交换成功以后,我们可以理解为B索引位置后的元素都是2,B与C交换了以后,我们并不能让C索引进行自增,因为换过来的新元素值我们不确定是多少,换言之此刻的C索引位置指向的元素可能是任何数,我们需要再重新检测下,所以这个时候B元素进行–,C元素索引不动。当C元素的索引位置与B元素索引位置重叠的时候此数组完成扫描,时间复杂度为N。
    简易demo代码如下:

        void sort(vector<int>& nums) 
        {
            //left index A
            int i = 0;
            //right index B
            int j = nums.size() - 1;
            //curent index C
            int z = 0;
            
            while(z <= j)
            {
                if(nums[z] == 0)
                {
                    int tmp = nums[i];
                    nums[i] = nums[z];
                    nums[z] = tmp;
                    i++;
                    z++;
                }           
                else if(nums[z] == 2)
                {
                    int tmp = nums[j];
                    nums[j] = nums[z];
                    nums[z] = tmp;
                    j--;   
                }
                else
                {
                    z++;
                }
            }       
        }
    
    展开全文
  • 一个有头结点的关于0、1、2随机排列,我们要实现将数字按照0、1、2顺序排列。这也就是这道题名为荷兰国旗原因,下图即为荷兰国旗,可谓生动形象。 单链表: 链表可以实现存储空间动态管理链式存储结构,...

    数据结构-用单链表实现荷兰国旗问题

    (学数据结构的第4周)

    (还是太菜,3/18调了3节课才调通)

    问题简单描述

    荷兰国旗有红白蓝三种颜色,分别用数字0、1、2表示。一个有头结点的关于0、1、2的随机排列,我们要实现将数字按照0、1、2的顺序排列。这也就是这道题名为荷兰国旗的原因,下图即为荷兰国旗,可谓生动形象。

    Alt
    单链表:
    链表可以实现存储空间动态管理的链式存储结构,其中每个存储结点不仅包含元素本身的信息(数据域),而且包含表示元素之间逻辑关系的信息,C/C++采用指针实现。所谓单链表是每个结点中包含数据域外只设置一个指针域,其指向后继结点。

    结点结构
    ┌───┬───┐
    │data │next │
    └───┴───┘
    data域–存放结点值的数据域
    next域–存放结点的直接后继的地址(位置)的指针域(链域)
    在这里插入图片描述
    思考:
    (1)将1张单链表L分成3张单链表,数据域为0的存放在L1,数据域为1的存放在L2,数据域为2的存放在L3;
    (2)将3张表连接在一起,成为1张表。

    C代码如下

    #include"linklist.cpp"
    void sort(LinkNode *&L,LinkNode *&L1,LinkNode *&L2,LinkNode *&L3)
    {
    	LinkNode *p=L->next,*r1,*r2,*r3;//p指向第1个数据节点
    	L1=L;//L1利用原来L的头结点
    	r1=L1;//r1始终指向L1的尾结点
    	L2=(LinkNode *)malloc(sizeof(LinkNode));
    	L2->next=NULL;
    	r2=L2;//r2始终指向L2的尾结点
    	L3=(LinkNode *)malloc(sizeof(LinkNode));
    	L3->next=NULL;
    	r3=L3;//r3始终指向L3的尾结点
        while(p!=NULL)
    	{
    		if(p->data==0)
    		{
    			r1->next=p;
    			r1=p;
    			p=p->next;//p移到下一个结点
    		}
            else if(p->data==1)
    		{
    			r2->next=p;
    			r2=p;
    			p=p->next;
    		}
    		else if(p->data==2)
    		{
    			r3->next=p;
    			r3=p;
    			p=p->next;
    		}	
    	}
    	
    	r1->next=L2->next;//L1尾结点指向L2首结点
    	r2->next=L3->next;//L2尾结点指向L3首结点
    	r3->next=NULL;
    	DispList(L);
    }
    
    int main()
    {
    	LinkNode *h,*h1,*h2,*h3;
    	int a[]={0,1,0,2,1,2,0,1,2};
        CreateListR(h,a,9);
        DispList(h);
    	sort(h,h1,h2,h3);
        
    	return 0;
    }
    

    在“linklist.cpp”里包含了单链表的定义、建立、头插法/尾插法、查找等一系列基本运算。要用到如下:

    #include<stdio.h>
    #include<malloc.h>
    
    typedef int ElemType;
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }LinkNode;
    
    void CreateListR(LinkNode *&L,ElemType a[],int n)//尾插法
    {
    	LinkNode *s,*r;
    	L=(LinkNode *)malloc(sizeof(LinkNode));
    	r=L;
    	for(int i=0;i<n;i++)
    	{
    		s=(LinkNode *)malloc(sizeof(LinkNode));
    		s->data=a[i];
            r->next=s;
    		r=s;
    	}
    	r->next=NULL;
    }
    
    输出结果

    在这里插入图片描述

    展开全文
  • 荷兰国旗

    千次阅读 2015-04-15 12:29:18
    问题本身是关于三色球排序和分类,由荷兰科学家Dijkstra提出。由于问题三色小球有序排列后正好分为三类,Dijkstra就想象成他母国国旗,于是问题也就被命名为荷兰问题(Dutch National Flag Problem)。 ...
  • 关于UPS及其应用中几个问题的讨论  中国电源学会交流稳定电源专业委员会 王其英A前言 乍一踏进UPS市场,其状如雨后春笋,拨地而起,令人耳目一新,又有百花争艳之势。国外品牌产品有瑞士V-SPEED IM Sitepro....
  • 关于CPU占用率过高的问题 很多天前就发现自己的腾讯云服务器一直有个进程CPU占用率很高 使用top命令查看发现是kswapd0进程 上网查了很多教程都说是因为内存占用较高导致系统自动调用kswapd0进程来搬运内存数据到...
  • 今天分享关于快速排序思路以及三种版本迭代优化 我们先来介绍partition问题 多图预警!! 所有算法都经过对数器核对,可以放心使用 已知一个数组arr,要求我们以随机一个数作为标准把数组分为以下两个...
  • 最开始由荷兰科学家迪杰斯特拉提出的问题 即五台计算机同时试图访问五台共享的磁盘驱动器。 这是一个多线程同步问题,用来解释死锁和资源耗尽。 问题描述: 有五个哲学家每天都只做两件事情,吃饭(eating)和...
  • 关于我国人工智能学科专业人才培养问题  在上世纪90年代,原国家教委高校学生司于1991年3月8日发文聘任我担任学生司计算机顾问,负责全国高校招生系统联网工作,对国内高校学科专业建设是熟悉了解。现在提起...
  • 在学习web开发,React时候,在读取json时候,出现如下问题,文件 in_theaters.json中用json格式存储了数据,如下 { "count": 14, "start": 0, "total": 63, "subjects": [ { "rating": { "max":...
  • 【算法】荷兰国旗

    2015-06-08 16:01:32
    from ... 题目描述 ...拿破仑席卷欧洲大陆之后,代表自由,平等,博爱竖色三色旗也风靡一时。荷兰国旗就是一面三色旗(只不过是横向),自上而下为红白蓝三色。...该问题本身是关于三色球排序和分
  • 1月19日,中国科学院计算技术研究所回应有关员工造假“国产编程语言”网络质疑,发布了关于“木兰”语言问题处理情况说明。声明强调,近日,网上出现质疑“木兰”语言信息。我所获知这一情况后高度重视。经所...
  • 内容全部来自编程之法:面试和算法心得一书...该问题本身是关于三色球排序和分类,由荷兰科学家Dijkstra提出。由于问题三色小球有序排列后正好分为三类,Dijkstra就想象成他母国国旗,于是问题也就被命名为...
  • 雷锋网按:数据隐私、数据安全、数据道德这三者一直是商业界与学术界探讨热点问题,本文就在流程过程中如和处理上述三个问题,提出了一些自己见解。本文作者为 Anne Rozinat 博士与Christian W. Gunther 博士,...
  • 问题联系Q1446595067吉林快-三平台开发, 是一种面向对象解释型计算机程序设计语言,由荷兰人Guido van Rossum于1989年发明,第一个公开发行版发行于1991年。 Python是纯粹自由软件, 源代码和解释器CPython...
  • 网友热议一针见血地指出:关于里约奥运第一场打荷兰,失利原因,小宇是次要因素,不是主要因素。不是为小宇推卸责任,那时候首次参加奥运会,作为队内年龄最小新人,不该承担主要责任,尽管小宇责任心很强。我...
  • 资料均来源于维基百科关于进程同步,我们先来看一道计算机科学中著名经典问题:哲学家就餐问题(Dining Philosophers Problem)。这个问题最初是由荷兰计算机科学家艾兹赫尔·韦伯·戴克斯特拉(Edsger Wybe ...
  • 1972年10月,国际信息处理联合会(IFIP)在荷兰召开关于CAD原理工作会议”上给出如下定义:CAD是一种技术,其中人与计算机结合为一个问题求解组,紧密配合,发挥各自所长,从而使其工作优于每一方,并为应用多...
  • 请求示例可以是希望宣布搬迁(荷兰人致富)到他新市镇人,或者打算结婚(融合voorgenomen huwelijk)到他或她市镇人。 请求表示个人/组织已向特定组织提出请求,或个人/组织正在制定但尚未提交给组织...
  • 今天做中国银联的在线笔试,遇到好多关于经济和会计方面的问题,其实这些问题和生活息息相关,觉得有必要去了解一些这方面的知识。关于会计,另有Blog记录学习。加油,雅蠛蝶。那些法则 丁伯根法则 - Tinbergens ...
  • 幸福问题是社会学一直以来关注的问题。论文以荷兰社会学家鲁特·芬因霍芬的幸福研究为视角,分析当前欧洲幸福研究中概念、方法的使用。鲁特将幸福定义为对整体生活满意度的自我报告,这已经成为西方特别是欧洲社会...
  • 荷兰消费者保护组织将三星荷兰公司提交法院,认为该公司应在其推出后一个月内为其电话提供更新和升级服务,推出后四年内和/或两年后出售时间。“ 三星智能手机更新 消费者保护组织还要求法院命令三星向消费者...
  • 但是,现有方法是很难同时抽取多尺度和多- 在同一时间,这对于captur 荷兰国际集团面部图像内在特性重要directiv 两者均几何结构。 在本文中,我们建议采用对数非抽样Contourlet变换(LNSCT)到estimatË ...
  • L'Air du BoisOpenCutList OpenCutList是扩展,用于自动生成零件清单,计算切割图,打印标签以及生成木工项目成本和重量报告。 下载并安装 可从文件夹或其官方页面中获得带...尚无关于OpenCutList全面指南。

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

关于荷兰的问题