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:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            if (i != j) {
                if(*(nums + i) + *(nums + j) == target) {
                    int *arr;
                    arr = (int *)malloc(2);
                    *arr = i;
                    *(arr+1) = j;
                    return arr;
                }
            }
        }
    }
    return NULL;
}

7. Reverse Integer

Reverse digits of an integer.

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

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

 

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if (x >= 1534236469 or x = -1563847412 or x <= -2147483648):
            return 0
        if x < 0:
            objNum = int(str(-x)[::-1])
            objNum = -objNum
        else:
            objNum = int(str(x)[::-1])
        return objNum

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int reverse(int x) {
    char tmpStr[25];
    sprintf(tmpStr,"%d", x );
    int strLen = strlen(tmpStr);

    int flag = 0;
    if(x < 0)
    {
        x = -x;
        flag = -1;
    }

    char objStr[25];
    int i = 0 ;
    for(; i < strLen; i++)
        objStr[i] = tmpStr[strLen-i-1];
    objStr[strLen] = '';

    int objNum = atoi(objStr);
    if(flag < 0)
        objNum = -objNum;
    return objNum;
}

int main() {
    int i = 12345;
    i = reverse(i);
    printf("%d", i);
    return 0;
}

8. String to Integer (atoi)

int myAtoi(char* str) {
    int start_pos = 0;
    while (*(str + start_pos) == ' ')
        start_pos++;
    bool  is_positive_num = true;

    if (*(str + start_pos) == '-') {
        start_pos++;
        is_positive_num = false;
    }
    else if (*(str + start_pos) == '+')
        start_pos++;
    int tmp_pos = start_pos, num_len = 0;
    while (*(str + tmp_pos) >= '0' && *(str + tmp_pos) <= '9') {
        num_len++;
        tmp_pos++;
    }
    //when out of bounds, return max value
    if (is_positive_num){
        if ((num_len > 10) ||
            (num_len == 10 && (strcmp(str, "2147483647") > 0)))
            return INT_MAX;
    }
    else {
        if ((num_len > 10) ||
            (num_len == 10 && (strcmp(str, "-2147483647") > 0)))
            return INT_MIN;
    }
    int tmp_num, final_num = 0;
    for (int i = 0; i < num_len; i++) {
        tmp_num = pow(10.0, num_len - i - 1);
        final_num += (*(str + start_pos + i) - '0') * tmp_num;
    }
    if (!is_positive_num)
        final_num = -final_num;
    return final_num;
}

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;

    int tmp_num = 0;
    bool is_carry_bit = false;
    tmp_num += l1->val + l2->val;
    if (tmp_num >= 10) {
        tmp_num = tmp_num % 10;
        is_carry_bit = true;
    }
    struct ListNode *p, *tmp_p, *head = (struct ListNode *) malloc(sizeof(struct ListNode));
    head->val = tmp_num;
    p = head;
    l1 = l1->next;
    l2 = l2->next;

    while (l1 != NULL || l2 != NULL) {
        if (is_carry_bit)
            tmp_num = 1;
        else
            tmp_num = 0;
        if (l1 == NULL) {
            tmp_num += l2->val;
            l2 = l2->next;
        }
        else if (l2 == NULL) {
            tmp_num += l1->val;
            l1 = l1->next;
        }
        else{
            tmp_num += l1->val + l2->val;
            l1 = l1->next;
            l2 = l2->next;
        }
        if (tmp_num >= 10) {
            tmp_num = tmp_num % 10;
            is_carry_bit = true;
        }else
            is_carry_bit = false;
        tmp_p = (struct ListNode *) malloc(sizeof(struct ListNode));
        tmp_p->val = tmp_num;
        p->next = tmp_p;
        p = p->next;

    }
    if(is_carry_bit) {
        tmp_p = (struct ListNode *) malloc(sizeof(struct ListNode));
        tmp_p->val = 1;
        p->next = tmp_p;
        p = p->next;
    }
    p->next = NULL;
    return head;
}

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.

 

