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

我把这个算法称为找♂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)

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

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

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

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

显然这个算法的复杂度太糟糕了，每移动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; }

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