1

Тема: Додавання двох чисел у форматі linked list

Є два числа у форматі linked list записані в зворотному порядку, треба їх додати і повернути в тому ж форматі.
Роблю ось так:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* new_l1 = l1;
        ListNode* new_l2 = l2;
        int rest { 0 };
        while (new_l1 && new_l2) {
            int item = new_l1->val + new_l2->val + rest;
            if (item < 10) {
                new_l1->val = item;
                rest = 0;
            } else {
                rest = item / 10;
                new_l1->val = item % 10;
            }
            new_l1 = new_l1->next;
            new_l2 = new_l2->next;
        }
        if (new_l2) {
            while (new_l2) {
                int item = new_l2->val + rest;
                if (item < 10) {
                    new_l1 = new ListNode(item);
                    rest = 0;
                } else {
                    rest = item / 10;
                    new_l1 = new ListNode(item % 10);
                }
                new_l2 = new_l2->next;
                new_l1 = new_l1->next;
            }
        } else if(new_l1) {
            while (new_l1) {
                int item = new_l1->val + rest;
                if (item < 10) {
                    new_l1->val = item;
                    rest = 0;
                } else {
                    rest = item /10;
                    new_l1->val = item % 10;
                }
                new_l1 = new_l1->next;
            }
        }
        if (rest > 0) {
            new_l1 = new ListNode(rest);
        }
        return l1;

При переліках різної довжини губиться перша цифра числа (остання для переліку).

2

Re: Додавання двох чисел у форматі linked list

new_l1 = new ListNode(item);

Як саме new_l1 чіпляється до списку?

            if (item < 10) { // о, ви вирішили оптимізувати код - замість ділення і залишку використовуєте порівняння і гілки
                new_l1->val = item;
                rest = 0;
            } else { // а ні
                rest = item / 10;
                new_l1->val = item % 10;
            }

Цей код виглядає як вираз "чоловічий статевий хуй": довго і безглуздо.

Подякували: leofun01, steamwater2

3

Re: Додавання двох чисел у форматі linked list

koala написав:
new_l1 = new ListNode(item);

Як саме new_l1 чіпляється до списку?

            if (item < 10) { // о, ви вирішили оптимізувати код - замість ділення і залишку використовуєте порівняння і гілки
                new_l1->val = item;
                rest = 0;
            } else { // а ні
                rest = item / 10;
                new_l1->val = item % 10;
            }

Цей код виглядає як вираз "чоловічий статевий хуй": довго і безглуздо.

Усе правильно, код має відповідати розмірам статевого органа програміста:).
А що там коїться в однорядкових — це їхня особиста трагедія:).
І взагалі, не шарите ви в модних італійських патернах:).

Ось чим усе скінчилося:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* new_l1 = l1;
        ListNode* new_l2 = l2;
        int rest { 0 };
        ListNode* dummy = new ListNode();
        ListNode* current = dummy;
        while (new_l1 || new_l2 || rest) {
            int sum = (new_l1 ? new_l1->val : 0) + (new_l2 ? new_l2->val : 0) + rest;
            rest = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
            new_l1 = new_l1 ? new_l1->next : new_l1;
            new_l2 = new_l2 ? new_l2->next : new_l2;
        }
        return dummy->next;
    }
Подякували: leofun011

4

Re: Додавання двох чисел у форматі linked list

Ого як у вас код... скоцюрбився.

5 Востаннє редагувалося steamwater (25.09.2024 19:54:04)

Re: Додавання двох чисел у форматі linked list

koala написав:

Цей код виглядає як вираз "чоловічий статевий орган": довго і безглуздо.

koala, якщо воно довге, то це непогано, а от якщо воно безглуздо висить, то треба лiкувати за умови, що ще не пiзно.

6

Re: Додавання двох чисел у форматі linked list

Teg Miles написав:

Є два числа у форматі linked list записані в зворотному порядку, треба їх додати і повернути в тому ж форматі.

Teg Miles, знов задача з умов несумiсної, складностi. Але й цi умови викладенi незрозумiло. У якому форматi треба розглядати послiдовнicть чисел у кожному контейнерi як єдине число? Наведiть приклад вхiдних послiдовностей, та результуючеї.

7

Re: Додавання двох чисел у форматі linked list

steamwater написав:
Teg Miles написав:

Є два числа у форматі linked list записані в зворотному порядку, треба їх додати і повернути в тому ж форматі.

