В этой статье блога мы углубимся в популярную задачу «Сложение двух чисел» в LeetCode и рассмотрим различные подходы к ее решению. Независимо от того, являетесь ли вы опытным программистом или только начинаете, мы рассмотрим различные методы, используя разговорный язык, и предоставим примеры кода на Python, Java и C++. Итак, давайте засучим рукава и вместе взломаем код!

Метод 1: сложение в начальной школе
Помните старые добрые времена сложения чисел в школе? Здесь мы можем применить тот же принцип. Мы проходим оба числа одновременно, начиная с младшей значащей цифры (крайняя справа) до самой старшей цифры (крайняя левая), и отслеживаем значение переноса.

Пример кода (Python):

def add_two_numbers(num1, num2):
    carry = 0
    result = ""
    while num1 or num2 or carry:
        digit_sum = carry
        if num1:
            digit_sum += num1 % 10
            num1 //= 10
        if num2:
            digit_sum += num2 % 10
            num2 //= 10
        carry = digit_sum // 10
        result = str(digit_sum % 10) + result
    return int(result)

Метод 2: подход со связанными списками
LeetCode часто использует связанные списки для представления чисел. В этом подходе мы проходим оба связанных списка одновременно, добавляя соответствующие цифры и отслеживая значение переноса. Мы создаем новый связанный список для хранения результата.

Пример кода (Java):

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int digitSum = carry;

        if (l1 != null) {
            digitSum += l1.val;
            l1 = l1.next;
        }

        if (l2 != null) {
            digitSum += l2.val;
            l2 = l2.next;
        }

        carry = digitSum / 10;
        current.next = new ListNode(digitSum % 10);
        current = current.next;
    }

    return dummy.next;
}

Метод 3: рекурсивное решение
Для тех, кто предпочитает более элегантное и лаконичное решение, на помощь может прийти рекурсия. Мы рекурсивно добавляем цифры, начиная с младшей, и распространяем перенос по мере продвижения вперед.

Пример кода (C++):

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val) : val(val), next(nullptr) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    return addTwoNumbersHelper(l1, l2, 0);
}
ListNode* addTwoNumbersHelper(ListNode* l1, ListNode* l2, int carry) {
    if (!l1 && !l2 && carry == 0)
        return nullptr;

    int digitSum = carry;
    if (l1) {
        digitSum += l1->val;
        l1 = l1->next;
    }
    if (l2) {
        digitSum += l2->val;
        l2 = l2->next;
    }

    ListNode* newNode = new ListNode(digitSum % 10);
    newNode->next = addTwoNumbersHelper(l1, l2, digitSum / 10);

    return newNode;
}

В этой статье блога мы рассмотрели различные методы решения задачи «Сложение двух чисел» в LeetCode. Мы рассмотрели метод сложения в начальной школе, подход связанного списка и рекурсивное решение. В зависимости от ваших предпочтений в кодировании и ограничений задачи вы можете выбрать метод, который подходит вам лучше всего. Приятного кодирования!