某公司一道笔试题，求思路及解答

Question

有A个1和B个0组成的列数字，每次取出K个数（可以不连续），如果是0则变成1，如果是1则变成0，这列数字最大长度不超过10万，现求一个算法，问取出多少次才能变成全部是1的一列数？
public long pick(long A,long B,long K)
{}
比如long n = pick(4,1,3)
即11110
第一步：10000
第二步：01100
第三步：11111
所以：n=3

Answer 1

结合你给的例子，我看了数分钟才看明白你的题什么意思。
A,B,K分别代表第一二三这三个参数是吧？
我觉得出这个题的是脑残。
如果每次取出K个数没有一定的规则的话，那么这个次数能算出来么？
就比如你给的例子：
即11110
第一步：10000
第二步：01100
第三步：11111 
11110 -> 10000 -> 01100 -> 11111
完全没有章法可言。
最极端的情况，当然就是用B/K余数直接进位了。
其他的情况，让先知来告诉你吧。

Answer 2

11110 -> 10000 
10000 -> 01100
01100 -> 11111 这样会更清晰些。

Answer 3

粗看了一遍~感觉章法还是有的!至少最后一步一定是把K个0变成1
那么下一步问题是如何把A个1和B个0 转变成有K个0 的列数!

Answer 4

public long pick(long A,long B,long K){
if((A+B)<=K || K==0 || (A+B%K)<K) return  -1; //如果K的大于A+B 那么无解 如果K=0 也是无解!
else return B/K+2;
}我的答案不知道对不对!
解释:
当 A+B 小于K时无解;
当 K为0时无解;
当 B取K的模后与A的和小于K时无解;
其他,只要B/K+2次就可以求出来!有考虑不到的地方,望指正!

Answer 5

    public long pick(long A,long B,long K){
        if((A+B)<=K || ( K==0 && B != 0 )|| (A+B%K)<K) return  -1; 
        else return B/K+2;        
    }
刚刚代码写的有点问题!改了一下!

Answer 6

我一直在关注这个帖子。
不知道是楼主没描述清楚，还是出题的人脑子让门挤了。如果真如楼主所言，K个数不连续，而且是随机取的，那只有god才知道什么时候能变成全是1。

Answer 7

就楼主的例子来说,
K=3:B=1变成1要3次,B=2变成1要2次,B=3变成1要1次,B大于3时取模加上前面的;
K=4,B只能为偶数,B=2时2次;
K=5,B=1时2次,B=2时2次,B=3时3次,B=4时4次,B=5时1次;如果B是奇数个,K肯定是奇数的,不然出不了结果,比如2,4,一次取偶数个,必然在把一个0变1的同时会把一个1变0,怎么换也不可能把奇数个0变成1!最差的方法就是用递规把每种情况都试一遍~``不去管1的个数,将B个0通过一次取K个再取反的方法需要几次能全变成1.当B大于K时只算B%K的部分,比如分别求{1,2,3```B%K}个0和N个1变换得到M个数字,再用同样方法递归变换这M个数,直到得出结果.条件要设置好,不然可能会进入死循环(比如K偶B奇时).

Answer 8

import java.util.Set;
import java.util.HashSet;
public class Pick {
private Set<Long> B=new HashSet<Long>();//保存已转变过的形式
private long shortest=10000;//次数
public void trans(long b,long k,long times){
if(b%k==0&&shortest>times+1) {
shortest=times+1;
return;
}
B.add(b);//将此次转变之前的形式保存起来
for(long i=0;i<=b;i++){
long t=times;
b+=k-i-i;
if(B.contains(b)||b/k>2) continue;//转变后的形式如果已经出现过或是b的长度大于k的2倍则进行下一次循环
t++;
trans(b,k,t);
}
}
public long pick(long B,long K){
long b=B%K;
long m=B/K;
if(b==0) return m;//刚好整除
trans(b,K,0);
return this.shortest+m;
}
public static void main(String[] args){
Pick p=new Pick();
long result=p.pick(1, 3);
System.out.println(result<10000?result:"没有结果!");
}
}程序有逻辑错误,次数没算对,要下班了没时间改,高手改下~``
基本思路就是对B的变换,假定A足够用.
例:对于B=2,K=3,先将B=2保存,分别求出当变换0个0,1个0,2个0时的情况,再分别递归.当B重复或B>2K时放弃(B>2K时变换次数肯定不会是最少的,而且会造成死循环).当全变换成1时,保存次数,最后得最少次数.