Teg Miles, знов задача з умов несумiсної, складностi. Але й цi умови викладенi незрозумiло. У якому форматi треба розглядати послiдовнicть чисел у кожному контейнерi як єдине число? Наведiть приклад вхiдних послiдовностей, та результуючеї.

На диво, якраз тут пан Teg дав більш-менш адекватний опис вхідних даних. Ви як звичайно числа записуєте? Арабськими цифрами, позиційно, починаючи з найбільшого розряду. Ну от і тут - цифри, позиційно, але в зворотному напрямку, починаючи з найменшого розряду. Питання, чи зберігається в списку цифра як символ ASCII чи як число до 10, вважаю технічним.

8 Востаннє редагувалося steamwater (26.09.2024 22:02:22)

Re: Додавання двох чисел у форматі linked list

koala написав:

Ви як звичайно числа записуєте?

У int воно пишеться у бiнарному i може бути записане у зворотньому порядку. Чому ви вважаєте реверс-кодування десятичного переважаючим? Десятичне це те що виводиться на екран як представлiння, а у елемент списку чи будь-якого контейнеру воно пишеться, за звичай, iнакше - тобто у бiнарному форматi. Ви можете задати формат навiть строково, але це треба описати. До того ж у зворотньому порядку можуть бути записанi не тiлькi числа. Числа можуть бути записанi як треба i тодi їх формат не матиме значення, а у зворотньому порядку вони могуть слiдувати як елементи самого списку, бо саме так були записанi у список. Чи є однозначнiсть з вказаних мiркуваннь у цьому текстовi:

Teg Miles написав:

Є два числа у форматі linked list записані в зворотному порядку, треба їх додати і повернути в тому ж форматі.

?
Моє птання до ТС лишається у силi. Якщо бракує сил чи бажання, - можна дати посилання на пешоджерело.

Подякували: leofun011

9

Re: Додавання двох чисел у форматі linked list

steamwater написав:
koala написав:

Ви як звичайно числа записуєте?

У int воно пишеться у бiнарному i може бути записане у зворотньому порядку.

І часто вам особисто доводиться писати числа в форматі int? Не створювати програму для запису, а саме ПИСАТИ?

steamwater написав:

Моє птання до ТС лишається у силi. Якщо бракує сил чи бажання, - можна дати посилання на пешоджерело.

У нього дуже специфічна манера спілкування. Подібні прохання він зазвичай узагалі ігнорує.

10

Re: Додавання двох чисел у форматі linked list

steamwater написав:
koala написав:

Ви як звичайно числа записуєте?

У int воно пишеться у бiнарному i може бути записане у зворотньому порядку. Чому ви вважаєте реверс-кодування десятичного переважаючим. Десятичне це те що виводиться на екран як представлiння, а у елемент списку чи будь-якого контейнеру воно пишеться, за звичай, iнакше - тобто у бiнарному форматi. Ви можете задати формат навiть строково, але це треба описати. До того ж у зворотньому порядку можуть бути записанi не тiлькi числа. Числа можуть бути записанi як треба i тодi їх формат не матиме значення, а у зворотньому порядку вони могуть слiдувати як елементи самого списку, бо саме так були записанi у список. Чи є однозначнiсть з вказаних мiркуваннь у цьому текстовi:

Teg Miles написав:

Є два числа у форматі linked list записані в зворотному порядку, треба їх додати і повернути в тому ж форматі.

?
Моє птання до ТС лишається у силi. Якщо бракує сил чи бажання, - можна дати посилання на пешоджерело.

Завдання звідси: https://leetcode.com/explore/learn/card … sion/1228/

11 Востаннє редагувалося steamwater (26.09.2024 17:38:30)

Re: Додавання двох чисел у форматі linked list

koala написав:

І часто вам особисто доводиться писати числа в форматі int? Не створювати програму для запису, а саме ПИСАТИ?

Доволi часто. Ви будете здивованi, але частiше нiж явно, за допомогою лiтералiв. Тай лiтерали бувають не тiльки десятичнi.

int a(123), b(456),
    c=a+b;//тут є щось про 10-тичний формат?
some_cont.insert(it, с);//а тут?
some_cont.insert(it, inverse_bits(c+1));//а тут?

До того ж у текстi сказано, що воно записано (числа чи сам список), але не сказано ким. Тому питання про те як, я особисте, пишу у кодi, не стосується того як воно записано у елемент списка. Бо ж я нiколи не писав у елемент списка. Це робить операцiя доступа на запис, а формат того що записано - результату запису, не стосується 10-тичного формату.

