0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>12 окт 2022</li>
2
<ul><li>12 окт 2022</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: сложить двоичные числа, представленные в виде строк</h2>
4
</ul><h2>Задача: сложить двоичные числа, представленные в виде строк</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня складываем двоичные числа.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня складываем двоичные числа.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Даны два двоичных числа в виде строк a и b. Нужно вернуть их суммы в виде строки.</p>
8
<p><strong>Условие.</strong>Даны два двоичных числа в виде строк a и b. Нужно вернуть их суммы в виде строки.</p>
9
Ввод: a = "11", b = "1" Вывод: "100" Ввод: a = "1010", b = "1011" Вывод: "10101"<p><strong>Решение</strong></p>
9
Ввод: a = "11", b = "1" Вывод: "100" Ввод: a = "1010", b = "1011" Вывод: "10101"<p><strong>Решение</strong></p>
10
<p>Чтобы решить эту задачу, мы должны начать с конца и посимвольно складывать цифры. Создадим два указателя - для каждой из строк. На старте они будут ссылаться на последние символы строк. Теперь просто пойдём с конца строк к началу, уменьшая значения указателей на один.</p>
10
<p>Чтобы решить эту задачу, мы должны начать с конца и посимвольно складывать цифры. Создадим два указателя - для каждой из строк. На старте они будут ссылаться на последние символы строк. Теперь просто пойдём с конца строк к началу, уменьшая значения указателей на один.</p>
11
<p>Главная проблема здесь - не забыть о числах, которые переносятся в следующий разряд. А ещё нужно помнить, что одна строка может быть длиннее другой. В этом случае придётся добавить оставшиеся символы из более длинной строки к результату.</p>
11
<p>Главная проблема здесь - не забыть о числах, которые переносятся в следующий разряд. А ещё нужно помнить, что одна строка может быть длиннее другой. В этом случае придётся добавить оставшиеся символы из более длинной строки к результату.</p>
12
<p>Чтобы работать со строками было удобно, я использовал StringBuilder. В Java это самый эффективный способ для операций на изменение строк.</p>
12
<p>Чтобы работать со строками было удобно, я использовал StringBuilder. В Java это самый эффективный способ для операций на изменение строк.</p>
13
<p>Вот как алгоритм будет реализован на Java:</p>
13
<p>Вот как алгоритм будет реализован на Java:</p>
14
public String addBinary(String aa, String bb) { char[] aChars = aa.toCharArray(); char[] bChars = bb.toCharArray(); int rest = 0; int readerA = aChars.length - 1; int readerB = bChars.length - 1; StringBuilder sb = new StringBuilder(); while (readerA >= 0 && readerB >= 0){ int a = aChars[readerA] - '0'; int b = bChars[readerB] - '0'; int sum = a + b + rest; rest = sum/2; sb.append(sum % 2); readerA--; readerB--; } while(readerA >= 0){ int a = aChars[readerA] - '0'; int sum = a + rest; rest = sum/2; sb.append(sum % 2); readerA--; } while(readerB >= 0){ int b = bChars[readerB] - '0'; int sum = b + rest; rest = sum/2; sb.append(sum % 2); readerB--; } if (rest != 0){ sb.append(rest); } return sb.reverse().toString(); }<p>Результаты</p>
14
public String addBinary(String aa, String bb) { char[] aChars = aa.toCharArray(); char[] bChars = bb.toCharArray(); int rest = 0; int readerA = aChars.length - 1; int readerB = bChars.length - 1; StringBuilder sb = new StringBuilder(); while (readerA >= 0 && readerB >= 0){ int a = aChars[readerA] - '0'; int b = bChars[readerB] - '0'; int sum = a + b + rest; rest = sum/2; sb.append(sum % 2); readerA--; readerB--; } while(readerA >= 0){ int a = aChars[readerA] - '0'; int sum = a + rest; rest = sum/2; sb.append(sum % 2); readerA--; } while(readerB >= 0){ int b = bChars[readerB] - '0'; int sum = b + rest; rest = sum/2; sb.append(sum % 2); readerB--; } if (rest != 0){ sb.append(rest); } return sb.reverse().toString(); }<p>Результаты</p>
15
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все символы в строках.</p>
15
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все символы в строках.</p>
16
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество памяти (максимальный размер памяти - две строки).</p>
16
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество памяти (максимальный размер памяти - две строки).</p>
17
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
17
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>