Вопрос:

Является ли мой код для решения Binary Gap правильным или нет? Что я должен улучшить в этом?

java optimization challenge-response

5372 просмотра

13 ответа

63 Репутация автора

Двоичный пробел в положительном целом числе N - это любая максимальная последовательность последовательных нулей, которая окружена единицами на обоих концах в двоичном представлении N.

Например, число 9 имеет двоичное представление 1001 и содержит двоичный пробел длины 2. Число 529 имеет двоичное представление 1000010001 и содержит два двоичных пробела: один из длины 4 и один из длины 3. Число 20 имеет двоичное представление 10100 и содержит один двоичный пробел длины 1. Число 15 имеет двоичное представление 1111 и не имеет двоичных пробелов.

Напишите функцию:

int решение (int N); что, учитывая положительное целое число N, возвращает длину самого длинного двоичного разрыва. Функция должна вернуть 0, если N не содержит двоичный пробел.

Например, учитывая N = 1041, функция должна возвращать 5, потому что N имеет двоичное представление 10000010001 и поэтому самый длинный двоичный пробел имеет длину 5.

public int solution(int n) {
        // write your code in Java SE 8
        String binaryRep = Integer.toBinaryString(n);
        System.out.println("Binary Representation of " + n + " = " + binaryRep);
        List<String> strList = new ArrayList<String>();
        int count = 0;
        for (int i = 0; i < binaryRep.length(); i++) { // Loop through the each number 
            String str = binaryRep.charAt(i) + ""; // getting one by one number
            if(str.equals("0")){
                for(int j = i;j<binaryRep.length();j++){ //Get each next element
                    String str1 = binaryRep.charAt(j) + "";
                    if(!str.equals("1") &&  str.equals(str1)){
                        if(!strList.isEmpty() && count >= strList.size()){
                            strList.add(str1);
                        }else if(strList.isEmpty()){
                            strList.add(str1);
                        }
                        count ++; 
                    }else{
                        count = 0;
                        break;
                    }
                }
           }   
        }
        return strList.size();
    }
Автор: Vimal Panchal Источник Размещён: 03.12.2016 09:00

Ответы (13)


1 плюс

3489 Репутация автора

Нет необходимости помещать содержимое двоичной строки в массив (если, конечно, это не является обязательным требованием), просто перебирайте саму строку и используйте метод String.substring (), чтобы извлечь значение каждой двоичной цифры, представленное в строке , как в:

String digit = binaryString.substring(i, i+1);

Все сводится к подсчету числа 0 между любым набором 1 и отслеживанию этих 0 с использованием переменной типа данных Integer, которая увеличивается каждый раз, когда встречается 0. Эта же переменная сбрасывается в 0 каждый раз, когда встречается 1, но перед ее сбросом вы бы сравнили ее с еще одной предопределенной целочисленной переменной, которая будет содержать самый длинный цикл из 0 встречаемых, например:

if(binaryString.substring(i, i+1).equals("1")) {
    if (zeroHit > longest) { longest = zeroHit; }
    zeroHit = 0;
}
else { zeroHit++; }

Весь метод может выглядеть примерно так:

private static int solution(int intValue) {
    String binaryString = Integer.toBinaryString(intValue);
    int zeroHit = 0;
    int longest = 0;
    for (int i = 0; i < binaryString.length(); i++) {
        if(binaryString.substring(i, i+1).equals("1")) {
            if (zeroHit > longest) { longest = zeroHit; }
            zeroHit = 0;
        }
        else { zeroHit++; }
    }
    return longest;
}
Автор: DevilsHnd Размещён: 03.12.2016 10:52

3 плюса

85 Репутация автора

Решение

Я еще не тестировал ваш код, но он кажется очень неэффективным, если ваша цель - просто подсчитать самый длинный «двоичный разрыв».

Проблемы в вашем коде:

  • Делает, java.lang.Stringкогда это может быть просто char. Создание объектов намного медленнее, чем создание примитивных типов.
  • Составляет список, когда он может просто считать. Если вам нужен только размер списка, вы можете просто посчитать его в целочисленной переменной.
  • Глупый алгоритм. Подстрока строки не может быть длиннее исходной. Я говорю о втором forцикле. Например, предположим, вы считаете двоичный разрыв 1001. Тогда ваш алгоритм считает двоичный разрыв 001и затем 01. Вам не нужно считать второй вообще. И это происходит потому, что у вас есть две петли.

