EasyLeetCode02, добавь два числа

алгоритм LeetCode

Всем привет, меня зовут Тан Лян.

Сегодня я предлагаю вам второй вопрос LeetCode, добавляющий два числа Это вопрос средней сложности.github,объясняющее видео

смысл названия

Смысл вопроса очень прост, учитывая два непустых связанных списка. Представление целого числа в виде связанного списка в обратном порядке требует, чтобы мы сложили два числа и вернули связанный список той же формы.

За исключением числа 0, ни одно из этих чисел не начинается с 0, то есть ведущего 0 нет.

Так называемый обратно-связный список, пример приведен в заголовке, то есть следующий вид:

Например 2 -> 4 -> 3, хранилище 342, а не 243, тут нужно обратить внимание.

диапазон данных

  • Количество узлов в каждом связанном списке находится в диапазоне[1, 100]Внутри
  • 0 <= Node.val <= 9
  • Данные заголовка гарантируют, что числа, представленные в списке, не содержат ведущих нулей.

решение

Сама задача очень проста, сложность заключается в использовании связанных списков.

Мы знаем, что в C++ существует концепция указателей, и указатель может указывать на адрес переменной в памяти. Используя указатели, мы можем разработать специальную структуру данных, которая хранит указатель на структуру того же типа в определенной структуре. Таким образом, мы можем соединить экземпляры нескольких структур через указатели в структуре, как в цепочке.Эта структура данных называется связанным списком.

Мы можем посмотреть на определение связанного списка, данное в заголовке:

Одноклассник раньше спрашивал меня, откуда взялась структура, которую вы используете, и я не видел вашего определения. На самом деле, это особенность многих OJ, нам нужно реализовать только основную логику, иногда написание функции, иногда написание класса. В дополнение к коду, который мы пишем, судейская машина запускает много другой логики. Просто эти логики не имеют никакого отношения к нашей проблеме, поэтому они все скрыты.

Например, определение связанного списка здесь, LeetCode, было определено для нас. Нам просто нужно использовать его, нам не нужно заботиться о том, где он определен.

Давайте взглянем на эту структуру, ее имяListNode, как следует из названия, представляет собой узел связанного списка. Он имеет две переменные-члены, одна из которыхintval типа, а другойListNodeуказатель. Здесь val хранит целое число от 0 до 9, которое представляет один из битов целого числа.Указатель здесь, естественно, используется для указания на следующий узел.

Давайте посмотрим на функцию, которую мы хотим реализовать:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)

Есть два входящих параметра, которые являются головными указателями двух связанных списков, и возвращаемый результат также является указателем. — указатель на новый связанный список, который мы сгенерировали.

Итак, есть две вещи, которые нам нужно сделать, одна — пересечьl1иl2Эти два связанных списка, второй — добавить в них числа, сгенерировать новый связанный список и вернуть указатель на заголовок нового связанного списка.

Связный список не похож на массив, мы не можем знать точную длину, мы можем только использоватьwhileЦикл для обхода, переход от начального узла один за другим и остановка при переходе к нулевому указателю. В этой задаче нам нужно обойти два связанных списка, поэтому условие цикла должно быть записано так:

while (l1 != nullptr || l2 != nullptr) {
    // todo
}

После обхода связанного списка все остальное просто, то есть завершить добавление. К этому времени мы обнаружим, что очень удобно хранить связанный список в обратном порядке. Поскольку позиция каждого элемента, который мы получаем, определена, первый должен быть единицей, а второй — десяткой. Если наш связанный список хранится в положительном порядке, прежде чем мы узнаем длину связанного списка, мы не знаем, какой бит является первым битом.

Таким образом, на первый взгляд, связанный список, хранящийся в обратном порядке, кажется немного проблематичным, но на самом деле он упрощает задачу для нас.

Наконец, нам нужно только обратить внимание на перенос сложения, это легко написать код:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode();
        ListNode* pnt = ret;
        bool carry = false;
        while (l1 != nullptr || l2 != nullptr || carry) {
            int cur = 0;
            if (l1 != nullptr) {
                cur += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                cur += l2->val;
                l2 = l2->next;
            }
            if (carry) {
                cur ++;
            }
            if (cur >= 10) {
                cur -= 10;
                carry = true;
            }else {
                carry = false;
            }
            pnt->next = new ListNode(cur);
            pnt = pnt->next;
        }
        return ret->next;
    }
};

Об обращении с переносом сказать особо нечего, единственное, что следует отметить, это то, чтоwhileУсловия в цикле имеют дополнительное суждение о том, следует ли переносить или нет. Это обработка, когда перенос происходит в старший бит, в противном случае перенос старшего бита будет потерян.

Если вы обратите внимание на этот трюк и поймете основы использования связанных списков, эта проблема будет легко решена, не так ли?

Ну вот и все по этой теме, спасибо за прочтение.

Категории