LeetCode刷题

LeetCode刷题1——两数之和

最近想要练一练代码能力，得知LeetCode这个网站挺不错的，所以便开始刷题。

LeetCode中国版

在这里主要就是练习一下python，其它编程语言可能基本不会涉及到。

从最简单的开始题——两数相加开始。

先附带一下题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

首先是最简单也是最容易想到的解法：

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

提交结果如下：

由于时间复杂度为O(n²)，自然用时较长。

接下来考虑使用哈希表的解法，代码如下：

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

此时的时间复杂度为O(n)，提交结果如下：

LeetCode刷题2——LeetCode两数相加

先附带题目：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

这题其实就是涉及了最简单的链表相加问题，没啥好说的，直接上代码：

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
        """
        n = l1.val + l2.val
        l3 = ListNode(n % 10)
        l3.next = ListNode(n // 10)
        p1 = l1.next
        p2 = l2.next
        p3 = l3
        while True:
            if p1 and p2:
                sum = p1.val + p2.val + p3.next.val
                p3.next.val = sum % 10
                p3.next.next = ListNode(sum // 10)
                p1 = p1.next
                p2 = p2.next
                p3 = p3.next
            elif p1 and not p2:
                sum = p1.val + p3.next.val
                p3.next.val = sum % 10
                p3.next.next = ListNode(sum // 10)
                p1 = p1.next
                p3 = p3.next
            elif p2 and not p1:
                sum = p2.val + p3.next.val
                p3.next.val = sum % 10
                p3.next.next = ListNode(sum // 10)
                p2 = p2.next
                p3 = p3.next
            else:
                if p3.next.val == 0:
                    p3.next = None
                break
        return l3

我这边先定义一下链表的初始化和输出：

class LinkList:
    # 新建一个头指针为空的链表
    def __init__(self):
        self.head=None
    # 将数据插入链表:
    def initList(self, data):
        # 创建头结点
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        # 逐个为 data 内的数据创建结点, 建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printList(self, head):
        if head == None:
            return
        node = head
        while node.next != None:
            print('%d -> ' % (node.val), end='')
            node = node.next
        print('%d' % (node.val))

然后后面加个主函数调用一下它：

if __name__ == '__main__':
    data1 = [2, 4, 3]
    data2 = [5, 6, 4]
    l = LinkList()
    l1 = l.initList(data1)
    l2 = l.initList(data2)
    l.printList(l1)
    l.printList(l2)
    s = Solution()
    l3 = s.addTwoNumbers(l1, l2)
    l.printList(l3)

下面是输出情况以及提交情况：

LeetCode刷题3——LeetCode无重复字符的最长子串

先附带题目：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

首先是最简单易懂的遍历大法：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)

        if length <= 1:
        	return length

        max_length = 0
        for i in range(length):
            data = s[i]
            for j in range(i + 1, length):
                if s[j] not in data:
                    data = data + s[j]
                else:
                    break
            max_length = max(max_length, len(data))

        return max_length

虽然确实简单易懂，但是从时间复杂度上来看，很有可能会超时。

下面是提交情况：

离谱哈哈，所以这次我们考虑用哈希表的方法来解决：

直接上代码：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        if length <= 1:
            return length
        head, max_length = 0, 0
        myHashMap = {}
        for index in range(length):
            if s[index] in myHashMap and head <= myHashMap[s[index]]:
                head = myHashMap[s[index]] + 1
            else:
                max_length = max(max_length, index - head + 1)
            myHashMap[s[index]] = index
        return max_length

下面是提交结果：

结束语

由于博主能力有限，博文中提及的信息，也难免会有疏漏之处。希望发现疏漏的朋友能热心指出其中的错误，以便下次修改时能以一个更完美更严谨的样子，呈现在大家面前。同时如果有更好的方法也请不吝赐教。

如果有什么相关的问题，也可以关注评论留下自己的问题，我会尽量及时发送！

然后如果这些内容对你有所帮助的话，麻烦点赞或者评论告诉我可以吗（这样我更新博客的速度才会越来越快！！！）