今天开始刷Leetcode上面的算法题。我会更新我刷题过程中提交的代码(成功和不成功的都有)和比较好的解法

第二题 Add Two Numbers

题目的意思：输入两个链表，这两个链表都是倒序的数字，相加后返回倒序的链表。比如：

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

Output: 7 -> 0 -> 8

（342 + 465 = 807）

我的解法：

思路很简单，把两个链表分别转换成数字，相加后把结果再转换成链表

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    # @param {ListNode} l1

    # @param {ListNode} l2

    # @return {ListNode}

    def addTwoNumbers(self, l1, l2):		#以上是leetcode给与的部分，下面开始编码

    	 #分别把l1、l2转成正序的字符串

        a=str(l1.val)

        b=str(l2.val)

        while l1.next != None:

            a += str(l1.next.val)

            l1 = l1.next

        a = a[::-1]

        while l2.next != None:

            b += str(l2.next.val)

            l2 = l2.next

        b = b[::-1]

        #获得两个数相加的值

        c = int(a) + int(b)

        #把c转换成逆序链表

        li = ListNode(c%10)	#头结点

        if c//10 < 1:			#当c只是一位数的时候

            return li

        #c为多位数，思路是对c/10求余数，把余数放在节点的值中，连接各节点

        c = c//10

        tem = li

        while c//10 >= 1:

            t = ListNode(c%10)

            tem.next = t

            tem = t

            c = c//10

        #把最后一位放入节点

        t = ListNode(c)

        tem.next = t

        return li

以上是我的解法，虽然通过了测试，但是执行的时间有193ms，在python中算比较慢的了...

所以我去网上找了更好的解法：

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    # @return a ListNode

	 def addTwoNumbers(self, l1, l2):		#以上是leetcode给与的部分，下面开始编码

        dummy, flag = ListNode(0), 0

        head = dummy		#dummy是头结点，无意义

        while flag or l1 or l2:

            node = ListNode(flag)

            if l1:

                node.val += l1.val

                l1 = l1.next

            if l2:

                node.val += l2.val

                l2 = l2.next

            flag = node.val / 10		#注意这个flag，在下一次新建节点的时候会把flag的值给该节点

            node.val %= 10

            head.next = node

            head = head.next  # head.next, head = node, node

        return dummy.next

第三题 Longest Substring Without Repeating Characters

题目的意思：给一个字符串，找出这个字符串中没有重复元素的最大子字符串，返回这个子字符串的长度

我的解法：

我的思路是新建一个字符串(tem)，依次从给予的字符串中读字符，如果tem没有该字符，则把该字符插入tem中，如果有该字符，则在tem中找出上次出现这个字符的位置post，并删除(0,post)的所有字符，然后把该字符插入tem，同时我新建了count和maxNum变量，用来记录最长子字符串的长度，返回maxNum

class Solution:

    # @param {string} s

    # @return {integer}

    def lengthOfLongestSubstring(self, s):    #以上是leetcode给与的部分，下面开始编码

        tem = ''

        count = 0

        maxNum = 0

        for i in range(len(s)):

            if s[i] not in tem:

                tem += s[i]

                count += 1

                maxNum = max(count, maxNum)

            else:

                t = 0

                for j in range(i):

                    if s[j] == s[i] and j >= t:

                        t = j

                for x in range(t+1):

                    tem = tem[x+1:]

                    count -= 1

                tem += s[i]

                count += 1

        print(tem)

        return maxNum

可是这个代码提交上去后，给了我个Time Limit Exceeded(未通过)，点开一看，看到了个超长的字符串未通过测试...时间过长

下面这个算法，大致思路和我上一个一样，但是使用了哈希表，让它来记录字符的索引，在哈希表中先把每个字符的值初始化为-1，出现第一次就把值改为该字符所在字符串的位置

class Solution:

    # @param {string} s

    # @return {integer}

    def lengthOfLongestSubstring(self, s):

        start = 0

        maxNum = 0

        dic = {}

        for i in range(len(s)):

            dic[s[i]] = -1

        for i in range(len(s)):

            if dic[s[i]] != -1:

                while start <= dic[s[i]]:

                    dic[s[start]] = -1

                    start += 1

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

            dic[s[i]] = i

        return maxNum