[leetcode]第一部分

Two Sum

Problem

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

首先,最简单的想法是:两个指针,直接从前往后,进行计算,直到遇到和为target的两个数时,直接返回索引.但是很明显,这种方法时间复杂度非常高,为$$O(n^2)$$,其中n为数组长度.

给出python的实现:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numLen = len(nums)
        for i in range(numLen):
            for j in range(i+1, numLen):
                if nums[i] + nums[j] == target:
                    return [i,j]

提交时间为5529 ms,想想是否有改进的方法,是否可以避免进行一些无用的计算呢?在这里,想到了:如果数组是有序的(即使不是有序的,也可以在优于$$O(n^2)$$的时间复杂度内排序成功),那么可以直接使用两个指针分别从首尾进行匹配,这样可以降低时间复杂度.

改进后的代码如下:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        origin = list()
        # copy the list
        for i in range(len(nums)):
            origin.append(nums[i])
        self.quickSort(origin, 0, len(origin)-1)
        i = 0
        j = len(origin) - 1
        while i < j:
            nowSum = origin[i] + origin[j]
            if nowSum == target:
                break
            elif nowSum > target:
                j -= 1
            else:
                i += 1
        if i < j:
            start = -1
            end = -1
            for k in range(len(nums)):
                if nums[k] == origin[i]:
                    start = k
                elif nums[k] == origin[j]:
                    end = k
            if start > -1 and end > -1:
                if start > end:
                    return [end, start]
                else:
                    return [start, end]

    # quick sort
    def quickSort(self, origin, start, end):
        """
        :type origin: List[int]
        :type start: int
        :type start: end
        """
        if start > end:
            return
        pivot = origin[start]
        i = start 
        j = end
        while i!=j:
            while origin[j] >= pivot and i<j :
                j -= 1
            while origin[i] <= pivot and i<j :
                i += 1
            if i < j:
                t = origin[i]
                origin[i] = origin[j]
                origin[j] = t
        origin[start] = origin[i]
        origin[i] = pivot
        self.quickSort(origin, start, i-1)
        self.quickSort(origin, i+1, end)

提交之后发现报错了,看了下错误的案例:

nums = [3,3]
target = 6

原来是木有考虑有相同数字的情况,在这里,可以添加一个标记字段:isSet来标识是否已经匹配第一个数字,如果有就继续,这样就不会误判啦另外,在这里,我们使用的是快排,快排的平均时间复杂度是$$O(nlog(n))$$,而在数组本来有序的情况下,时间复杂度非常高,为$$O(n^2)$$,因此,为了避免这种情况,我们可以先将数组先进行一个随机处理.因此,改进的算法如下:

import random

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        origin = list()
        # copy the list
        for i in range(len(nums)):
            origin.append(nums[i])
        self.quickSort(origin, 0, len(origin)-1)
        i = 0
        j = len(origin) - 1
        while i < j:
            nowSum = origin[i] + origin[j]
            if nowSum == target:
                break
            elif nowSum > target:
                j -= 1
            else:
                i += 1
        if i < j:
            start = -1
            end = -1
            isSet = False
            for k in range(len(nums)):
                if nums[k] == origin[i] and not isSet:
                    start = k
                    isSet = True
                elif nums[k] == origin[j]:
                    end = k
            if start > -1 and end > -1:
                if start > end:
                    return [end, start]
                else:
                    return [start, end]

    # quick sort
    def quickSort(self, origin, start, end):
        """
        :type origin: List[int]
        :type start: int
        :type start: end
        """
        if start > end:
            return
        self.randomList(origin, start, end)
        pivot = origin[start]
        i = start 
        j = end
        while i!=j:
            while origin[j] >= pivot and i<j :
                j -= 1
            while origin[i] <= pivot and i<j :
                i += 1
            if i < j:
                self.swap(origin, i, j)
        origin[start] = origin[i]
        origin[i] = pivot
        self.quickSort(origin, start, i-1)
        self.quickSort(origin, i+1, end)


    def swap(self, origin, a, b):
        if a >= len(origin) or b >= len(origin):
            return
        tmp = origin[a]
        origin[a] = origin[b]
        origin[b] = tmp

    def randomList(self, origin, start, end):
        tmp = random.randint(start, end)
        self.swap(origin, start, tmp)

此时,提交时间优化到了118 ms.

更新:现在才发现自己把问题想复杂了…其实只要借助一个复制的hash结构就可以以$$O(n)$$的时间复杂度解决…

方法1:
两步循环,第一遍循环初始化hash,第二遍循环去找相应的索引.
注意,这种情况,即使碰到有数字重复的情况也是能满足条件的,重点是有一个条件:numDict[complement] != i,由于题干中强调了只有一个正解,因此如果有两个数相同,那么必定target只能为该重复数的和.虽然在第一遍初始化hash时,会覆盖前面的数字,但是在第二遍循环的时候会从前往后去找,还是能找到相应的数字.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numDict = dict()
        for i in range(len(nums)):
            numDict[nums[i]] = i
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in numDict and numDict[complement] != i:
                j = numDict[complement]
                if i > j:
                    return [j, i]
                else:
                    return [i, j]

此时,提交的耗时缩短为48 ms.

方法2:
一遍循环:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numDict = dict()
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in numDict:
                j = numDict[complement]
                if i > j:
                    return [j, i]
                else:
                    return [i, j]
            numDict[nums[i]] = i

此时,提交的耗时缩短为:45 ms.

复杂度分析

  • 时间复杂度:后面两种方法的时间复杂度均为$$O(n)$$,其中n表示数组的长度
  • 空间复杂度:$$O(n)$$,主要是存储hash结构的空间,最多会存储n个元素

一些思考

小结: 遇到这种类型的题目,可以不用一开始就想太复杂,多思考用额外的存储结构来实现时间复杂度的降低.

Add Two Numbers

Problem

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

思路:很明显,这道题涉及到的数据结构应该是指针.定义两个指针,同时移动,定义一个标志位,用来标志是否需要进位,另外有一个小trick:为了避免出现老是需要判断哪个先移动到头的情况,可以在正式的计算之前,将两个ListNode排好序,就可以避免出现一大段乱七八糟的判断了.

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

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """       
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l1, l2 = self.sortNodeList(l1, l2)
        flag = 0
        retNode = l2
        pre = l2
        while l1 is not None or l2 is not None:
            if l1 is not None:
                nowSum = l1.val + l2.val + flag
            else:
                nowSum = l2.val + flag
            flag = nowSum / 10
            nowVal = nowSum % 10
            l2.val = nowVal
            if l1 is not None:
                l1 = l1.next
            pre = l2
            l2 = l2.next
        if flag > 0:
            newNode = ListNode(flag)
            pre.next = newNode
        return retNode



    # sort the two ListNodes
    def sortNodeList(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rType: ListNode, ListNode
        """
        now1 = l1
        now2 = l2
        while now1 is not None and now2 is not None:
            now1 = now1.next
            now2 = now2.next
        if now1 is None:
            return l1, l2
        else:
            return l2, l1

小提醒:第一次写的时候,忽略了最后的进位问题,忘记引入pre这个变量,由于l2已经指向了None,因此设置l2.next的时候会报错,因此,需要定义一个pre变量指向当前节点.

复杂性分析

  • 时间复杂性: $$O(max(m,n))$$,mn分别是两个ListNode的长度
  • 空间复杂度:$$O(max(m,n))$$,新ListNode的最大长度为$$max(m,n)+1$$

运行时间为: 120 ms.

一些思考

小结:审清题目,多用实际例子去模拟,想通思路~

打赏

mickey

记录生活,写给几十年后的自己。