koala написав:

У нього дуже специфічна манера спілкування. Подібні прохання він зазвичай узагалі ігнорує.

Мене це не обходить. Я є на форумi i маю право сподiватись на адекватнiсть у спiлкуваннi. Тож якщо учаснику подобається її не виказувати, то це його вибiр. Коли людина звертається за допомогою, а питання це дiя яка припускає час i зусиляя того хто матиме бажання вiдповiсти, то певна повага до допомагаючих, чи просто читачiв, этично обгрунтована. Недбале формулювання, це вже, певна неповага. А iгнорування уточнюючого зустрiчного питання й поготiв.

12 Востаннє редагувалося steamwater (26.09.2024 16:31:00)

Re: Додавання двох чисел у форматі linked list

Teg Miles написав:

Завдання звідси:

Teg Miles, там треба рееструватись, а я не хочу. Може скопуєте текст завдання? Вiн не має бути великим?

13

Re: Додавання двох чисел у форматі linked list

steamwater написав:
Teg Miles написав:

Завдання звідси:

Teg Miles, там треба рееструватись, а я не хочу. Може скопуєте текст завдання? Вiн не має бути великим?

Дано два непорожніх зв'язаних переліки, які являють собою два не негативні числа.
Числа подані в зворотному порядку і кожен із вузлів містить лише одну цифру.
Додайте ці два числа і поверніть результат у вигляді зв'язаного переліку.
Будь-які два числа не починаються з нуля, окрім власне нуля.

14 Востаннє редагувалося steamwater (26.09.2024 19:18:31)

Re: Додавання двох чисел у форматі linked list

Тобто, цифри. Вже краще. Але як воно стосується списку, незрозумiло. Це може бути масив, вектор, тощо. Ну гаразд. Тож,  якщо маємо, скажiмо:
{1, 2, 3}
{3, 4, 5}
то матимемо:
{4, 6, 8}
?

15

Re: Додавання двох чисел у форматі linked list

steamwater написав:

Тобто, цифри. Вже краще. Але як воно стосується списку, незрозумiло. Це може бути масив, вектор, тощо. Ну гаразд. Тож,  якщо маємо, скажiмо:
{1, 2, 3}
{3, 4, 5}
то матимемо:
{4, 6, 8}
?

Так.

16 Востаннє редагувалося steamwater (27.09.2024 12:13:08)

Re: Додавання двох чисел у форматі linked list

Вхiднi cписки можуть бути рiзного розмiру?
Ну тодi для загального випадку, може бути так:

#include <iostream>
#include <forward_list>
using std::cout;
using std::forward_list;

int main()
{
    using LS = forward_list<int>;
    using l_it = LS::iterator;

    //LS ls1{8, 7, 6, 9};//also works just fine
    LS ls1{8, 7, 6, 1};
    LS ls2{7, 6, 5};

    auto ls1_sz=std::distance(ls1.begin(), ls1.end());
    auto ls2_sz=std::distance(ls2.begin(), ls2.end());

    LS &ls_first=ls1_sz<ls2_sz? ls1:ls2;
    LS &ls_second=&ls_first==&ls1? ls2:ls1;

    LS ls_res;

    int remind(0), res(0);

   l_it it_frst=ls_first.begin(),      it_end=ls_first.end(),
        it_sec=ls_second.begin(), it2_end=ls_second.end();

    res= *it_frst+*it_sec;
    remind=res/10;
    res%=10;

    ls_res.push_front(res);
    l_it it_res=ls_res.begin();

        ++it_frst;
        ++it_sec;

    for(;it_frst!=it_end; ++it_frst, ++it_sec)
    {
        res= *it_frst+*it_sec+remind;

        remind=res/10;
        res%=10;

        it_res=ls_res.insert_after(it_res, res);       
    }

     for(;it_sec!=it2_end; ++it_sec)
     {
        res=*it_sec+remind;

        remind=res/10;
        res%=10;

        it_res=ls_res.insert_after(it_res, res);        
     }

    if(remind)
    ls_res.insert_after(it_res, remind);     

    for(auto el:ls_res)cout<<el<<' ';

    return 0;
}

17

Re: Додавання двох чисел у форматі linked list

steamwater написав:

Вхiднi cписки можуть бути рiзного розмiру?
Не вiдповiдаєте. Ну тодi для загального випадку, може бути так:

#include <iostream>
#include <forward_list>
using std::cout;
using std::forward_list;

