LeetCode Note 1st,practice makes perfect

1. Two Sum

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.

Example:

1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. int* twoSum(int* nums, int numsSize, int target) {
5. for (int i = 0; i < numsSize; i++) {
6. for (int j = 0; j < numsSize; j++) {
7. if (i != j) {
8. if(*(nums + i) + *(nums + j) == target) {
9. int *arr;
10. arr = (int *)malloc(2);
11. *arr = i;
12. *(arr+1) = j;
13. return arr;
14. }
15. }
16. }
17. }
18. return NULL;
19. }

7. Reverse Integer

Reverse digits of an integer.

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

下面是通过的Python代码（看上去挺调皮的）：

1. class Solution(object):
2. def reverse(self, x):
3. """
4. :type x: int
5. :rtype: int
6. """
7. if (x >= 1534236469 or x = -1563847412 or x <= -2147483648):
8. return 0
9. if x < 0:
10. objNum = int(str(-x)[::-1])
11. objNum = -objNum
12. else:
13. objNum = int(str(x)[::-1])
14. return objNum

C语言不能用对应的库，没法转化为字符串再反转，下面是linux上练习的：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. int reverse(int x) {
5. char tmpStr[25];
6. sprintf(tmpStr,"%d", x );
7. int strLen = strlen(tmpStr);
8. int flag = 0;
9. if(x < 0)
10. {
11. x = -x;
12. flag = -1;
13. }
14. char objStr[25];
15. int i = 0 ;
16. for(; i < strLen; i++)
17. objStr[i] = tmpStr[strLen-i-1];
18. objStr[strLen] = '\0';
19. int objNum = atoi(objStr);
20. if(flag < 0)
21. objNum = -objNum;
22. return objNum;
23. }
24. int main() {
25. int i = 12345;
26. i = reverse(i);
27. printf("%d", i);
28. return 0;
29. }

8. String to Integer (atoi)

1. int myAtoi(char* str) {
2. int start_pos = 0;
3. while (*(str + start_pos) == ' ')
4. start_pos++;
5. bool  is_positive_num = true;
6. if (*(str + start_pos) == '-') {
7. start_pos++;
8. is_positive_num = false;
9. }
10. else if (*(str + start_pos) == '+')
11. start_pos++;
12. int tmp_pos = start_pos, num_len = 0;
13. while (*(str + tmp_pos) >= '0' && *(str + tmp_pos) <= '9') {
14. num_len++;
15. tmp_pos++;
16. }
17. //when out of bounds, return max value
18. if (is_positive_num){
19. if ((num_len > 10) ||
20. (num_len == 10 && (strcmp(str, "2147483647") > 0)))
21. return INT_MAX;
22. }
23. else {
24. if ((num_len > 10) ||
25. (num_len == 10 && (strcmp(str, "-2147483647") > 0)))
26. return INT_MIN;
27. }
28. int tmp_num, final_num = 0;
29. for (int i = 0; i < num_len; i++) {
30. tmp_num = pow(10.0, num_len - i - 1);
31. final_num += (*(str + start_pos + i) - '0') * tmp_num;
32. }
33. if (!is_positive_num)
34. final_num = -final_num;
35. return final_num;
36. }

2. Add Two Numbers

