iii.run

2. Add Two Numbers

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
Explanation: 342 + 465 = 807.

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p=new ListNode(0); //answer
        ListNode* top=p;
        ListNode* q=NULL; //temp
        int flag =0;
        int tmp;
        while(l1&&l2){
            tmp = l1->val+l2->val+flag;
            flag = tmp/10;
            q = new ListNode(tmp%10);
            p->next = q;
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1){
            tmp = l1->val+flag;
            flag = tmp/10;
            q = new ListNode(tmp%10);
            p->next = q;
            p = p->next;
            l1 = l1->next;
        }
        while(l2){
            tmp = l2->val+flag;
            flag = tmp/10;
            q = new ListNode(tmp%10);
            p->next = q;
            p = p->next;
            l2 = l2->next;
        }
        if(flag>0){
            q = new ListNode(flag);
            p->next = q;
        }
    return top->next;
    }
};

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

class Solution {
private:
    static int find_kth(vector<int>::const_iterator A, int m,
        vector<int>::const_iterator B, int n, int k) {
        //always assume that m is equal or smaller than n
        if (m > n) return find_kth(B, n, A, m, k);
        if (m == 0) return *(B + k - 1);
        if (k == 1) return min(*A, *B);
        //divide k into two parts
        int ia = min(k / 2, m), ib = k - ia;
        if (*(A + ia - 1) < *(B + ib - 1))
            return find_kth(A + ia, m - ia, B, n, k - ia);
        else if (*(A + ia - 1) > *(B + ib - 1))
            return find_kth(A, m, B + ib, n - ib, k - ib);
        else
            return A[ia - 1];
    }
public:
    double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
        int m = A.size();
        int n = B.size();
        int total = m + n;
        if (total & 0x1) //判断奇数
            return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
        else
            return (find_kth(A.begin(), m, B.begin(), n, total / 2) +
                find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
    }
};

• 三种情况
  • A[k/2-1] == B[k/2-1] 找到答案了
  • A[k/2-1] > B[k/2-1] 第K项不在B前k/2-1内
  • A[k/2-1] < B[k/2-1] 第K项不在A前k/2-1内

• 递归停止条件
  • m==0， 从B里边直接算第K个即可
  • k ==1， 找到两个元素中更小的
  • A[k/2-1] == B[k/2-1] 找到答案了

思路之巧妙