计算二进制数的最小交换,这里 N 是偶数,0 和 1 的数量相等

问题描述 投票:0回答:0

You are given the following:
    An Integer N
    A binary string S of length N×N
N is always even and string S has an equal number of 0's and 1's. You are allowed to swap any two elements S[i] and S[j] (0≤i ≠j<N×N) of string S.
Task
Determine the minimum number of swaps required to be done on string S such that the following conditions hold true for the entire string.
    If (i+1)  mod N-(i)  mod N=1, then (S[i+1]+S[i])=1 for (0≤i<N×N-1).
    If i+N<N×N, then (S[i+N]+S[i])=1.
Note
    Assuming 0 based indexing.
Example
Assumptions
    N=2
    String S="1010"
Approach
Swapping indices 0 and 1, we get string S ="0110",
String S="0110" satisfies all the conditions, Hence answer is 1.
Function description

这里输入有两个参数 N 是一个整数,S 是长度为 N 交叉 N 的二进制字符串

对于输入N=2,字符串S=0011输出为1;

public class MinimumSwap {
    public static void main(String[] args) {
        // 0123
        String s = "101010101010";
        int N = 6;
//       String st = "00110011";
        if (N % 2 == 0) {
            System.out.println(countMinSwaps(s, N));
        }

    }

    static int countMinSwaps(String s, int N) {
        char[] ch = s.toCharArray();
        int count = 0;
        
        for (int i = 0; i < (N + N) - 1; i++) {
            if (i + 1 % N - (i) % N == 1) {
                int x = ch[i + 1] - '0';
                int y = ch[i] - '0';
                if(x + y != 1) {
//              char temp = ch[i];
//              ch[i] = ch[i + 2];
//              ch[i + 2] = temp;
                count++;
                }
            } if (i + N < N + N) {
                int p = ch[i + N] - '0';
                int q = ch[i] - '0';
                if ( p + q != 1) {
//                  char temp = ch[i];
//                  ch[i] = ch[i + 1];
//                  ch[i + 1] = temp;
                    count++;
                }
            }
        
        }
        return count;
    }

我试图解决我一直在理解问题,比如 N=2、S=1010 这样的输入 为了满足第二个条件,他们交换了索引 0 和 1,因此输出为 0110,即 i=0 和 N=2。 现在我增加了 i=1, s[i]=1 和 s[i+1]=1(这里我满足这个条件 i + 1 % N - (i) % N == 1 )其中第一个条件不满足ryt 那为什么不交换。

我换对了吗??

java binary swap
© www.soinside.com 2019 - 2024. All rights reserved.