You are given two linked lists representing two non-negative numbers.
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.

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. if (l1 == NULL)
10. return l2;
11. if (l2 == NULL)
12. return l1;
13. int tmp_num = 0;
14. bool is_carry_bit = false;
15. tmp_num += l1->val + l2->val;
16. if (tmp_num >= 10) {
17. tmp_num = tmp_num % 10;
18. is_carry_bit = true;
19. }
20. struct ListNode *p, *tmp_p, *head = (struct ListNode *) malloc(sizeof(struct ListNode));
21. head->val = tmp_num;
22. p = head;
23. l1 = l1->next;
24. l2 = l2->next;
25. while (l1 != NULL || l2 != NULL) {
26. if (is_carry_bit)
27. tmp_num = 1;
28. else
29. tmp_num = 0;
30. if (l1 == NULL) {
31. tmp_num += l2->val;
32. l2 = l2->next;
33. }
34. else if (l2 == NULL) {
35. tmp_num += l1->val;
36. l1 = l1->next;
37. }
38. else{
39. tmp_num += l1->val + l2->val;
40. l1 = l1->next;
41. l2 = l2->next;
42. }
43. if (tmp_num >= 10) {
44. tmp_num = tmp_num % 10;
45. is_carry_bit = true;
46. }else
47. is_carry_bit = false;
48. tmp_p = (struct ListNode *) malloc(sizeof(struct ListNode));
49. tmp_p->val = tmp_num;
50. p->next = tmp_p;
51. p = p->next;
52. }
53. if(is_carry_bit) {
54. tmp_p = (struct ListNode *) malloc(sizeof(struct ListNode));
55. tmp_p->val = 1;
56. p->next = tmp_p;
57. p = p->next;
58. }
59. p->next = NULL;
60. return head;
61. }

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abc",
which the length is 3.

Given "b",
with the length of 1.

Given "wke",
with the length of 3. Note that the answer must be a substring, "pwke" is
a subsequence and not a substring.

1. int lengthOfLongestSubstring(char* s) {
2. char sub_str[200] = "";
3. char tmp_str[200] = "";
4. bool is_rep = false;
5. int k, h, i = 0, j = 0, max_len = 0, sub_len = 0;
6. while (*(s + i) != '\0') {
7. while (*(sub_str + j) != '\0') {
8. if (*(sub_str + j) == *(s + i)) {
9. is_rep = true;
10. break;
11. }
12. j++;
13. }
14. // if the char isn't repeat, add it to the sub_str
15. if (!is_rep) {
16. *(sub_str + sub_len++) = *(s + i);
17. *(sub_str + sub_len) = '\0';
18. }
19. else {
20. // if the sub_str is bigger than the max_sub_str, reset the max_len
21. if (sub_len > max_len)
22. max_len = sub_len;
23. // reset the sub_str when the char is repeat
24. for (k = j + 1, h = 0; k < sub_len; k++,h++)
25. *(tmp_str + h) = *(sub_str + k);
26. *(tmp_str + h) = *(s + i);
27. *(tmp_str + h + 1) = '\0';
28. strcpy(sub_str, tmp_str);
29. sub_len = h + 1;
30. }
31. i++; j = 0;
32. is_rep = false;
33. }
34. if (sub_len > max_len)
35. max_len = sub_len;
36. return max_len;
37. }

9. Palindrome Number

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

1. bool isPalindrome(int x) {
2. if (x < 0)
3. return false;
4. int base_num = 1,tmp = x/10;
5. while(tmp > 0) {
6. tmp = tmp /10;
7. base_num *= 10;
8. }
9. int left_num, right_num;
10. while(x > 0) {
11. left_num = x / base_num;
12. right_num = x % 10;
13. if(left_num != right_num)
14. return false;
15. x = (x - left_num*base_num - left_num) / 10;
16. base_num = base_num / 100;
17. }
18. return true;
19. }

21. Merge Two Sorted Lists

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.

(This problem is not difficult, simple single linked list. So I use c,java,python to do this problem.)

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. if (NULL == l1) return l2;
10. if (NULL == l2) return l1;
11. struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)), *p_objlst, *tmp, *p_l1 = l1, *p_l2 = l2;
12. if (p_l1->val <= p_l2->val) {
13. head->val = p_l1->val;
14. p_l1 = p_l1->next;
15. }else{
16. head->val = p_l2->val;
17. p_l2 = p_l2->next;
18. }
19. p_objlst = head;
20. while (p_l1 != NULL || p_l2 != NULL) {
21. tmp = (struct ListNode *) malloc(sizeof(struct ListNode));
22. if (p_l1 == NULL) {
23. tmp->val = p_l2->val;
24. p_l2 = p_l2->next;
25. p_objlst->next = tmp;
26. p_objlst = p_objlst->next;
27. continue;
28. }
29. if (p_l2 == NULL) {
30. tmp->val = p_l1->val;
31. p_l1 = p_l1->next;
32. p_objlst->next = tmp;
33. p_objlst = p_objlst->next;
34. continue;
35. }
36. if (p_l1->val >= p_l2->val) {
37. tmp->val = p_l2->val;
38. p_l2 = p_l2->next;
39. }else {
40. tmp->val = p_l1->val;
41. p_l1 = p_l1->next;
42. }
43. p_objlst->next = tmp;
44. p_objlst = p_objlst->next;
45. }
46. p_objlst->next = NULL;
47. return head;
48. }

