首页 > > 程序设计 > C/C++ >

Leetcode刷题

2018-06-18 03:57:03来源：未知阅读 ()

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

 1 double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
 2     int *nums = NULL;
 3     int totle_num = 0;
 4     int mid_num = 0;
 5     double mid = 0;
 6     int i = 0, j = 0, k = 0;
 7  
 8     totle_num = nums1Size + nums2Size;
 9     mid_num = totle_num >> 1;
10  
11     nums = (int *)malloc(sizeof(int) * (totle_num));
12     if (nums == NULL) {
13         return -1;
14     }
15  
16     for (k = 0; k < (mid_num + 1); k++) {
17         if (nums1Size == 0 || i == nums1Size) {
18             *(nums + k) = *(nums2 + j);
19             j++;
20         } else if (nums2Size == 0 || j == nums2Size) {
21             *(nums + k) = *(nums1 + i);
22             i++;
23         } else if (*(nums1 + i) <= *(nums2 + j)) {
24             *(nums + k) = *(nums1 + i);
25             i++;
26         } else if (*(nums1 + i) > *(nums2 + j)){
27             *(nums + k) = *(nums2 + j);
28             j++;
29         }
30     }
31  
32     if (totle_num % 2 == 0) {
33         mid = (double)((*(nums + (mid_num - 1)) + *(nums + mid_num))) / (double)2;
34     } else {
35         mid = *(nums + mid_num);
36     }
37     free(nums);
38  
39     return mid;
40 }

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

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 9     struct ListNode *tail1 = NULL;
10     struct ListNode *tail2 = NULL;
11     struct ListNode *new = NULL;;
12     int tmp = 0;
13  
14     if (NULL == l1 || NULL == l2) {
15         perror("list NULL!\n");
16         return NULL;
17     }
18  
19     for (tail1 = l1, tail2 = l2; (tail1->next != NULL) || (tail2->next != NULL);) {
20         if ((tail1->next != NULL) && (tail2->next != NULL)) {
21             tail1->val += tail2->val;
22         } else if ((tail1->next != NULL) && (tail2->next == NULL)) {
23             if (tail2 != NULL) {
24                 tail1->val += tail2->val;
25             }
26         } else if ((tail1->next == NULL) && (tail2->next != NULL)) {
27             if (tail1 != NULL) {
28                 tail1->val += tail2->val;
29                 new = (struct ListNode *)malloc(sizeof(struct ListNode));
30                 if (NULL == new) {
31                     perror("malloc failed!\n");
32                     return NULL;
33                 }
34                 tail1->next = new;
35                 new->val = 0;
36                 new->next = NULL;
37             }
38         }
39  
40         tail1->val += tmp;
41         if (tail1->val < 10) {
42             tmp = 0;
43         } else {
44             tmp = tail1->val / 10;
45             tail1->val %= 10;
46         }
47  
48         if (tail1->next != NULL) {
49             tail1 = tail1->next;
50         }
51         if (tail2->next != NULL) {
52             tail2 = tail2->next;
53         } else {
54             tail2->val = 0;
55         }
56     }
57  
58     if (tail1 != NULL) {
59         if (tail2 != NULL) {
60             tail1->val += tail2->val;
61         }
62         tail1->val += tmp;
63         if (tail1->val >= 10) {
64             tmp = tail1->val / 10;
65             tail1->val %= 10;
66             new = (struct ListNode *)malloc(sizeof(struct ListNode));
67             if (NULL == new) {
68                 perror("malloc failed!\n");
69                 return NULL;
70             }
71             tail1->next = new;
72             new->val = tmp;
73             new->next = NULL;
74         }
75     }
76  
77     return l1;
78 }

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

 1 int searchInsert(int* nums, int numsSize, int target) {
 2     int *pNum = NULL;
 3     int i = 0;
 4  
 5     if (NULL == nums) {
 6         return -1;
 7     }
 8  
 9     if (numsSize <= 0) {
10         return -1;
11     }
12  
13     pNum = nums;
14  
15     for (i = 0; i < numsSize; i++) {
16         if (*(pNum + i) >= target) {
17             return i;
18         } else {
19             if (i == numsSize - 1) {
20                 return numsSize;
21             }
22         }
23     }
24  
25     return -1;
26 }

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
 9     struct ListNode *tail1 = NULL;
