文档章节

算法学习笔记(四)---第k个二进制数字问题

夏尘安
 夏尘安
发布于 2014/04/13 14:05
字数 640
阅读 213
收藏 0

昨天晚上做微软的线上测试,被虐的杠杠的。。。先贴一道题出来,题目如下

重点还是思想,而且一点出来这个思想真的不难。

就是二进制数字排序问题。比如21,20的时候,排序就是:

0011,0101,0110,1001,1010,1100

仔细推测可以发现,从右到左(低位到高位)来看,若出现01分界线就一定需要交换,并且01的右边都需要头尾依次交换。

拿长一点的数字来举例,01111000下一位数字应该是10000111,其实就是最高两位01交换成10,后面六位,第一位1和最后一位0交换,第二位1和倒数第二位0交换,第三位1和倒数第三为0交换。多举几个例子就会发现这个规律绝对是正确的。

然后还稍微有个问题就是题目中要求k位输入有错要打印impossible,就是怎么判断的问题。代码简单来说就是从第一个数字前面m0后面n1开始数,数到第k个数字返回这个数就行了。可是如果k>排序组合数值呢?

一个办法就是计算一下排列组合总数为K若大于这个值就打印错误,当然比较麻烦;

第二个方法就是判断已数到最大数字,1100这种1都在高位,但是计数还没达到k,输出错误,不过还是要把整个数组都要判断一遍。

最后我用的简单方法是,因为每次找到下一位数字都肯定要交换数字,找到k程序会马上终止,如果还在循环但是没有交换数字,就判断已经达到最大排列组合。代码如下:

#include <iostream>
using namespace std;
int main(void)
{
         int m,n,k,length,flag=0,temp,impossible=0,number=0;
         int num[40];
         cin>>m>>n>>k;
         for(int i=0;i<m;i++)
         {num[i]=0;}
         for(i=m;i<m+n;i++)//the mininum
         {
                   num[i]=1;
         }
         length=m+n;
         //find the k-th num aggregated by 0 of m numbers and 1 of n numbers.
         while(number!=k-1){
             for(i=length-1;i>0;i--)
                   {
                   if(num[i]!=num[i-1])
                   {
           if (num[i]==1)
                            {
                                     temp=num[i];
                                     num[i]=num[i-1];
                                     num[i-1]=temp;
                                     for(int j=i+1;j<length-1;j++)
                                     {
                                               temp=num[j];
                                               num[j]=num[length-(j-i-1)-1];
                                               num[length-(j-i-1)-1]=temp;
                                     }
                                     flag=1;
                                     break;
                            }
                   }
                   }
             number++;
                   if(flag==0)
                   {
                            cout<<"Impossible"<<endl;
                            impossible=1;
                            break;
                   }
                   flag=0;
         }
         if(impossible==0){
         for(i=0;i<length;i++)
         {cout<<num[i];}
         cout<<endl;
         }
         return 0;
}


© 著作权归作者所有

夏尘安
粉丝 0
博文 7
码字总数 3091
作品 0
海淀
私信 提问
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
“我爱智能”原创性博客索引

不知不觉,博客也写出了一点小体系,新的阶段已经开始,未来希望再接再厉继续补充这一体系,在成长中写博客,在博客中成长,在此先做一个小的梳理,谢谢大家的支持。 一)关于深度学习系列 ...

on2way
2015/08/29
0
0
ApacheCN 人工智能知识树 v1.0

Special Sponsors 贡献者:飞龙 版本:v1.0 最近总是有人问我,把 ApacheCN 这些资料看完一遍要用多长时间,如果你一本书一本书看的话,的确要用很长时间。但我觉得这是非常麻烦的,因为每本...

ApacheCN_飞龙
05/18
0
0
机器学习,Hello World from Javascript!

摘要:JavaScript 适合做机器学习吗?这是一个问号。但每一位开发者都应该了解机器学习解决问题的思维和方法,并思考:它将会给我们的工作带来什么?同样,算法能力可能会是下一阶段工程师的...

淘宝前端团队
2017/12/08
0
0
7步掌握Python机器学习

“开始”,是一个令人激动的字眼。然而万事开头难,当你拥有过多的选择时,往往就会不知所措。 我们希望借助免费、便捷的在线资源,帮助你完成从小白到大牛的蜕变。这篇文章将会回答如何选择...

【方向】
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JS基础-该如何理解原型、原型链?

JS的原型、原型链一直是比较难理解的内容,不少初学者甚至有一定经验的老鸟都不一定能完全说清楚,更多的"很可能"是一知半解,而这部分内容又是JS的核心内容,想要技术进阶的话肯定不能对这个...

OBKoro1
今天
6
0
高防CDN的出现是为了解决网站的哪些问题?

高防CDN是为了更好的服务网络而出现的,是通过高防DNS来实现的。高防CDN是通过智能化的系统判断来路,再反馈给用户,可以减轻用户使用过程的复杂程度。通过智能DNS解析,能让网站访问者连接到...

云漫网络Ruan
今天
14
0
OSChina 周一乱弹 —— 熟悉的味道,难道这就是恋爱的感觉

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @xiaoshiyue :好久没分享歌了分享张碧晨的单曲《今后我与自己流浪》 《今后我与自己流浪》- 张碧晨 手机党少年们想听歌,请使劲儿戳(这里)...

小小编辑
今天
2.8K
24
SpringBoot中 集成 redisTemplate 对 Redis 的操作(二)

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二) List 类型的操作 1、 向列表左侧添加数据 Long leftPush = redisTemplate.opsForList().leftPush("name", name); 2、 向列表右......

TcWong
今天
46
0
排序––快速排序(二)

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架: 1、首先需要设置一个枢轴元素即setPivot(int i); 2、然后需要与枢轴元素进行比较即int comparePivot(int j); 3、最后...

FAT_mt
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部