int lengthOfLongestSubstring(char* s) {
    char sub_str[200] = "";
    char tmp_str[200] = "";
    bool is_rep = false;
    int k, h, i = 0, j = 0, max_len = 0, sub_len = 0;
    while (*(s + i) != '') {
        while (*(sub_str + j) != '') {
            if (*(sub_str + j) == *(s + i)) {
                is_rep = true;
                break;
            }
            j++;
        }
        // if the char isn't repeat, add it to the sub_str
        if (!is_rep) {
            *(sub_str + sub_len++) = *(s + i);
            *(sub_str + sub_len) = '';
        }
        else {
            // if the sub_str is bigger than the max_sub_str, reset the max_len
            if (sub_len > max_len)
                max_len = sub_len;
            // reset the sub_str when the char is repeat
            for (k = j + 1, h = 0; k < sub_len; k++,h++)
                *(tmp_str + h) = *(sub_str + k);
            *(tmp_str + h) = *(s + i);
            *(tmp_str + h + 1) = '';
            strcpy(sub_str, tmp_str);
            sub_len = h + 1;
        }
        i++; j = 0;
        is_rep = false;
    }
    if (sub_len > max_len)
        max_len = sub_len;
    return max_len;
}

9. Palindrome Number

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

bool isPalindrome(int x) {
    if (x < 0)
        return false;
    int base_num = 1,tmp = x/10;
    while(tmp > 0) {
        tmp = tmp /10;
        base_num *= 10;
    }
    int left_num, right_num;
    while(x > 0) {
        left_num = x / base_num;
        right_num = x % 10;
        if(left_num != right_num)
            return false;
        x = (x - left_num*base_num - left_num) / 10;
        base_num = base_num / 100;
    }
    return true;
}

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (NULL == l1) return l2;
    if (NULL == l2) return l1;
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)), *p_objlst, *tmp, *p_l1 = l1, *p_l2 = l2;
    if (p_l1->val <= p_l2->val) {
        head->val = p_l1->val;
        p_l1 = p_l1->next;
    }else{
        head->val = p_l2->val;
        p_l2 = p_l2->next;
    }
    p_objlst = head;
    while (p_l1 != NULL || p_l2 != NULL) {
        tmp = (struct ListNode *) malloc(sizeof(struct ListNode));
        if (p_l1 == NULL) {
            tmp->val = p_l2->val;
            p_l2 = p_l2->next;
            p_objlst->next = tmp;
            p_objlst = p_objlst->next;
            continue;
        }
        if (p_l2 == NULL) {
            tmp->val = p_l1->val;
            p_l1 = p_l1->next;
            p_objlst->next = tmp;
            p_objlst = p_objlst->next;
            continue;
        }
        if (p_l1->val >= p_l2->val) {
            tmp->val = p_l2->val;
            p_l2 = p_l2->next;
        }else {
            tmp->val = p_l1->val;
            p_l1 = p_l1->next;
        }
        p_objlst->next = tmp;
        p_objlst = p_objlst->next;
    }
    p_objlst->next = NULL;
    return head;
}

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode(0)
        if l1.val <= l2.val:
            head.val = l1.val
            l1 = l1.next
        else:
            head.val = l2.val
            l2 = l2.next
        p = head
        while l1 != None or l2 != None:
            tmp = ListNode(0)
            if l1 is None:
                tmp.val = l2.val
                l2 = l2.next
                p.next=tmp
                p = p.next
                continue
            if l2 is None:
                tmp.val = l1.val
                l1 = l1.next
                p.next=tmp
                p = p.next
                continue
            if l1.val >= l2.val:
                tmp.val = l2.val
                l2 = l2.next
            else:
                tmp.val = l1.val
                l1 = l1.next
            p.next=tmp
            p = p.next
        return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = new ListNode(0);
        if(l1.val <= l2.val) {
            head.val = l1.val;
            l1 = l1.next;
        }else{
            head.val = l2.val;
            l2 = l2.next;
        }
        ListNode p = head, tmp;
        while (l1 != null || l2 != null) {
            tmp = new ListNode(0);
            if(l1 == null) {
                tmp.val = l2.val;
                l2 = l2.next;
                p.next=tmp;
                p = p.next;
                continue;
            }
            if(l2==null) {
                tmp.val = l1.val;
                l1 = l1.next;
                p.next=tmp;
                p = p.next;
                continue;
            }
            if(l1.val >= l2.val) {
                tmp.val = l2.val;
                l2 = l2.next;
            } else {
                tmp.val = l1.val;
                l1 = l1.next;
            }
            p.next=tmp;
            p = p.next;
        }
        return head;
    }
}

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.

