Leetcode刷题

时间:2019-10-26 05:19来源:永利澳门游戏网站
You are given two non-empty linked lists representing two non-negativeintegers. The digits are stored in reverse order and each of their nodescontain a single digit. Add the two numbers and return it as a linkedlist.       If the integ

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.

 

 

 

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

 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 }

 

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

Leetcode刷题。click to show spoilers.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

 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 < 0x80000000n");
18         return 0;
19     }   
20  
21     if (data == 0) {
22         printf("data == 0n");
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 < 0x80000000n");
68         return 0;
69     }
70  
71     return data;
72 }

 

 

 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 }

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

本博客用于记录在LeetCode网址上部分题的解答方法。具体达成格局纯属个人的有些解答,那几个解答恐怕不是好的解答方法,记录在这里,督促和煦多学学多演练。

 

Leetcode刷题。There is a more generic way of solving this problem.

 

 

 


Note:

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

Example:

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?

 

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

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Leetcode刷题。 

 

 

 

 

Leetcode题库

 

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

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

 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 }

Example 2:

 

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

The median is 2.0

 

 

Output: 7 -> 0 -> 8


 

 

 

 

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

 

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?

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

Example 1:

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

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

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.

 

 

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

 

click to show spoilers.


 

 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 }

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

 

 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 }

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

Reverse digits of an integer.

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

You may assume no duplicates in the array.

 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 != '') {
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 }

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

 

 

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.

 

 

Some hints:

 

 

 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 } 
nums1 = [1, 2]
nums2 = [3, 4]

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

Have you thought about this?


 

 

 

 

 


编辑:永利澳门游戏网站 本文来源:Leetcode刷题

关键词: