Re: [閒聊] 每日leetcode

[DJYOSHITAKA (franchouchouISBEST)]

後來想想才知道可以像你板大神這樣inplace
一開始是想說會不會有從最右進位到最左的case 所以就直接用stack先存
但它是*2吼 而且carry最多是1
不管怎麼樣carry都不會傳超過一個digit
剩我浪費記憶體了

ListNode* doubleIt(ListNode* head) {
    stack<ListNode*> s;
    while(head)
    {
        s.push(head);
        head = head->next;
    }

    int carry = 0;
    ListNode* pre = NULL;

    while(!s.empty())
    {
        ListNode* cur = s.top();
        s.pop();
        if(cur->val*2 + carry >= 10)
        {
            cur->val = cur->val*2 + carry - 10;
            carry = 1;
        }
        else
        {
            cur->val = cur->val*2 + carry;
            carry = 0;
        }

        cur->next = pre;
        pre = cur;
    }

    ListNode *dummy = new ListNode(1);
    dummy->next = pre;
    return carry == 1 ? dummy : dummy->next;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.31.27 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715087810.A.290.html
※ 編輯: DJYOSHITAKA (114.137.31.27 臺灣), 05/07/2024 21:17:56
推 JIWP: 別卷了
推 argorok: 別卷了
推 sustainer123: 從右到左都進位的例子不就例2ㄇ
→ DJYOSHITAKA: 應該說 要不要carry只要看next就好 不用看到next->ne
→ DJYOSHITAKA: xt，因為最大digit9*2=18 carry最大=1所以19
→ DJYOSHITAKA: 然後4*2=8 8+1=9  5*2=10 10+1=11 整理出來其實單看
→ DJYOSHITAKA: next->val*2有沒有進位即可 不用考慮後面的事情
→ DJYOSHITAKA: 想表達這個 好難講== 你們直覺想到對的比較猛