4.8华为笔试第二道题-二进制

输入一个0和1的整型串代表二进制

其中：

任意的00可以转化为10
任意的10可以转化为01

输出转化之后，最大的二进制。

个人想法：

观察转换的两种规则，

第一个是转换规则，连续的两个0能变大，延伸为所有连续的0000可以转化为1110（只有最后有一个0）

第二个是转移规则，0只能左移，1只能右移

因此，

随便一个序列110010100111010（15个，7个0，8个1）

从第一个0开始，后面的0都转移第一个0的后面，得到110000000111111

再通过00->10的规则，最后只剩下最右边的0，得到11 1111110 111111

最后转换为111111011111111

所以只需要统计长为n序列中前序1的个数m₁，0的个数m₂即可

如果m₂==0或m₂==1，那么只需要输出原序列

否则输出：【m₁个1】-【m₂-1个1】-【1个0】-【n-m₁-m₂个1】，这样是最大的

做的时候没想透彻，然后只通过了20%的用例，不知道我想的有没有错，欢迎指正。

#华为春招笔试##华为##笔试题目#

全部评论

推荐最新楼层

hurley

同济大学 C++

我把这个算法称为找♂0算法，从定义出发的思路： 1：MAX情况，FFFF是最大的二进制数 2：对于任何一个二进制数，比较大小的条件： a) 如果所有位都相等，那么两个数相等 b) 从左向右两个数间第一个不同的位中，是1的那个数更大所以，对于两个不同的数，只要最高不同位是1，那么后面的数是多少都无所谓。因此对数组从左到右循环，找到第一个为0的位，努力让这个位变成1，变成1的方法是：看这个位的后一位是否是0，如果是0则00->10变化成功，如果是1则再看1后是不是0，如果是0则010->001->101变化成功，以此类推，当访问到末尾时还找不到能提供0的对，那么算法无能为力，可以返回了。以下是pseudocode bool move(int arr[],int start,int size){ if(start==size) false; if(arr[start+1]!=0){ move(arr,start+1,size); } if(arr[start+1]==0){ arr[start]=!arr[start]; arr[start+1]=!arr[start+1]; return true; }else return false; function solution(int arr[],int size)->int []{ for(int i=0;i<size;i++){ if(arr[i]==0){ if(!move(arr,i,size)) break; } } return arr; } 复杂度分析，最好情况n个0，O(n)遍历得到n-1个1+0，最坏情况0+n-2个1+0->n-2个1+01复杂度是O(n2)

1 回复分享

发布于 2020-04-12 03:57

凉可乐好喝

字节跳动_DATA_后端架构工程师

这个第二题我侥幸过了，我的思路是，碰到00，就换成10，如果碰到010，就换成101，侥幸通过

点赞回复分享

发布于 2020-04-09 09:04

部门直招c加加

山东大学 C++

请问华为的笔试平台是在牛客吗？

点赞回复分享

发布于 2020-04-09 09:06

老弘

华南理工大学 C++

我的思路是先找到第一个0，然后统计后面的1的数量m。因为1能右移，把0弄到高位聚集然后从左到右00变10，所以直接生成一个n-m-1个1、1个0、m个1的字符串。考试的时候忘记考虑全1的情况，结果0%。也不知道思路对不对😂

点赞回复分享

发布于 2020-04-09 12:47

牛客377850253号

RWTH Aachen University 算法工程师

&我的思路是找到第一个0的位置，记录下这个0的位置，之后每多一个0加一，最后确定这个0的位置，其他位全变为1，思路就是数零的个数😂

点赞回复分享

发布于 2020-04-09 19:45

hurley

同济大学 C++

显然这个算法的复杂度太糟糕了，每移动1个0就放弃了上一次移动变化的所有信息，如同冒泡一样去移动0。现在可以从这个算法上改进。观察发现，从最高位开始，在第t位遇到的第一个0称为首0，如果遇到00，则无条件变为10，首0向后了一位，如果遇到01，如果想把0->1则至少要找到形如0+x个1+0的结构变为10+x个1，对于n-t+1位已经达到最大，对于t+1位后的0取决于x个1后，如果遇到0，则变成1并让首0向后一位，如果遇到1，则x->x+1 function solution(int arr[],int size){ int t; for(t=0;t<size;t++){ if(arr[t]!=0) break; } for(int i=t;i<size;i++){ if(arr[i]==0){ if(i==size-1) break; if(arr[i+1]==0){ arr[i]=1; }else{ int t0=0,tp; for(int j=i+2;j<size;j++){ if(arr[j]==0){ t0++; arr[j]=1; tp=j; } } if(t0!=0){ swap(arr[min(i+t0,j)],arr[i]); } break; } } return arr; }

点赞回复分享

发布于 2020-04-12 03:57

牛客269603054号

赣南师范大学 Java

我的思路是找第一个0的位置，和数0的数量，但是一直通不过 30%。不知道错在哪里？求指点。

点赞回复分享

发布于 2021-09-28 17:57