int main()
{
    using LS = forward_list<int>;
    using l_it = LS::iterator;

    //LS ls1{8, 7, 6, 9};//also works just fine
    LS ls1{8, 7, 6, 1};
    LS ls2{7, 6, 5};


    auto ls1_sz=std::distance(ls1.begin(), ls1.end());
    auto ls2_sz=std::distance(ls2.begin(), ls2.end());

    LS &ls_first=ls1_sz<ls2_sz? ls1:ls2;
    LS &ls_second=&ls_first==&ls1? ls2:ls1;

    LS ls_res;

    int remind(0), res(0);

    l_it it_frst=ls_first.begin();
    l_it it_end=ls_first.end();
    l_it it_sec=ls_second.begin();
    l_it it2_end=ls_second.end();

    res= *it_frst+*it_sec;
    remind=res/10;
    res%=10;

    ls_res.push_front(res);
    l_it it_res=ls_res.begin();

        ++it_frst;
        ++it_sec;

    for(;it_frst!=it_end;)
    {
        res= *it_frst+*it_sec+remind;

        remind=res/10;
        res%=10;
        it_res=ls_res.insert_after(it_res, res);
        ++it_frst;
        ++it_sec;
    }

     for(;it_sec!=it2_end;)
     {
        res=*it_sec+remind;
        remind=res/10;
        res%=10;
        it_res=ls_res.insert_after(it_res, res);
        ++it_sec;
     }

    if(remind)
    ls_res.insert_after(it_res, remind);     

    for(auto el:ls_res)cout<<el<<' ';

    return 0;
}

Так, бувають різного розміру. Вони дають вже готову структуру для зв'язаного переліку.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
    }
};

18 Востаннє редагувалося steamwater (27.09.2024 00:37:00)

Re: Додавання двох чисел у форматі linked list

Teg Miles написав:

Вони дають вже готову структуру для зв'язаного переліку.

Ну, по-перше, в мене iї не було. А по-друге, менi std бiльш до вподоби. Вам теж раджу. Там iнтерфейс не дає доступу до таких речей як покажчики на ноди. Тобто дивлячись на С-шний код у плюсовiй обгортцi, ви не вчитеся програмувати на плюсах. Ще й можуть бути рецiдиви взяти та застосувати uniqe_ptr у такому кодi... Тут я вам не допоможу.
Ще цiкавiше, той факт, що вiд таких завданнь є бiльш небезпечна шкода. Це не сумiснiсть умов по логицi та складностi. Список не має вiдношення до задачи перекодування чисел залежно вiд порядку цифр. Це схоже на завдання злiтати на Мiсяць i вирiшити там на пiску дрючком рiвняння x-5 = 1-x.
Проте, подивившись на код для std::forward_list ви можете написати для будь-якого контейнера.

19

Re: Додавання двох чисел у форматі linked list

steamwater написав:
Teg Miles написав:

Вони дають вже готову структуру для зв'язаного переліку.

Ну, по-перше, в мене iї не було. А по-друге, менi std бiльш до вподоби. Вам теж раджу. Там iнтерфейс не дає доступу до таких речей як покажчики на ноди. Тобто дивлячись на С-шний код у плюсовiй обгортцi, ви не вчитеся програмувати на плюсах. Ще й можуть бути рецiдиви взяти й застосувати uniqe-ptr у такому кодi... Тут я вам не допоможу.
Ще цiкавiше, той факт, що вiд таких завданнь є бiльш небезпечна шкода. Це не сумiснiсть умов по логицi та складностi. Список не має вiдношення до задачи перекодування чисел залежно вiд порядку цифр. Це схоже на завдання злiтати на Мiсяць i вирiшити там на пiску дрючком рiвняння x-5 = 1-x.

Просто на LeetCode багато математиків, тому така несумісність.
Їм подобається літати на Місяць, бо доводиться багато розрахунків робити:).

20 Востаннє редагувалося steamwater (27.09.2024 00:51:10)

Re: Додавання двох чисел у форматі linked list

Так, небезпека, - бiжу у калiдор!
Це вже третя, мабуть. Наче пронесло. Але чи дадуть поспати невiдомо.
Математики гарнi хлопцi та дiвчата. Але коли не лiзуть у прекметну область. Тобто, невелика кiлькiсть може, але вони або фiзики, або мали потенцiал ними стати. Решту я б без надзору у лic не пускав. Можуть зав'язуючи шнурки, зв'язати їх мiж собою :)