LeetCode 1-5 题

1.twosum

题目

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

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

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

return [0, 1].

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums)<=1:
            return False
        buff_dict = {}
        for i in range(len(nums)):
            if nums[i] in buff_dict:
                return [buff_dict[nums[i]],i]
            else:
                buff_dict[target - nums[i]] = i
                print buff_dict

if __name__ == '__main__':
    Solution().twoSum([3,2,4], 6)

class Solution(object):

def twoSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[int]

"""

if len(nums)<=1:

return False

buff_dict = {}

for i in range(len(nums)):

if nums[i] in buff_dict:

return [buff_dict[nums[i]],i]

else:

buff_dict[target - nums[i]] = i

print buff_dict

if __name__ == '__main__':

Solution().twoSum([3,2,4], 6)

输出结果分析

第一次
buff_dict={3:0,}与0位置匹配的数字是3
第二次
buff_dict={3: 0, 4: 1}与1位置匹配的数字是4
第三次
因为nums[2]=4在buff_dict中，所以直接返回结果即可，对应的下标为[buff_dict[nums[i]],i]

算法复杂度

只要一个for循环，算法复杂度为O(n)

注意点

for循环和if语句的用法，for循环从0开始
return False而不是return false
上面的用法是1维hash表

2. addTwoNumbers

题目

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.

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

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

代码

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        root = n = ListNode(0)
        while l1 or l2 or carry:
            v1 = v2 =0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2=l2.next
            carry,val = divmod(v1+v2+carry,10)
            n.next = ListNode(val)
            n = n.next
        return root.next

class Solution(object):

def addTwoNumbers(self, l1, l2):

"""

:type l1: ListNode

:type l2: ListNode

:rtype: ListNode

"""

carry = 0

root = n = ListNode(0)

while l1 or l2 or carry:

v1 = v2 =0

if l1:

v1 = l1.val

l1 = l1.next

if l2:

v2 = l2.val

l2=l2.next

carry,val = divmod(v1+v2+carry,10)

n.next = ListNode(val)

n = n.next

return root.next

注意点

是链表相加，所以要构造ListNode结构
链表赋值之后要到next的位置，不断往后走，root一开始不动
divmod函数可以求两个数相除的商和余数。

3. Longest Substring Without Repeating Characters

题目

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = maxLength = 0
        usedChar = {}
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]]+1
                print "----------------------------------"
                print "111111111111"
            else:
                maxLength = max(maxLength,i - start + 1)
                print "----------------------------------"
                print "222222222222"
            usedChar[s[i]]=i
            print usedChar
            print start
            print maxLength
        return maxLength

if __name__ == '__main__':
    Solution().lengthOfLongestSubstring("abcabcbb")

class Solution(object):

def lengthOfLongestSubstring(self, s):

"""

:type s: str

:rtype: int

