DummyH的部落格

原文

Question:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input:   (2 ->  4  ->  3) + (5 -> 6  ->  4)
Output: 7  ->​​​​​​​ ​​​​​​​ 0  ->​​​​​​​ ​​​​​​​ 8

翻譯

問題:

      給定兩個非空的鍊結串列，分別代表兩個非負的整數串列，串列內每個元素皆由反方向儲存(越前面的節點位數越低)，每一個節點代表一個位元。

將此兩個鍊結串列相加並回傳。

解答:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *newNode(int data)
{
    struct ListNode *NewNode = (struct ListNode *) malloc(sizeof(struct ListNode));
    NewNode->val = data;
    NewNode->next = NULL;
    return NewNode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    
    struct ListNode *head    = NULL;
    struct ListNode *current = NULL;
    struct ListNode *rear    = NULL;
    int temp    = 0 , result = 0;
    
    while (l1 != NULL || l2 != NULL)
    {
        // 計算總合
        result = temp + (l1? l1->val: 0) + (l2? l2->val: 0);
        
        // 進位處理
        temp   = (result >= 10)? 1 : 0;
        result = (result >= 10)? (result-10):result;
        
        // 節點串連
        current = newNode(result);
        if (!head)
            head = current;
        else
            rear-> next = current;

        rear = current;
        
        //指標後移 
        if (l1) 
            l1 = l1->next;
        if (l2) 
            l2 = l2->next;    

        //最後的進位處理   
        if (temp == 1)
            rear->next = newNode(1);
    }
    return head;
}

解析:

      此題為難度中級，需具備linklist基本概念與細心的進位處理。

需要注意的是: 

1. 基本功能 如: new node (新增節點)，最好可獨立出另一個function，增加程式的可讀性。

2. 可多善加使用 如: bigger number = (5>3)?5:3; 的技巧來簡化程式。

原文

Question:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻譯

問題:

給定一個整數陣列 nums 與一個特定值 T ，回傳一組index [ a , b] ，而使得 T = nums [a] + nums [b].

注意：不可重複使用同一個元素　Ex :  6 = 3 + 3　是不合法的。

解答:

int twoSum(int *nums ,int length, int target) 
{
    static int answer[2] = {0};
    
     for (int i = 0 ; i < length; i++)
     {
        for (int j = i+1 ; j < length ; j++)
        {
            if((nums [i] + nums [j]) == target)
            {
                answer[0] = i;
                answer[1] = j;
                    
                return answer;
            }
        }
     }
     return 0;
}

解析:

      此題為簡單的熱身題，使用一般暴力破解法，窮舉所有可能即可得到答案。

需要注意的是: 

1.  "所有可能" 只需檢查一次即可，所以 j = i+1 而非從 0 開始。

2.  宣告 int answer 時，記得加上 static 其目的是使陣列 answer 於 twoSum() 結束時，依然可保留其記憶體位置而不被刪除。