Самая большая проблема заключается в том, что эту проблему можно решить, не переходя ни intв какие java.lang.String. И если вы столкнулись с этой проблемой из учебника, я считаю, что это «правильный» ответ: использовать побитовые операторы.

public static int solution(int num) {
    int ptr; //Used for bitwise operation.
    for(ptr=1; ptr>0; ptr<<=1) //Find the lowest bit 1
        if((num&ptr) != 0)
            break;
    int cnt=0; //Count the (possible) gap
    int ret=0; //Keep the longest gap.
    for(; ptr>0; ptr<<=1) {
        if((num&ptr) != 0) { //If it's bit 1
            ret = cnt < ret ? ret : cnt; //Get the bigger one between cnt and ret
            cnt=-1; //Exclude this bit
        }
        cnt++; //Increment the count. If this bit is 1, then cnt would become 0 beause we set the cnt as -1 instead of 0.
    }
    return ret;
}
Автор: minary Размещён: 03.12.2016 11:01

1 плюс

1344 Репутация автора

Вот мое скромное решение. Теперь я вижу, что это похоже на модификацию ответа DevilsHnd. Я проверял это

public int countZeros(int n) {
        String binaryRep = Integer.toBinaryString(n);
        char[] nChars = binaryRep.toCharArray();
        int nElemLength = Math.min(binaryRep.lastIndexOf('1') + 1, nChars.length);
        if (nElemLength <= 2) {
            return 0;
        }
        String[] elementsParts = binaryRep.substring(0, nElemLength).split("1");
        int zeroLength = 0;
        for (String elementsPart : elementsParts) {
            if (elementsPart.length() > zeroLength) {
                zeroLength = elementsPart.length();
            }
        }
        return zeroLength;
    }
Автор: BlackRainbow Размещён: 28.09.2017 02:24

0 плюса

6 Репутация автора

Я думаю, что ваш код немного сбивает с толку, проверьте этот.

public int solution(int n) {
    if (n <= 0) return 0;
    char[] chars = Integer.toBinaryString(n).toCharArray();
    ArrayList<Integer> arrayList = new ArrayList<>();
    int maxCount = 0;
    for (int i = 0; i < chars.length; i++) {
        while (chars[i] == '0' && i + 1 < chars.length) {
            maxCount++;
            i++;
            if (i + 1 == chars.length && chars[i] == '0')
                maxCount = 0;
        }
        if (maxCount != 0)
            arrayList.add(maxCount);
        maxCount = 0;
    }

    return arrayList.isEmpty() ? 0 : Collections.max(arrayList);
}
Автор: Mario_1412 Размещён: 17.01.2018 09:52

1 плюс

907 Репутация автора

Как насчет этого алгоритма. Это плохо для времени или хорошо?

int count = 0, prevCount = 0;

while (a > 1) {

  if (a % 2 == 0) {
     count++;
     if (count > prevCount)
        prevCount++;
     } else {
            count = 0;
        }    
        a = a/2;
    }

    if(a % 2 == 0)
       prevCount++;
Автор: Hafiz Waleed Hussain Размещён: 24.03.2018 08:26

0 плюса

1 Репутация автора

Привет, это мое решение для этой задачи. У меня была оценка задачи: 100% Корректность: 100%

public int solution(int N) {
    String binary = Integer.toBinaryString(N);
    int[] table = new int[binary.length()];

    for (int i=0;i<binary.length();i++){
        int number = Integer.parseInt(binary.substring(i,i+1));
        table[i] = number;
    }

    int resu = 0;
    int res = 0;
    for (int i=0;i<table.length;i++){
        if (table[i] == 1){
            if (resu > res){
                res = resu;
            }
            resu = 0;
        }else {
            resu++;
        }
    }

    return res;
}
Автор: Mr Sadman Размещён: 19.04.2018 08:46

0 плюса

336 Репутация автора

Для всеобщего блага, вот мое решение двоичного разрыва, которое принесло мне 100% как за оценку задания, так и за правильность задания:

class Solution {
    public int solution(int N) {
        String nStr = Integer.toBinaryString(N);

        boolean isCounting = false;
        int j=0;
        int[] seqs = new int[32];
        for (int i=0; i<nStr.length(); i++)
        {
            if ( nStr.charAt(i) == '1')
            {
                if (!isCounting)
                {
                    isCounting = true;
                    seqs[j] = 0;
                }
                else // isCounting, turn it off
                {
                    isCounting = false;
                    j++;
                }

            }
            else // nStr.charAt(i) == '0'
            {
                if (!isCounting)
                    isCounting = true;
                seqs[j]++;
            }

        }
        if (isCounting == true)
            seqs[j] = 0;

        int maxGap = 0;
        for (int k=0; k<seqs.length; k++)
            if (seqs[k] > maxGap)
                maxGap = seqs[k];
        return maxGap;
   }
}
Автор: Very Objective Размещён: 09.08.2018 05:05

