Решение на LeetCode 67. Add Binary, което е вдъхновено от caikehe
class Solution {
public:
string addBinary(string a, string b) {
string res = "";
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
if (i >= 0) {
carry += a[i] == '0' ? 0 : 1;
i--;
}
if (j >= 0) {
carry += b[j] == '0' ? 0 : 1;
j--;
}
res = ((carry%2) == 0 ? "0" : "1") + res;
carry /= 2;
}
return res;
}
};
Основната идея е да проверите знаците назад и да изчислите цифрената сума от два дадени низа. Има 4 различни комбинации: 0+0=0 , 0+1 or 1+0=1 или 1+1=10 . Само последната ситуация ще предизвика 0 с пренасяне, а останалите няма да причинят пренасяне (напр. 0 or 1).
Имайки предвид тази идея, можем да преминем през струните от края към предната част. „Троичният оператор“ става удобен, когато се опитваме да напишем кратък код.
carry тук прави изчисляването на цифрената сума и може да варира от 0 to 3. За да забележите, лесно е да разберете, че пренасянето може да варира от 0 to 2, като например 0+0 to 0, 0+1 or 1+0 to 1, 1+1 to 2. Въпреки това, когато 1+1 to 2 се появи за първи път, carry /= 2 прави carry = 1, което ще бъде отведено до следващия цикъл while, ако е наличен. След това, когато 1+1 се появи отново, carry ще бъде добавено до 3 . Следователно пренасянето варира от 0 до 3. Можете да тествате двоичното добавяне case11+11, за да разберете.
Освен това условието carry != 0 в цикъла while е важно. Нека да разгледаме 1+1 случай. Последната сума от цифри в регистъра първо ще доведе до carry да бъде 2, след което carry /= 2 прави carry = 1. В този момент i and j е намалено до -1 след един цикъл, първите две условия в цикъла while вече не важат. Изчислението обаче не е завършено, тъй като имаме само res = "0" . Сега carry != 0 наистина пренася изчислението напред и в крайна сметка прави res = 10.
Надявам се това да помогне.
