Недавно устроился на новую работу в связи с банкротством компании, в которой работал. Поскольку начинаю работать только в Сентябре, решил порешать задачки с leetcode, чтоб совсем мозги не закисали.
И вот одна из этих задачек. Даны два числа, представленные связными списками. Каждый элемент списка - это один знак этого числа. Причём в обратном порядке. Т.е. 721 будет выглядеть так: 1 -> 2 -> 7
Задача написать функцию, складывающую эти два числа. И дана уже заготовка кода.
/**
* 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) {}
};
Т.е. нужно по сути написать эту функцию. Сначала создал временную переменную, куда буду пихать результат, организовал цикл, но потом брослся в глаза последний конструктор класса ListNode. Ну прямо просится рекурсия под этот конструктор. В результате, стираю всё, что наваял и получился вот такой код, который заработал и прошёл все тесты.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if((l1 != nullptr) || (l2 != nullptr) || (carry != 0) ) {
int tmp_result = ((l1 != nullptr) ? l1->val : 0) + ((l2 != nullptr) ? l2->val : 0) + carry;
if(tmp_result >= 10) {
carry = 1;
tmp_result -= 10;
} else {
carry = 0;
}
return new ListNode(tmp_result, addTwoNumbers((l1 != nullptr) ? l1->next : nullptr, (l2 != nullptr) ? l2->next : nullptr));
} else {
return nullptr;
}
}
private:
int carry = 0;
};
А причём тут ИИ, спросите вы? Да после того, как решил эту задачу, решил посмотреть, как её решит ИИ. А сделал он достаточно топорно, а именно так, как я хотел решать изначально.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* _l1, ListNode* _l2) {
// Create a dummy head to simplify the list construction logic
ListNode* dummyHead = new ListNode(0);
ListNode* currentNode = dummyHead;
int carryValue = 0;
// Iterate while there are nodes in either list or a carry remains
while (_l1 != nullptr || _l2 != nullptr || carryValue != 0) {
// Get values from the current nodes, default to 0 if list is exhausted
int firstVal = (_l1 != nullptr) ? _l1->val : 0;
int secondVal = (_l2 != nullptr) ? _l2->val : 0;
// Calculate the sum of the digits and the current carry
int sumValue = firstVal + secondVal + carryValue;
carryValue = sumValue / 10;
// Create a new node with the digit part of the sum
currentNode->next = new ListNode(sumValue % 10);
currentNode = currentNode->next;
// Advance the pointers of the input lists
if (_l1 != nullptr) {
_l1 = _l1->next;
}
if (_l2 != nullptr) {
_l2 = _l2->next;
}
}
// Store the actual head of the result list
ListNode* resultHead = dummyHead->next;
// Free the dummy head memory to prevent memory leaks
delete dummyHead;
return resultHead;
}
};
На самом leetcode есть несколько решений к данной задаче. И нет ни одного решения с рекурсией. Да, я понимаю, многие не любят рекурсию и считают её антипаттерном, но тем не менее, задание тестовое, есть конструктор, кричащий: "Будь мужиком, заюзай рекурсию, б***ь!". По мне так, вариант с рекурсией выглядит проще и элегантнее.
Вывод напрашивается сам собой. Да, ИИ решит задачу. Но решит её так, чтоб она просто работала, т.е. на уровне индуса. А вот если надо проявить креативность, тут уже не так всё радужно. Хотя, зная, что это по сути языковая модель, а не интеллект, ожидать какой-то креативности от него не стоит.
P.S. Да, я знаю, что вместо (l1 != nullptr) можно было написать просто l1, но я предпочитаю именно такую запись в своём коде. Чтоб другие разрабы не искали каждый раз, что за переменные l1, l2, а уже понимали, что это какие-то указатели.