0 плюса

11 Репутация автора

РЕШЕНИЕ ОБЪЕКТИВА C (n)

Результаты, данные Codility

Оценка задачи: 100%
Корректность: 100%
Производительность: Не выполнено

Сложность времени

Наихудшая временная сложность O (n)

Алгоритм Объяснение

ФАКТЫ

Каждый действительный разрыв начинается с «1» и заканчивается другим «1», по крайней мере, с одним «нулем» между ними.

  • 1001 - Действительный разрыв
  • 00100 - Недопустимый пробел
  • 10100 - это действительный пробел
  • 11111 - Недействительный пробел

ШАГ 1

  • Получить представление битов по одному от Rigth слева.

  • Это означает, что при n = 4 я получу сначала ноль, затем еще один ноль, затем единицу, наконец ноль. [0,1,0,0]

  • 4 -> 0100

ШАГ 2

  • Начните искать первое «1» - поскольку наш флаг «hasStartPattern» имеет значение «ложь» в первой итерации, мы будем искать первое вхождение «1», это означает, что у нас есть допустимый стартовый шаблон, и мы меняем флаг «hasStartPattern» 'true для следующих итераций, мы должны проверить, является ли текущий бит' 0 ', и использовать счетчик, в данном случае' кандидатов '.

  • Только если во входных битах есть еще один «1», мы уверены, что у нас есть допустимый двоичный пробел, тогда мы сравниваем наших предыдущих «кандидатов» с нашим текущим «gapCounter», чтобы сохранить самый высокий.

  • В случае, если нет другого «1», чтобы закрыть разрыв, мы никогда не меняем значение «gapCounter» и возвращаем 0

Решение XCode здесь

-(int)solutionOne:(int)n {

    BOOL hasStartPattern = NO;
    int candidates = 0;
    int gapCounter = 0;

    while(n){
        // STEP 1
        NSString *bit = (n & 1) ? @"1": @"0";
        n /= 2;

        // STEP 2
        if ( hasStartPattern  && [bit isEqualToString:@"0"]) {
            candidates++;
        }
        else if ( hasStartPattern  && [bit isEqualToString:@"1"]) {
            // At least one '1' exist as a close pattern
            if (candidates > gapCounter) {
                gapCounter = candidates;
            }
            candidates = 0;
        }
        else if ([bit isEqualToString:@"1"]) {
            hasStartPattern = YES; // At least one '1' exist as an open pattern
        }
    }
    return gapCounter;
}
Автор: Manuel Mosso Размещён: 09.11.2018 10:09

0 плюса

11 Репутация автора

ОБЪЕКТИВ-C РЕШЕНИЕ O (2n)

Результаты, данные Codility

Оценка задачи: 100%
Корректность: 100%
Производительность: Не выполнено

Сложность времени

Наихудшая временная сложность O (2n)

Алгоритм Объяснение

ФАКТЫ

Каждый действительный разрыв начинается с «1» и заканчивается другим «1», по крайней мере, с одним «нулем» между ними.

  • 1001 - Действительный разрыв
  • 00100 - Недопустимый пробел
  • 10100 - это действительный пробел
  • 11111 - Недействительный пробел

ШАГ 1

  • Получить биты n, используя вспомогательный метод, который имеет O (n) сложность

ШАГ 2

  • Итерируйте по каждому биту, который мы получили в первом шаге
  • Начните искать первое «1» - поскольку наш флаг «hasStartPattern» имеет значение «ложь» в первой итерации, мы будем искать первое вхождение «1», это означает, что у нас есть допустимый стартовый шаблон, и мы меняем флаг «hasStartPattern» 'true для следующих итераций, мы должны проверить, является ли текущий бит' 0 ', и использовать счетчик, в данном случае' кандидатов '.
  • Только если во входных битах есть еще один «1», мы уверены, что у нас есть допустимый двоичный пробел, тогда мы сравниваем наших предыдущих «кандидатов» с нашим текущим «gapCounter», чтобы сохранить самый высокий.
  • В случае, если нет другого «1», чтобы закрыть разрыв, мы никогда не меняем значение «gapCounter» и возвращаем 0.

