001 Two Sum [Easy]

题目

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

时间复杂度

\(O(n)\)

思路

比较暴力的做法就是用两个循环来穷举,这样的话时间复杂度会达到 \(O(n^2)\)。

另外一种思路就是使用一个 dict 来保存外循环中 target 与 num 的差值,这样在数组中只要发现这个值就可以直接返回了,而在 dic 查找的时间复杂度为 \(O(1)\)。

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        for i, num in enumerate(nums):
            if num in dic:
                return [dic[num], i]
            else:
                dic[target - num] = i

002 Add Two Numbers [Medium]

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

时间复杂度

\(O(n)\)

思路

把两个数相加存在链表里,这两个数字的每一位都存在链表中,并且链表是反转的。思路很简单,就是遍历链表,把数取出来,然后加完后再添加到链表中。

代码写得很直白。

代码

# 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
        """
        num1 = []
        num2 = []
        current = l1
        while current != None:
            num1.append(str(current.val))
            current = current.next
        current = l2
        while current != None:
            num2.append(str(current.val))
            current = current.next
        num1 = ''.join(num1)[::-1]
        num2 = ''.join(num2)[::-1]
        sum = int(num1) + int(num2)
        first = ListNode(str(sum)[0])
        for i in str(sum)[1:]:
            oldfirst = first
            first = ListNode(i)
            first.next = oldfirst
        return first

笔记

翻了一下 discuss,发现我的解法实在是太 dirty 了。

下面这一段代码我认为还是非常优美的实现:

class Solution:
    def addTwoNumbers(self, l1, l2):
        def toint(node):
            return node.val + 10 * toint(node.next) if node else 0
        def tolist(n):
            node = ListNode(n % 10)
            if n > 9:
                node.next = tolist(n // 10)
            return node
        return tolist(toint(l1) + toint(l2))

非递归版本:

class Solution:
    def addTwoNumbers(self, l1, l2):
        def toint(node):
            return node.val + 10 * toint(node.next) if node else 0
        n = toint(l1) + toint(l2)
        first = last = ListNode(n % 10)
        while n > 9:
            n /= 10
            last.next = last = ListNode(n % 10)
        return first

解释一下思路。

首先 toint(node) 函数是将链表转化成 int 类型的数据,因为 Python 中 int 可以存非常大的数,所以不用考虑链表的长度。算法也很简单,因为链表是转置的,所以高位在链表后面,依次乘以 10 的 n 次方再相加就可以了。

tolist(n) 函数式将计算好的数据转化成链表,再纸上拿一个一个例子画一个图就很好理解了。node = ListNode(n % 10) 每一次递归都创建一个节点来存放某一位的数据,tolist(n // 10) 每一次递归都截取一位数字。

非递归的方法类似。

007 Reverse Integer [Easy]

题目

Reverse digits of an integer.

The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Ex:

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

思路

这道题很简单,但是要考虑转置之后会不会溢出,但是 Python 的 int 是不会溢出的,所以就需要手动判断一下,INT32 最大值是 \(2^{31}-1\),用十六进制表示就是 0x7FFFFFFF

代码

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            result = -(int(str(x).lstrip('-')[::-1]))
        else:
            result = int(str(x)[::-1])
        
        if abs(result) > 0x7FFFFFFF:
            return 0
        return result