1010cc时时彩标准版 > 三分时时彩1010CC > leetcode每日一题,LeetCode从零刷起

原标题:leetcode每日一题,LeetCode从零刷起

浏览次数:195 时间:2019-09-12

数据结构与算法的重要性就不多说了,几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的,程序猿们都懂的,现在最权威流行的刷题平台就是 LeetCode。闲话少讲,步入正题。

LeetCode(7. Reverse Integer)

Leetcode刷题,leetcode刷

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 < 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 }

 


 

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 1010cc时时彩标准版,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 }

 

Leetcode题库本博客用于记录在LeetCode网站上一些题的解答方法。具体实现方法纯属个人的一些解答,这些解答可能不是...

Reverse Integer

程序=数据结构 算法,数据结构与算法的重要性就不多说了。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的,程序猿们都懂的,现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接

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.

Question

  • leetcode: Reverse Integer | LeetCode OJ
  • lintcode: (413) Reverse Integer

LeetCode原题链接

string - C Reference

知识点:

  1. 这道题考察了关于C int类型的范围以及存储方式。这就要了解数字是如何在计算机存储的了,这涉及到原码,反码和补码的知识。关于这方面的内容,我推荐一篇讲得非常清楚的博客:C 原码,反码,补码详解
    不过在实际使用中,我们只需要知道C int 的范围位于-232 --- 232-1, 且我们可以用INT_MAX表示int的最大值,用INT_MIN表示int的最小值。
  2. 关于一个数值是否越界的判断:这里我用到了这样一个小tip,即如果有可能 a b > INT_MAX的话,为了防止越界造成的麻烦,我们用 a > INT_MAX - b 来判断。其他的运算同理(比如乘法转除法)。这样的等价判断避免了越界带来的麻烦。

Problem Statement

Reverse digits of an integer. Returns 0 when the reversed integer overflows (signed 32-bit integer).

string - C Reference

本文由1010cc时时彩标准版发布于三分时时彩1010CC,转载请注明出处:leetcode每日一题,LeetCode从零刷起

关键词:

上一篇:1010cc时时彩标准版:短视频录制,视频添加音频

下一篇:没有了