1. Two Sum

Difficulty : Easy
Description:

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

Solution :

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        placeHolder = dict() 
        for i, x in enumerate(nums):
            if target - x in placeHolder:
                return placeHolder[target - x], i
            else:
                    placeHolder[x] = i

        return false

常见结题思路是暴力遍历(Brute Force), 时间复杂度会是O(N2), 空间复杂度为O(1).
可以通过维护一个字典来记录遍历过的元素和其对应index. 当遍历到新的元素时, 可以将target和新元素的差值和字典中的记录进行比较, 如果存在对应记录, 说明该差值存在, 并且对应索引是字典中差值对应的值, 返回相应答案即可.

2. Add Two Numbers

Difficulty : Medium
Description :

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.

Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution :

3

4. Median of Two Sorted Arrays

Difficulty : Hard
Description :

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

You may assume nums1 and nums2 cannot be both empty.

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.5There are two sorted arrays nums1 and nums2 of size m and n respectively.

Solution:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1 = len(nums1)
        len2 = len(nums2)

        index_l = []

        total_len = len1 + len2
        if total_len % 2 == 0:
            index_l.append(total_len / 2 - 1)
            index_l.append(total_len / 2)
        else:
            index_l.append((total_len -1 ) / 2)

        result = 0
        index_1 = 0 
        index_2 = 0
        for i in range(total_len):
            current = 0
            if index_1 >= len1 and index_2 < len2:
                current = nums2[index_2]
                index_2 += 1
            elif index_2 >= len2 and index_1 < len1:
                current = nums1[index_1]
                index_1 +=1
            elif nums1[index_1] < nums2[index_2]:
                current = nums1[index_1]
                index_1 += 1
            else:
                current = nums2[index_2]
                index_2 += 1
            if index_l :
                if i in index_l:
                    result += current
                    index_l.remove(i)
            else :
                break

        if total_len % 2 == 1:
            return result
        else:
            return result / 2

5. Longest

Difficulty : Medium
Description :

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: “babad” Output: “bab”
Note: “aba” is also a valid answer.

Example 2:
Input: “cbbd” Output: “bb”

Solution
python3