Решение XCode здесь

+(int)solutionTwo:(int)n {    
    // STEP 1
    // O(n)
    NSString *bits = [self getBitsForNumber:n];

    BOOL hasStartPattern = NO;
    int candidates = 0;
    int gapCounter = 0;

    // STEP 2
    // O(n)
    for (int i=0; i < bits.length; i++) {

        char currentBit = [bits characterAtIndex:i];

        if ( hasStartPattern  && currentBit == '0' ) {
            candidates++;
        }
        else if ( hasStartPattern  && currentBit == '1' ) {
            // At least one '1' exist as a close pattern
            if (candidates > gapCounter) {
                gapCounter = candidates;
            }
            candidates = 0;
        }
        else if (currentBit == '1') {
            hasStartPattern = YES; // At least one '1' exist as an open pattern
        }

    }

    return gapCounter;
}

/*
Time Complexity:
- The worst case time complexity for this auxiliary method is O(n)
*/
+(NSString*)getBitsForNumber:(int)n {
    NSMutableString *bits = [NSMutableString string];
    while(n) {
        [bits insertString:((n&1)? @"1" : @"0") atIndex:0];
        n /= 2;
    }
    return bits;
}
Автор: Manuel Mosso Размещён: 09.11.2018 11:27

0 плюса

1 Репутация автора

вот мое решение.

Это 100/100.

Я думаю, что это может быть отполировано, хотя.

    class Solution {
      public int solution(int N) {

       String s = Integer.toBinaryString(N);
       int ctr = 0;

       for (int x = 0; x < s.length(); x++){

           if (s.substring(x,x+1).equals("1")){

               ctr++;
           }

       }


       int result[] = new int[ctr];

       boolean flag = false;
       int fCtr = 0;
       for(int y = 0; y < s.length(); y++){
           if(s.substring(y,y+1).equals("1")){
               flag = true;
               if(flag == true){
                    fCtr++;
               }

               }
           else if (s.substring(y,y+1).equals("0") && flag == true && fCtr < ctr){
               result[fCtr]++;
           }
         } 

        int ans = 0;
        for (int d = 0; d < result.length; d++){
            if (ans <= result[d]){
                ans = result[d];
            }
        }

       return ans;
    }
}
Автор: benjamin palma Размещён: 22.02.2019 04:54

0 плюса

1 Репутация автора

В интересах всех, вот мое решение для Binary Gap, которое дало мне 100% как за оценку задачи, так и за корректность задачи в c #:

class Solution
{
    public int solution(int num)
    {

        int countZero = 0;
        bool flag = false;
        int temp = 0;

        /*
        1- first converte num result to binary form
        2- count the number of '0' 
        */

        while (num != 0)
        {
            if (num % 2 == 1)
            {
                flag = true;
                if (temp > countZero)
                {
                    countZero = temp;
                }
                temp = 0;
            }
            else
            {
                if (flag)
                {

                    temp++;
                }
            }
            num = num / 2;
        }
        return countZero;
    }
}
Автор: Nour Qweder Размещён: 08.04.2019 09:42

0 плюса

35 Репутация автора

Я думаю, что это очень маленький код

    public int solution(int N)
    {
        string binary = Convert.ToString(N, 2);
        binary = binary.TrimEnd(new Char[] { '0' });
        var gaps = binary.Split('1');
        int max = 0;
        foreach (var item in gaps)
        {
            if (!string.IsNullOrEmpty(item))
                if(item.Length > max)
                   max = item.Length;
        }            
        return max ;
    }
Автор: user1445018 Размещён: 13.06.2019 05:31

0 плюса

31 Репутация автора

здесь мой

public int solution(int N) {

    String binary = Integer.toBinaryString(N);

    LinkedList<Integer> gaps = new LinkedList<>();
    int countGap = 0;
    int j = 0;
    for (int i = 1; i < binary.length() - 1; i++) {
        if (binary.charAt(i) == '0') {
            countGap++;
        } else {

            gaps.add(j, countGap);
            j++;
            countGap = 0;
        }
    }

    gaps.add(j, countGap);

    if (binary.charAt(binary.length() - 1) == '0') {
        gaps.set(gaps.size() - 1, 0);
    }

    Collections.sort(gaps);

    return gaps.getLast();
}
Автор: Iryna Prokopenko Размещён: 16.07.2019 07:39
Вопросы из категории :
32x32