1. # Definition for singly-linked list.
2. # class ListNode(object):
3. #     def __init__(self, x):
4. #         self.val = x
5. #         self.next = None
6. class Solution(object):
7. def mergeTwoLists(self, l1, l2):
8. """
9. :type l1: ListNode
10. :type l2: ListNode
11. :rtype: ListNode
12. """
13. if l1 is None:
14. return l2
15. if l2 is None:
16. return l1
17. head = ListNode(0)
18. if l1.val <= l2.val:
19. head.val = l1.val
20. l1 = l1.next
21. else:
22. head.val = l2.val
23. l2 = l2.next
24. p = head
25. while l1 != None or l2 != None:
26. tmp = ListNode(0)
27. if l1 is None:
28. tmp.val = l2.val
29. l2 = l2.next
30. p.next=tmp
31. p = p.next
32. continue
33. if l2 is None:
34. tmp.val = l1.val
35. l1 = l1.next
36. p.next=tmp
37. p = p.next
38. continue
39. if l1.val >= l2.val:
40. tmp.val = l2.val
41. l2 = l2.next
42. else:
43. tmp.val = l1.val
44. l1 = l1.next
45. p.next=tmp
46. p = p.next
47. return head

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) { val = x; }
7. * }
8. */
9. public class Solution {
10. public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11. if(l1 == null) return l2;
12. if(l2 == null) return l1;
13. ListNode head = new ListNode(0);
14. if(l1.val <= l2.val) {
15. head.val = l1.val;
16. l1 = l1.next;
17. }else{
18. head.val = l2.val;
19. l2 = l2.next;
20. }
21. ListNode p = head, tmp;
22. while (l1 != null || l2 != null) {
23. tmp = new ListNode(0);
24. if(l1 == null) {
25. tmp.val = l2.val;
26. l2 = l2.next;
27. p.next=tmp;
28. p = p.next;
29. continue;
30. }
31. if(l2==null) {
32. tmp.val = l1.val;
33. l1 = l1.next;
34. p.next=tmp;
35. p = p.next;
36. continue;
37. }
38. if(l1.val >= l2.val) {
39. tmp.val = l2.val;
40. l2 = l2.next;
41. } else {
42. tmp.val = l1.val;
43. l1 = l1.next;
44. }
45. p.next=tmp;
46. p = p.next;
47. }
48. return head;
49. }
50. }

28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

1. int strStr(char* haystack, char* needle) {
2. if (*needle == '\0')
3. return 0;
4. int j = 0, i = 0, tmp_i;
5. bool flag = true;
6. while (*(haystack+i) != '\0') {
7. tmp_i = i;
8. while (*(needle+j) != '\0') {
9. if(*(haystack+tmp_i) == '\0')
10. return -1;
11. if(*(needle+j) != *(haystack+tmp_i))
12. flag = false;
13. j++;
14. tmp_i++;
15. }
16. if(flag == true)
17. return i;
18. j = 0;
19. i++;
20. flag = true;
21. }
22. return -1;
23. }

1. public class Solution {
2. public int strStr(String haystack, String needle) {
3. int lenH = haystack.length(), lenN = needle.length();
4. for (int i = 0; i <= lenH-lenN; i++)
5. if(haystack.substring(i, i+lenN).equals(needle))
6. return i;
7. return -1;
8. }
9. }

