Ссылка → https://leetcode.com/problems/add-binary/

Проблема: →

Имея две двоичные строки a и b, верните их сумму в виде двоичной строки.

Пример 1:

Input: a = "11", b = "1"
Output: "100"

Пример 2:

Input: a = "1010", b = "1011"
Output: "10101"

Ограничения:

  • 1 <= a.length, b.length <= 104
  • a и b состоят только из символов '0' или '1'.
  • Каждая строка не содержит ведущих нулей, кроме самого нуля.

Решение: →

Давайте сначала разберемся, как работает добавление бинарных файлов

Двоичное сложение намного проще, чем десятичное сложение, если вы помните следующие приемы или правила. Используя эти правила, можно легко сложить любое двоичное число. Четыре правила двоичного сложения:

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 =10

Давайте посмотрим пример,

В двоичном сложении мы будем проходить справа налево

Итак, согласно правилам,

→ 0 + 0 будет 0

→0 + 1 становится 1

→ 1 + 1 становится 10, здесь не осталось ни одного бинарного элемента, иначе он станет переносом.

Поняв, как работает двоичное сложение, давайте разберемся, как сложение двоичного кода достигается в программировании.

Например, мы дали две строки: a = «010», b = «110».

Здесь мы начнем читать каждый символ справа налево, так как двоичное сложение работает справа налево.

Здесь мы также должны заметить, что длина a и b может быть различной, поэтому нам нужно пройти на основе наибольшей длины, а также мы поставим условие, если позиция любой строки станет -1 (поскольку мы обход справа налево), то после этого мы не будем выполнять никаких операций с этой строкой, чтобы предотвратить ошибку.

Итак, наши первые две строки кода,

Теперь мы переходим к следующему шагу и делаем нашу первую итерацию.

Давайте сначала разберемся,

Здесь, поскольку мы выполняем математическую операцию, java автоматически преобразует char в Int.

Символ «0» → 48 (целое число)

Символ «1» → 49 (Int)

Итак, здесь будет «0» — «0» => 48–48 => 0

Здесь, согласно оператору postfix (++ или — ), сначала будет выполнена операция, а затем значение будет уменьшено на 1.

Итак, здесь сначала будет выполнен a.charAt(2), а затем будет выполнен декремент, поэтому после успешного выполнения a.charAt(2) значение aLength уменьшилось на 1,

Теперь, как и в предыдущих шагах, мы будем вычислять с помощью b.

Итак, здесь будет сумма => ‘0’ — ‘0’ => 48–48 => 0

Теперь, следующий шаг, результат — это StringBuilder, и мы добавляем значение к 0-й позиции результата →

0-я позиция результата → сумма % 2 =› 0 % 2 =› 0

Следующим шагом перенос будет (sum/2) =› 0/2 =› 0.

Теперь, следующая итерация,

сумма = перенос = 0

Символ «1» → 49 (Int)

Итак, здесь это будет сумма => сумма + «1» — «0»

=› сумма + 49–48 =› сумма + 1,

so,

сумма = 0 + 1 =› 1

Теперь для b:

Символ «1» → 49 (Int)

Итак, здесь будет сумма = сумма + (‘1’ — ‘0’)

=› сумма+ 49–48 =› сумма + 1,

so,

сумма = 1+ 1 =› 1

Здесь также значение aLength будет уменьшено на 1.

Также bLength будет уменьшен на 1.

Теперь мы вставляем значение в 0-ю позицию результата.

Теперь перенос = 2 / 2 → перенос = 1

перенос = 1, поэтому сумма = перенос → сумма = 1

Здесь Char ‘0’ → 48 (Int)

Итак, здесь будет «0» — «0» => 48–48 => 0,

so,

сумма =сумма +(0 + 0)=›1 + 0 =›1

Теперь для b:

его значение равно -1, поэтому условие не выполнено, а значение aLength будет уменьшено на 1.

длина = (длина -1) = (0–1) = -1

Теперь мы вставляем значение в 0-ю позицию результата.

сумма%2 => 1%2 => 1

Теперь для переноски:

перенос = (сумма / 2) => 1/2 => 0

Теперь мы выйдем из цикла while, так как условие станет FAIL.

После цикла while нам нужно только одно условие для переноса.

Прямо сейчас мы получили carry = 0, но если мы получим carry = 1, нам снова нужно добавить это к результатам.

Предположим, если я возьму другой пример, где последним carry будет 1.

Как и ниже, мне нужно добавить 1 к последнему результату

Теперь давайте проверим весь исходный код.

Код (Java): →

Код (Питон): →

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

Мы обходим весь массив (справа налево), пока не найдем место, поэтому временная сложность будет O(n).

Космическая сложность

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

Спасибо, что прочитали эту статью ❤

Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.

Хлопайте 👏 Если вам поможет эта статья.