"""

start = maxLength = 0

usedChar = {}

for i in range(len(s)):

if s[i] in usedChar and start <= usedChar[s[i]]:

start = usedChar[s[i]]+1

print "----------------------------------"

print "111111111111"

else:

maxLength = max(maxLength,i - start + 1)

print "----------------------------------"

print "222222222222"

usedChar[s[i]]=i

print usedChar

print start

print maxLength

return maxLength

if __name__ == '__main__':

Solution().lengthOfLongestSubstring("abcabcbb")

输出分析

输入"abcabcbb"，首先几次因为没有重复元素出现，代码不断增加maxlength，然后重复出现了a，b，c之后，如果start的数目小于等于该元素出现的起始位置，计算substring的start的位置就变了，要更新它，即加一。如果start不用更新且start大于当前元素出现的次数，那么就计算maxlength。看是否要更新。具体如下：

----------------------------------
222222222222
{'a': 0}
0
1
----------------------------------
222222222222
{'a': 0, 'b': 1}
0
2
----------------------------------
222222222222
{'a': 0, 'c': 2, 'b': 1}
0
3
----------------------------------
111111111111
{'a': 3, 'c': 2, 'b': 1}
1
3
----------------------------------
111111111111
{'a': 3, 'c': 2, 'b': 4}
2
3
----------------------------------
111111111111
{'a': 3, 'c': 5, 'b': 4}
3
3
----------------------------------
111111111111
{'a': 3, 'c': 5, 'b': 6}
5
3
----------------------------------
111111111111
{'a': 3, 'c': 5, 'b': 7}
7
3
[Finished in 0.2s]

----------------------------------

222222222222

{'a': 0}

----------------------------------

222222222222

{'a': 0, 'b': 1}

----------------------------------

222222222222

{'a': 0, 'c': 2, 'b': 1}

----------------------------------

111111111111

{'a': 3, 'c': 2, 'b': 1}

----------------------------------

111111111111

{'a': 3, 'c': 2, 'b': 4}

----------------------------------

111111111111

{'a': 3, 'c': 5, 'b': 4}

----------------------------------

111111111111

{'a': 3, 'c': 5, 'b': 6}

----------------------------------

111111111111

{'a': 3, 'c': 5, 'b': 7}

[Finished in 0.2s]

输入"pwwkew",上面的例子在找到最大的lenth之后maxlenth就没有更新了，我们可以看看这个例子，一开始pw最大，到第三次出现了w，所以start的位置变成2，后面出现了新的ke，所以最后maxlength会增加，然后又出现w，所以start变成3.但length要重新比较。

----------------------------------
222222222222
{'p': 0}
0
1
----------------------------------
222222222222
{'p': 0, 'w': 1}
0
2
----------------------------------
111111111111
{'p': 0, 'w': 2}
2
2
----------------------------------
222222222222
{'p': 0, 'k': 3, 'w': 2}
2
2
----------------------------------
222222222222
{'p': 0, 'k': 3, 'e': 4, 'w': 2}
2
3
----------------------------------
111111111111
{'p': 0, 'k': 3, 'e': 4, 'w': 5}
3
3
[Finished in 0.1s]

----------------------------------

222222222222

{'p': 0}

----------------------------------

222222222222

{'p': 0, 'w': 1}

----------------------------------

111111111111

{'p': 0, 'w': 2}

----------------------------------

222222222222

{'p': 0, 'k': 3, 'w': 2}

----------------------------------

222222222222

{'p': 0, 'k': 3, 'e': 4, 'w': 2}

----------------------------------

111111111111

{'p': 0, 'k': 3, 'e': 4, 'w': 5}

[Finished in 0.1s]

注意点

这个问题的解决思路其实是这样，对于一个字符s，我们可以遍历它其中的每一个元素i，并且从i开始数，到后面不重复的子字符的长度是多少。最后只要比较所有i开始的子字符的长度，那么就可以了。但是在这个思路的基础上，我们可以再次优化，也就是说我们不用吧所有的i分别遍历，我们只需要过一遍。每次记录计算子字符的开始位置和最大长度的值，并且在出现重复元素且重复元素的位置在开始位置之后已经出现过时，就更新开始位置。并且重新计算length并与maxlength比较，就是我们现在看到的算法。
利用了滑窗法和hash表的思想。

4.Median of Two Sorted Arrays

题目

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

Example1:

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

The median is 2.0

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example2:

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

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

nums1 = [1, 2]

nums2 = [3, 4]

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

解决方法

要解决这个问题，我们需要了解“中位数的用途是什么”。在统计中，中位数用于：
将一个集合划分为两个相等长度的子集合，其中一个子集合总是大于另一个。
如果我们理解中位数的用法，我们非常接近答案。
具体见这里的说明

代码

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m,n = len(nums1),len(nums2)
        if m>n:
            nums1,nums2,m,n = nums2,nums1,n,m
        if n == 0:
            raise ValueError

        imin,imax,half_len = 0,m,(m+n+1)/2
        while imin<=imax:
            i = (imin+imax)/2
            j = half_len-i
            if i<m and nums2[j-1]>nums1[i]:
                imin = i+1
            elif i>0 and nums1[i-1]>nums2[j]:
                imax = i-1
            else:
                if i==0:
                    max_left = nums2[j-1]
                elif j==0:
                    max_left = nums1[i-1]
                else:
                    max_left = max(nums1[i-1],nums2[j-1])
                if (m+n)%2==1:
                    return max_left
                if i==m:
                    min_right = nums2[j]
                elif j==n:
                    min_right = nums1[i]
                else:
                    min_right = min(nums1[i],nums2[j])
                return (max_left+min_right)/2.0

class Solution(object):

def findMedianSortedArrays(self, nums1, nums2):

"""

:type nums1: List[int]

:type nums2: List[int]

:rtype: float

