阿里笔试:对于一个01字符串,每次只能任意交换两个元素,或者把0变成1,或者把1变成0,或者反转整个字符串。那么从A串变成B串至少需要多少步。

时间:2020-8-30 作者:admin

题目:对于一个01字符串,每次只能任意交换两个元素,或者把0变成1,或者把1变成0,或者反转整个字符串。那么从A串变成B串至少需要多少步。

例子,1111000变成0010011至少需要3步。


思路1:首先可以分成两种情况,一种是反转,一种是不翻转。那么如何决定到底反转不翻转?可以比较不翻转时相同的位数,和翻转之后相同的位数,如果不翻转之前相同的位数多,那么反转显然是划不来的,如果反转之后相同的位数多,那么自然要选择反转。(反转可以使用StringBuilder的reverse)。然后比较上一次操作之后(反转或者不翻转),A是1,B是0的个数;A是0,B是1的个数。选择较小值,因为我们要进行这么多次的反转操作,剩下的就是变换操作。

还是上面的例子,不翻转相同的位数为2,翻转之后相同的位数为4,因此选择反转。

翻转之后:A:0 0 0 1 1 1 1

                 B:0 0 1 0 0 1 1

可以发现,翻转之后,A是1,B是0的个数为2,A是0,B是1的个数为1。因此我们需要的最小操作数为2,即一次反转加一次变换。

代码是copy别的人,因为这种方法虽然好理解,但是实现比较繁琐,我就没写了:


private static int help(String a, String b) {
        int res = 0;
        int n = a.length();
        //不反转相同的个数
        int counta = 0;
        int countb = 0;
        for (int i = 0 ; i < n ; i++){
            if (a.charAt(i) == b.charAt(i)) counta++;
            if (a.charAt(i) == b.charAt(n-i-1)) countb++;
        }
        if (countb > counta) {
            res++;
            b = reverse(b);
        }

        //翻转完之后看能不能交换
        //0001111
        //0010011
        StringBuilder s = new StringBuilder();
        StringBuilder p = new StringBuilder();

        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)){
                s.append(a.charAt(i));
                p.append(b.charAt(i));
            }
        }
        //01100
        //10011
        int c = 0 , d = 0;
        for (char l : s.toString().toCharArray()){
            if (l == '1') c++;
            else d++;
        }
        res += Math.min(c , d);
        res += s.length() - 2 * (Math.min(c , d));

        return res;


    }

  

思路2:更为简单的方法,分别计算不翻转时,A为0,B为1的位数a,A为1,B为0的位数b,以及翻转之后A为0,B为1的位数c,A为1,B为0的位数d。最后的结果其实就是min(max(a,b),max(c,d)+1)。举个例子:max(a,b)=a,这意味着只要进行b次的交换,和a-b次的变换即可。反转之后一样的,但是需要加上反转的1。

public static int process(String stra,String strb){
		int a=0,b=0,c=0,d=0;
		for(int i=0;i<stra.length();i++){
			
		if((stra.charAt(i)!=strb.charAt(i))&&(stra.charAt(i)=='1')) 
				a++;		
		if(stra.charAt(i)!=strb.charAt(i)&&stra.charAt(i)=='0') 
				b++;
		if(stra.charAt(stra.length()-1-i)!=strb.charAt(i)&&stra.charAt(i)=='1') 
				c++;
		if(stra.charAt(stra.length()-1-i)!=strb.charAt(i)&&stra.charAt(i)=='0') 
				d++;	
		}
		
		return Math.min(Math.max(a,b), Math.max(c,d)+1);
	}

相对来说这种方法就简单多了。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。