10     struct ListNode *tail2 = NULL;
11     struct ListNode *bak_node1 = NULL;
12     struct ListNode *bak_node2 = NULL;
13     struct ListNode *bak_node = NULL;
14  
15     if (l1 == NULL) {
16         return l2;
17     }
18  
19     if (l2 == NULL) {
20         return l1;
21     }
22  
23     // 找到第一个数据最小的链表，作为返回链表
24     if (l1->val <= l2->val) {
25         tail1 = l1;
26         tail2 = l2;
27     } else {
28         tail1 = l2;
29         tail2 = l1;
30     }
31     bak_node1 = tail1;
32     bak_node2 = tail2;
33  
34     bak_node = tail1;
35  
36     while (tail2 != NULL) {
37         while (tail1->val <= tail2->val) {
38             if (tail1->next == NULL) {
39                 tail1->next = tail2;
40                 return bak_node;
41             }
42             bak_node1 = tail1;
43             tail1 = tail1->next;
44         }
45  
46         bak_node2 = tail2->next;
47         tail2->next = tail1;
48         bak_node1->next = tail2;
49         bak_node1 = bak_node1->next;
50         tail2 = bak_node2;
51     }
52  
53     return bak_node;
54 }

 1 bool isValid(char* s) {
 2     char *pString = NULL;
 3     int flag1 = 0, flag2 = 0, flag3 = 0;
 4     int flag = 0;
 5  
 6     if (s == NULL) {
 7         perror("String NULL!\n");
 8         return false;
 9     }
10  
11     pString = s;
12  
13     while (*pString != '\0') {
14         if (*pString == '(') {
15             flag1++;
16             flag = 1;
17         } else if (*pString == ')') {
18             if (flag == 1 && flag1 != 0) {
19                 flag1--;
20             } else if (flag == 0) {
21                 return false;
22             }
23         }
24  
25         if (*pString == '{') {
26             flag2++;
27             flag = 2;
28         } else if (*pString == '}') {
29             if (flag == 2 && flag2 != 0) {
30                 flag2--;
31             } else if (flag == 0) {
32                 return false;
33             }
34         }
35  
36         if (*pString == '[') {
37             flag3++;
38             flag = 3;
39         } else if (*pString == ']') {
40             if (flag == 3 && flag3 != 0) {
41                 flag3--;
42             } else if (flag == 0) {
43                 return false;
44             }
45         }
46  
47         if (flag1 + flag2 + flag3 > 1) {
48             return false;
49         }
50         pString++;
51     }
52  
53     if ((flag1 != 0) || (flag2 != 0) || (flag3 != 0)) {
54         return false;
55     }
56  
57     return true;
58 }

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

 1 bool isPalindrome(int x) {
 2     int data = 0;
 3     int num = 1;
 4     int count = 0;
 5     int i = 0;
 6     int tmp1 = 1, tmp2 = 1;
 7  
 8     data = x;
 9  
10     if (data < 0) {
11         return 0;
12     }
13  
14     while (data / 10) {
15         data /= 10;
16         tmp1 *= 10;
17         count++;
18     }
19     if (data != 0) {
20         count++;
21         if (count != 10) {
22             tmp1 *= 10;
23         }
24     }
25  
26     data = x;
27     i = 0;
28     if (count == 10) {
29         if (data / 1000000000 != data % 10) {
30             return 0;
31         }
32         i++;
33         tmp2 *= 10;
34     }
35     while ((i < count / 2) && ((data % tmp1 / (tmp1 / 10)) == (data % (tmp2 * 10) / tmp2))) {
36         tmp1 /= 10;
37         tmp2 *= 10;
38         i++;
39     }
40     if (i != count / 2) {
41         return 0;
42     }
43  
44     return 1;
45 }

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:

The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

 1 int reverse(int x) {
 2     int array[10] = { 0 };
 3     int int_max = 0x7FFFFFFF;
 4     int int_min = 0x80000000;
 5     int data = 0;
 6     int count = 0;
 7     int num = 1;
 8     int i = 0;
 9  
10     data = x;
11     if ((int)data > (int)0x7FFFFFFF) {
12         printf("data > 0x7FFFFFFF");
13         return 0;
14     }   
15  
16     if ((int)data < (int)0x80000000) {
17         printf("data < 0x80000000\n");
18         return 0;
19     }   
20  
21     if (data == 0) {
22         printf("data == 0\n");
23         return 0;
24     }   
25  
26     i = 0;
27     data = x;
28     count = 0;
29     while ((data / 10) != 0) {
30         array[i++] = data % 10;
31         data = data / 10;
32         count++;
33     }   
34     if (data != 0) {
35         array[i] = data;
36         data = 0;
37         count++;
38     }
39  
40     if (count == 10) {
41         i = 0;
42         num = 1000000000;
43         while (i < count) {
44             if ((array[i] == int_max/num) || (array[i] == int_min/num)) {
45                 i++;
46                 int_max %= num;
47                 int_min %= num;
48                 num /= 10;
49             } else if ((array[i] < int_max/num) && (array[i] > int_min/num)) {
50                 break;
51             } else {
52                 return 0;
53             }
54         }
55     }
56  
57     for (i = count - 1, num = 1; i >= 0; i--) {
58         data += array[i] * num;
59         num *= 10;
60     }   
61     if ((int)data > (int)0x7FFFFFFF) {
62         printf("After: data > 0x7FFFFFFF");
63         return 0;
64     }   
65  
66     if ((int)data < (int)0x80000000) {
67         printf("After: data < 0x80000000\n");
68         return 0;
69     }
70  
71     return data;
72 }

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].

 1 /**
 2  * Note: The returned array must be malloced, assume caller calls free().
 3  */
 4 int* twoSum(int* nums, int numsSize, int target) {
 5     int *parray = NULL;
 6     int i = 0, j = 0;
 7  
 8     parray = (int *)malloc(sizeof(int) * 2);
 9     if (NULL == parray) {
10         perror("malloc error!\n");
11         return NULL;
12     }
13  
14     for (i = 0; i < numsSize; i++) {
15         for (j = i + 1; j < numsSize; j++) {
16             if (nums[i] + nums[j] == target) {
17                 *parray = i;
18                 *(parray + 1) = j;
19                 break;
20             }
21         }
22     }
23  
24     return parray;
25 }