int strStr(char* haystack, char* needle) {
    if (*needle == '')
        return 0;
    int j = 0, i = 0, tmp_i;
    bool flag = true;
    while (*(haystack+i) != '') {
        tmp_i = i;
        while (*(needle+j) != '') {
            if(*(haystack+tmp_i) == '')
                return -1;
            if(*(needle+j) != *(haystack+tmp_i))
                flag = false;
            j++;
            tmp_i++;
        }
        if(flag == true)
            return i;
        j = 0;
        i++;
        flag = true;
    }
    return -1;
}

public class Solution {
    public int strStr(String haystack, String needle) {
        int lenH = haystack.length(), lenN = needle.length();
        for (int i = 0; i <= lenH-lenN; i++)
            if(haystack.substring(i, i+lenN).equals(needle))
                return i;
        return -1;
    }
}

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        lenH = len(haystack)
        lenN = len(needle);
        for i in range(lenH-lenN+1):
            if haystack[i: i+lenN] == needle:
                return i
        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.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *p1 = head, *p2 = head, *p3;
    for (int i = 0; i <n; i++)
        p1 = p1->next;
    if (p1 == NULL)
        return p2->next;
    while (p1->next != NULL)  {
        p1 = p1->next;
        p2 = p2->next;
    }
    p3 = p2;
    p2 = p2->next->next;
    p3->next = p2;
    return head;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = head, p2 = head, p3;
        for(int i = 0; i < n; i++)
            p1 = p1.next;
        if(p1 == null)
            return p2.next;
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p3 = p2;
        p2 = p2.next.next;
        p3.next = p2;
        return head;
    }
}

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p1 = p2 = head
        for i in range(n):
            p1 = p1.next
        if p1 is None:
            return p2.next
        while p1.next is not None:
            p1 = p1.next
            p2 = p2.next
        p3 = p2
        p2 = p2.next.next
        p3.next = p2
        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.

 

class Solution(object):
    def isValid(self, s):
        stack = []
        for i in range(len(s)):
            ch = s[i]
            if ch in ['(','[','{']:
                stack.append(ch)
            elif ch in [')', ']', '}']:
                if not stack:
                    return False
                tmp_ch = stack.pop()
                if ch == ')':
                    if tmp_ch != '(':
                        return False
                if ch == '}':
                    if tmp_ch != '{':
                        return False
                if ch == ']':
                    if tmp_ch != '[':
                        return False
            else:
                return False
        if stack:
            return False
        return True

public class Solution {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<String>();
        String ch, tmp_ch;
        for (int i = 0; i < s.length(); i++) {
            ch = String.valueOf(s.charAt(i));
            if ( ch.equals("(") || ch.equals("{")
                || ch.equals("[") ) {
                    stack.push(ch);
                }
            else if( ch.equals(")") || ch.equals("}")
                || ch.equals("]") ){
                    if (stack.isEmpty())
                        return false;
                    tmp_ch = stack.pop();
                    if (ch.equals(")"))
                        if(!tmp_ch.equals("("))
                            return false;
                    if (ch.equals("}"))
                        if(!tmp_ch.equals("{"))
                            return false;
                    if (ch.equals("]"))
                        if(!tmp_ch.equals("["))
                            return false;
                }
            else
                return false;
        }
        if(!stack.isEmpty())
            return false;
        return true;
    }
}