"""

m,n = len(nums1),len(nums2)

if m>n:

nums1,nums2,m,n = nums2,nums1,n,m

if n == 0:

raise ValueError

imin,imax,half_len = 0,m,(m+n+1)/2

while imin<=imax:

i = (imin+imax)/2

j = half_len-i

if i<m and nums2[j-1]>nums1[i]:

imin = i+1

elif i>0 and nums1[i-1]>nums2[j]:

imax = i-1

else:

if i==0:

max_left = nums2[j-1]

elif j==0:

max_left = nums1[i-1]

else:

max_left = max(nums1[i-1],nums2[j-1])

if (m+n)%2==1:

return max_left

if i==m:

min_right = nums2[j]

elif j==n:

min_right = nums1[i]

else:

min_right = min(nums1[i],nums2[j])

return (max_left+min_right)/2.0

算法复杂度

使用二分法对min(n，m)进行查找，算法复杂度为O(log(min(m.n)))

注意点

弄清楚数学原理，在数学上推通了，纸上写好了伪代码再变成
while语句与if条件语句的用法
二分法的使用

5.Longest Palindromic Substring

题目

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

Example1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example2:

Input: "cbbd"
Output: "bb"

Input: "cbbd"

Output: "bb"

解决方法

解决这个问题，很多人会想当然的觉得，把一个字符串反过来即可，比如caba反过来是abac，里面最大的子字符串是aba，所以这是回文。因此只要找二者最大的子字符串即可。这是一个误区，比如这个例子。
S=abacdfgdcaba, S=abacdgfdcaba,他们的最大子集是abacd，但是这不是回文。
我用的方法是，逐次遍历每一个位置，并且以他们作为中心点，向两边延伸，观察是否两边扩展得到的结果相同，如果相同的话继续扩展，否则停止这个位置，更新maxlenth，并且到下一位置去。这里要注意，回文有基数回文和偶数回文两种情况，所以我这里分了两种情况讨论。

代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        maxlenth = 1
        maxindex = 0
        maxtype = 0
        maxstring = 0
        for i in range(n):
            leftindex1 = i-1
            rightindex1 = i
            leftindex2 = i-1
            rightindex2 = i+1
            currentlen1 = 0
            currentlen2 = 1
            while leftindex1>=0 and rightindex1<=n-1 and s[leftindex1]==s[rightindex1]:
                currentlen1 += 2
                leftindex1 -= 1
                rightindex1 += 1
            while leftindex2>=0 and rightindex2<=n-1 and s[leftindex2]==s[rightindex2]:
                currentlen2 += 2
                leftindex2 -= 1
                rightindex2 += 1
            if currentlen1>=currentlen2 and currentlen1>maxlenth:
                maxlenth = currentlen1
                maxindex = i
                print maxindex
                print maxlenth
            if currentlen2>=currentlen1 and currentlen2>maxlenth:
                maxlenth = currentlen2
                maxindex = i
                print maxindex
                print maxlenth

        if maxlenth%2 :
            return s[maxindex-maxlenth/2:maxindex+maxlenth/2+1]
        else:
            return s[maxindex-maxlenth/2:maxindex+maxlenth/2]

class Solution(object):

def longestPalindrome(self, s):

"""

:type s: str

:rtype: str

"""

n = len(s)

maxlenth = 1

maxindex = 0

maxtype = 0

maxstring = 0

for i in range(n):

leftindex1 = i-1

rightindex1 = i

leftindex2 = i-1

rightindex2 = i+1

currentlen1 = 0

currentlen2 = 1

while leftindex1>=0 and rightindex1<=n-1 and s[leftindex1]==s[rightindex1]:

currentlen1 += 2

leftindex1 -= 1

rightindex1 += 1

while leftindex2>=0 and rightindex2<=n-1 and s[leftindex2]==s[rightindex2]:

currentlen2 += 2

leftindex2 -= 1

rightindex2 += 1

if currentlen1>=currentlen2 and currentlen1>maxlenth:

maxlenth = currentlen1

maxindex = i

print maxindex

print maxlenth

if currentlen2>=currentlen1 and currentlen2>maxlenth:

maxlenth = currentlen2

maxindex = i

print maxindex

print maxlenth

if maxlenth%2 :

return s[maxindex-maxlenth/2:maxindex+maxlenth/2+1]

else:

return s[maxindex-maxlenth/2:maxindex+maxlenth/2]

算法复杂度

时间复杂度为O(n^2),因为遍历字符串为O(n),而扩展字符串到他的周围可能花费O(n)的时间，而这个算法的空间复杂度为O(1)

注意点

Python字符串选择，比如s="abcdf",那么s[1:4]=s1+s[2]+s[3],即为"bcd",而不是"bcdf",切记

Blog of Dada

There is no lemon so sour, that you can't make something resembling lemonade.

LeetCode 1-5 题

1.twosum

2. addTwoNumbers

3. Longest Substring Without Repeating Characters

4.Median of Two Sorted Arrays

5.Longest Palindromic Substring