Сложность пространства "сложить два двоичных строк" бросают вызов


Я решал эту проблему ", добавив две строки двоичных чисел" и придумал следующий алгоритм. Я пытаюсь анализировать свое время и сложность пространства. В то время как я был доволен его временная сложность, которая \$О(П)\$, Я не уверен, о пространстве. Я думаю, что пространство сложность \$О(П)\$, а также, но я могу ошибаться из-за StringBuilder использование здесь.

public String sumOfBinary(String x, String y) {
    if((x.length == 0 && y.length == 0) || (x == null && y == null)) 
       return;

    int i = x.length - 1, j = y.length - 1, carry = 0;
    StringBuilder sb = new StringBuilder();

    while(i > = 0 || j >= 0) {
     int sum = carry;
     if(i >= 0) {
       sum+= x.charAt(i--) - '0';
     }
     if(j>=0) {
       sum+=y.charAt(j--) - '0';
     }

     sb.append(sum%2);
     carry = sum/2;

    }
    if(carry!=0) {
      sb.append(carry);
    }
   return sb.reverse().toString();
}

Было бы здорово, если кто-нибудь может проверить код и дайте мне знать, если есть какие-либо другие лучший способ сделать это, наряду с тем, что сложности в алгоритм.



325
0
задан 27 января 2018 в 10:01 Источник Поделиться
Комментарии
2 ответа

Вот несколько пунктов, чтобы рассмотреть.

Проверка на пустую строку и null представляется излишним. Компилятор рассматривает их то же самое.

Ваша проверка на null, только проверяет, если оба null. Для завершения лучше было бы также проверить, если значение null.

Я думаю, что было бы более эффективным, чтобы использовать массив типа char значение максимальной длины(длина самой длинной строки плюс 1) и измените значение на каждый индекс, а не постоянно добавляя в StringBuilder.

Вы не проверять строки искаженной.

Вы не работа со строками разной длины.

Со всеми этими учитывается ваш код может выглядеть примерно так:

final static char ZERO_CHAR_VALUE = '0';
final static char ONE_CHAR_VALUE = '1';
final static char DEFAULT_CHAR_VALUE = '\0';

public static String AddBinary(String inValA, String inValB) {
if (inValA == null) {
if (inValB == null) {
return null;
}
return inValB;
}
if (inValB == null) {
return inValA;
}
int aIndex = inValA.length() - 1;
int bIndex = inValB.length() - 1;
int longestLength = Math.max(aIndex, bIndex) + 2;
char[] tempOutVal = new char[longestLength];
int tempOutIndex = tempOutVal.length - 1;
char aTemp;
char bTemp;
for (; aIndex >= 0 && bIndex >= 0; aIndex--, bIndex--, tempOutIndex--) {
aTemp = inValA.charAt(aIndex);
BinaryCharValidator(aTemp, inValA);
bTemp = inValB.charAt(bIndex);
BinaryCharValidator(bTemp, inValB);
SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
}
if (aIndex >= 0) {
for (; aIndex >= 0; aIndex--, tempOutIndex--) {
aTemp = inValA.charAt(aIndex);
BinaryCharValidator(aTemp, inValA);
bTemp = ZERO_CHAR_VALUE;
SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
}
}
if (bIndex >= 0) {
for (; bIndex >= 0; bIndex--, tempOutIndex--) {
aTemp = ZERO_CHAR_VALUE;
bTemp = inValB.charAt(bIndex);
BinaryCharValidator(bTemp, inValB);
SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
}
}
return new String(tempOutVal);
}

public static void SetValue(char aVal, char bVal, char[] outVal, int outIndex) {
if (outVal[outIndex] == DEFAULT_CHAR_VALUE) {
outVal[outIndex] = ZERO_CHAR_VALUE;
}
int aTemp = aVal - ZERO_CHAR_VALUE;
int bTemp = bVal - ZERO_CHAR_VALUE;
int outTemp = outVal[outIndex] - ZERO_CHAR_VALUE;
int sum = aTemp + bTemp + outTemp;
outVal[outIndex] = (char) ((sum % 2) + ZERO_CHAR_VALUE);
if (sum > 1) {
outVal[outIndex - 1] = ONE_CHAR_VALUE;
} else {
outVal[outIndex -1] = ZERO_CHAR_VALUE;
}
}

public static void BinaryCharValidator(char toCheck, String input) {
if (!(toCheck == ZERO_CHAR_VALUE || toCheck == ONE_CHAR_VALUE)) {
throw new IllegalArgumentException(String.format("Malformed string(only 1's and 0's allowed). The string is \"%s0\"", input));
}
}

1
ответ дан 30 января 2018 в 04:01 Источник Поделиться

Я согласен с вами, пространство сложность должна быть \$О(П)\$, используя StringBuilder не имеет значения, потому что внутренне он будет хранить char в массив, который будет расширяться / сокращаться по мере необходимости.

Теперь какой-то код-отзывы.

Проверить ошибки:


  1. Нулевой чек? x или y может быть null. Это (x == null || y == null) выглядит лучше.

  2. Ваш код говорит "sumofbinary"но что если ваша строка была "123" + "543"?

Проверьте имя:


  1. sb не профессиональное название, назовем его sum.

Проверьте синтаксис:


  1. while(i > = 0 || j >= 0) .. есть пространство > = для i > = 0но не для j.

Разное:


  1. StringBuilder могут быть отмечены final.

  2. Вы конце цикла, когда оба i & j являются 0. Это имеет недостаток, если i больше, чем jвы сэкономите об ошибке проверки, если (к > 0).

2
ответ дан 29 января 2018 в 03:01 Источник Поделиться