Программа двоичного разрыва на Java

Question

Моя постановка задачи:

Двоичный пробел в положительном целом числе N - это любая максимальная последовательность последовательных нулей, которая окружена единицами на обоих концах в двоичном представлении N. Например, число9 имеет двоичное представление 1001 и содержит двоичный пробел длины 2. Число 529 имеет двоичное представление 1000010001 и содержит два двоичных пробела: один длины 4 и один длины 3. Число 20 имеет двоичное представление 10100 и содержит один двоичный разрывдлина 1. Число 15 имеет двоичное представление 1111 и не имеет двоичных пробелов.Число 32 имеет двоичное представление 100000 и не имеет двоичных пробелов.

Мой код:

public class Abc {

    static void decToBinary(int n) {

        int[] binaryNum = new int[1000];

        // counter for binary array 
        int i = 0;
        while (n > 0) {
            // storing remainder in binary array 
            binaryNum[i] = n % 2;
            n = n / 2;
            i++;
        }
        int ctr = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<Integer>();

        // printing binary array in reverse order 
        for (int j = i - 1; j >= 0; j--) {
            System.out.print(binaryNum[j]);
            if (binaryNum[j] == 0) {
                k = j;
                do {
                    ctr++;
                    k++;
                } while (binaryNum[k] == 0);
                al.add(ctr);
                ctr = 0;
            }
        }

        for (int ii = 0; ii < al.size(); ii++) {
            System.out.println(al.get(ii));
        }
    }

    // driver program 
    public static void main(String[] args) {
        int n = 1041;
        decToBinary(n);
    }
}

Я пытаюсь показать вывод двоичного пробела, который хранится в моем ArrayList,Но выходные данные совершенно различны для данного ввода 1041. Я не знаю, почему он хранит 1,2,3,4;согласно моей логике он должен хранить только значения разрыва 5 и 3 в случае ввода: 1041, хотя 5 и 3 также хранятся в ArrayList, но с некоторым другим индексом.

Я думаю, что есть проблемав цикле do-while, особенно в al.add(ctr), но я еще не понял этого.

Answer 1

Попробуйте следующие коды,

public int solution(int n) {
    String binaryString = Integer.toBinaryString(n);
    int count = 0, bigGap = 0, temptCount = 0;
    for (int i = 0; i < binaryString.length(); i++) {
        char c = binaryString.charAt(i);
        if (c == '0') {
            temptCount++;
        } else {
            count = temptCount;

            if (count > bigGap) {
                bigGap = count;
            }
            temptCount = 0;
        }

    }

    return bigGap;
}

Answer 2

// работает на 100% со всеми тестами

public static void main(String ar[]) {
        Integer val = 10092;
        String vals = val.toBinaryString(val);
        int gapVal = findBinaryGap(vals);
        System.out.println(vals);
        System.out.println("gapVal=" + gapVal);

    }

public static Integer findBinaryGap(String binVal) {
        Integer retVal = 0;
        String splitVal[] = binVal.split("1");
        int endVal = splitVal.length;
        if (binVal.endsWith("0")) {
            endVal = endVal - 1;
        }
        for (int incr = 0; incr < endVal; incr++) {
            if (retVal < splitVal[incr].length()) {
                retVal = splitVal[incr].length();
            }
        }
        return retVal;
    }

Answer 3

var k также должно быть уменьшено, потому что j уменьшается, также после завершения итерации вы должны назначить j = k.и вы должны проверить, больше ли k или равно нулю while (k >= 0 && binaryNum[k] == 0);, в противном случае вы получите ArrayIndexOutOfBoundsException.также вы должны проверить, если k меньше нуля, чтобы правильно считать двоичные пробелы if(k < 0) {j = k;break;}

  for (int j = i - 1; j >= 0; j--) {
        System.out.print(binaryNum[j]);
        if (binaryNum[j] == 0) {
            k = j;
            do {
                ctr++;
                k--;
            } while (k >= 0 && binaryNum[k] == 0);
            if(k < 0) {
                j = k;
                break;
            }
            al.add(ctr);
            ctr = 0;
            j = k;
        }
    }

Answer 4

Я получил идеальные 100 с этим ответом.Надеюсь, что это поможет вам.

public int solution(int N) {
        String binary = Integer.toBinaryString(N);
        int count = 0;
        int tmpCount = 0;
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '0') {
                if (i > 0 && binary.charAt(i - 1) == '1') {
                    tmpCount++;
                } else {
                    if (tmpCount > 0) tmpCount++;
                }
            } else if (binary.charAt(i) == '1') {
                if (tmpCount > 0 && tmpCount > count) {
                    count = tmpCount;
                }
                tmpCount = 0;
            }
        }
        return count;
    }

Answer 5

Если это домашнее задание, ваша проблема здесь:

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            k = j;
            do {
                ctr++;
                k++;
            } while (binaryNum[k] == 0);
            al.add(ctr);
            ctr = 0;
        }
    }

Обратите внимание:

• Вы обновляете k по мере продвижения, но вы этого не делаетеобновите j, чтобы вы получали 1 через любое правильное значение ([1, 2, 3, 4, 5, 1, 2, 3] вместо [5, 3]).
• Вам вообще не нужно k.

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            int ctr = 0;
            while (binaryNum[j] == 0) {
                ctr++;
                j--;
            }
            al.add(ctr);
        }
    }

Здесь показано .

---

Если вы не делаете это для домашней работы и вам нужна производительность для реального использования, используйте Javaвстроенные побитовые методы в Integer классе , которые используют очень и очень быстрые инструкции CPU для процессоров, у которых они есть:

import java.util.Arrays;

public class Abc {
    static final int[] gaps(int n) {
        final int[] untrimmedResult = new int[15];
        int i = 0;

        // Remove trailing zeroes and last one bit to get to first gap.
        n >>>= Integer.numberOfTrailingZeros(n) + 1;
        while (n != 0) {
            final int gapSize = Integer.numberOfTrailingZeros(n);
            untrimmedResult[i++] = gapSize;
            n >>>= gapSize + 1;
        }

        final int[] result = new int[i];
        System.arraycopy(untrimmedResult, 0, result, 0, i);
        return result;
    }

    // driver program 
    public static void main(final String[] args) {
        final int n = 1041;
        System.out.println(Integer.toBinaryString(n));
        System.out.println(Arrays.toString(gaps(n)));
    }
}

Это , показанное здесь для работы, хотя это дает результаты в обратном порядке (что можно легко исправить, заполнив untrimmedResult в обратном порядке и правильно настроив аргументы System.arraycopy).