1. class Solution(object):
2. def strStr(self, haystack, needle):
3. """
4. :type haystack: str
5. :type needle: str
6. :rtype: int
7. """
8. lenH = len(haystack)
9. lenN = len(needle);
10. for i in range(lenH-lenN+1):
11. if haystack[i: i+lenN] == needle:
12. return i
13. return -1

19. Remove Nth Node From End of List

Given a linked list,
remove the nth node
from the end of list and return its head.

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
9. struct ListNode *p1 = head, *p2 = head, *p3;
10. for (int i = 0; i <n; i++)
11. p1 = p1->next;
12. if (p1 == NULL)
13. return p2->next;
14. while (p1->next != NULL)  {
15. p1 = p1->next;
16. p2 = p2->next;
17. }
18. p3 = p2;
19. p2 = p2->next->next;
20. p3->next = p2;
21. return head;
22. }

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) { val = x; }
7. * }
8. */
9. public class Solution {
10. public ListNode removeNthFromEnd(ListNode head, int n) {
11. ListNode p1 = head, p2 = head, p3;
12. for(int i = 0; i < n; i++)
13. p1 = p1.next;
14. if(p1 == null)
15. return p2.next;
16. while (p1.next != null) {
17. p1 = p1.next;
18. p2 = p2.next;
19. }
20. p3 = p2;
21. p2 = p2.next.next;
22. p3.next = p2;
23. return head;
24. }
25. }

1. # Definition for singly-linked list.
2. # class ListNode(object):
3. #     def __init__(self, x):
4. #         self.val = x
5. #         self.next = None
6. class Solution(object):
7. def removeNthFromEnd(self, head, n):
8. """
9. :type head: ListNode
10. :type n: int
11. :rtype: ListNode
12. """
13. p1 = p2 = head
14. for i in range(n):
15. p1 = p1.next
16. if p1 is None:
17. return p2.next
18. while p1.next is not None:
19. p1 = p1.next
20. p2 = p2.next
21. p3 = p2
22. p2 = p2.next.next
23. p3.next = p2
24. return head

20. Valid Parentheses

Given a string containing just the characters ')', '}', ']',
determine if the input string is valid.

The brackets must close in the correct order, "()[]{}" are
all valid but "([)]" are
not.

1. class Solution(object):
2. def isValid(self, s):
3. stack = []
4. for i in range(len(s)):
5. ch = s[i]
6. if ch in ['(','[','{']:
7. stack.append(ch)
8. elif ch in [')', ']', '}']:
9. if not stack:
10. return False
11. tmp_ch = stack.pop()
12. if ch == ')':
13. if tmp_ch != '(':
14. return False
15. if ch == '}':
16. if tmp_ch != '{':
17. return False
18. if ch == ']':
19. if tmp_ch != '[':
20. return False
21. else:
22. return False
23. if stack:
24. return False
25. return True

1. public class Solution {
2. public boolean isValid(String s) {
3. Stack<String> stack = new Stack<String>();
4. String ch, tmp_ch;
5. for (int i = 0; i < s.length(); i++) {
6. ch = String.valueOf(s.charAt(i));
7. if ( ch.equals("(") || ch.equals("{")
8. || ch.equals("[") ) {
9. stack.push(ch);
10. }
11. else if( ch.equals(")") || ch.equals("}")
12. || ch.equals("]") ){
13. if (stack.isEmpty())
14. return false;
15. tmp_ch = stack.pop();
16. if (ch.equals(")"))
17. if(!tmp_ch.equals("("))
18. return false;
19. if (ch.equals("}"))
20. if(!tmp_ch.equals("{"))
21. return false;
22. if (ch.equals("]"))
23. if(!tmp_ch.equals("["))
24. return false;
25. }
26. else
27. return false;
28. }
29. if(!stack.isEmpty())
30. return false;
31. return true;
32. }
33. }