Leetcode题库

 

 

 

本博客用于记录在LeetCode网站上一些题的解答方法。具体实现方法纯属个人的一些解答，这些解答可能不是好的解答方法，记录在此，督促自己多学习多练习。

 

 

---

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

 

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int *nums = NULL;
    int totle_num = 0;
    int mid_num = 0;
    double mid = 0;
    int i = 0, j = 0, k = 0;
 
    totle_num = nums1Size + nums2Size;
    mid_num = totle_num >> 1;
 
    nums = (int *)malloc(sizeof(int) * (totle_num));
    if (nums == NULL) {
        return -1;
    }
 
    for (k = 0; k < (mid_num + 1); k++) {
        if (nums1Size == 0 || i == nums1Size) {
            *(nums + k) = *(nums2 + j);
            j++;
        } else if (nums2Size == 0 || j == nums2Size) {
            *(nums + k) = *(nums1 + i);
            i++;
        } else if (*(nums1 + i) <= *(nums2 + j)) {
            *(nums + k) = *(nums1 + i);
            i++;
        } else if (*(nums1 + i) > *(nums2 + j)){
            *(nums + k) = *(nums2 + j);
            j++;
        }
    }
 
    if (totle_num % 2 == 0) {
        mid = (double)((*(nums + (mid_num - 1)) + *(nums + mid_num))) / (double)2;
    } else {
        mid = *(nums + mid_num);
    }
    free(nums);
 
    return mid;
}

 

---

 

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* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *tail1 = NULL;
    struct ListNode *tail2 = NULL;
    struct ListNode *new = NULL;;
    int tmp = 0;
 
    if (NULL == l1 || NULL == l2) {
        perror("list NULL!\n");
        return NULL;
    }
 
    for (tail1 = l1, tail2 = l2; (tail1->next != NULL) || (tail2->next != NULL);) {
        if ((tail1->next != NULL) && (tail2->next != NULL)) {
            tail1->val += tail2->val;
        } else if ((tail1->next != NULL) && (tail2->next == NULL)) {
            if (tail2 != NULL) {
                tail1->val += tail2->val;
            }
        } else if ((tail1->next == NULL) && (tail2->next != NULL)) {
            if (tail1 != NULL) {
                tail1->val += tail2->val;
                new = (struct ListNode *)malloc(sizeof(struct ListNode));
                if (NULL == new) {
                    perror("malloc failed!\n");
                    return NULL;
                }
                tail1->next = new;
                new->val = 0;
                new->next = NULL;
            }
        }
 
        tail1->val += tmp;
        if (tail1->val < 10) {
            tmp = 0;
        } else {
            tmp = tail1->val / 10;
            tail1->val %= 10;
        }
 
        if (tail1->next != NULL) {
            tail1 = tail1->next;
        }
        if (tail2->next != NULL) {
            tail2 = tail2->next;
        } else {
            tail2->val = 0;
        }
    }
 
    if (tail1 != NULL) {
        if (tail2 != NULL) {
            tail1->val += tail2->val;
        }
        tail1->val += tmp;
        if (tail1->val >= 10) {
            tmp = tail1->val / 10;
            tail1->val %= 10;