LeetCode笔记

题目列表

1. 两数之和 2. 两数相加 3. 无重复字符的最长子串

1. 两数之和

暴力循环

最简单的方法是使用暴力循环的方法，时间复杂度为$O(n^2)$。

class Solution(object):
def twoSum(self, nums, target):
    if len(nums) == 0:
        return []
    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if (nums[i] + nums[i + j + 1] == target):
                return [i, i + j + 1]

利用字典特性实现哈希查表

较优解是利用python字典来当作hash表，从而使时间复杂度为$O(n)$。

首先创建一个空的hash表，key值用来存储nums的值，value用来存储nums的下标。然后遍历数组，每次都用目标值减去当前数组的值得到我们要寻找的值。接着，在hash表中进行查表，如果key中存在这个值，则返回目标值。如果不存在，则先添加当前值和它的下标进入数组，把这一步放在最后是为了防止查表时自身与自身相加，接着遍历数组直到找到对应的下标。
这个方法巧妙的地方在于每一次当前值都会与前面遍历过的所有值进行查表判断，而且不会与自身进行查表。

class Solution(object):
def twoSum(self, nums, target):
    dict = {}
    if len(nums) == 0:
        return []
    for i in range(len(nums)):
        tar = target - nums[i]
        index = dict.get(tar)
        if (index != None):
            return [i, index]
        dict[nums[i]] = i

2. 两数相加

倒序加法公式

看到这个题后，我第一时间想到的就是直接使用小学加法竖式运算进行操作。首先来说，需要定义两个指针curNode1和curNode2来分别遍历两个倒序链表。由于两个链表可能不一样长，我们需要考虑到这种情况。其次，设置一个add变量来作为进位符。当两个指针都不为空时，两个变量与add进行加和操作，然后判断加和值是否大于零，如果大于的话需要进行取模操作，并且add变量进行进位（进位只可能为1，记得在下次加和后进位归零）。最后将得到的结果并入链表中。对于只有一个指针不为空的情况，只需要忽略另一个指针即可，其他操作相同。最后，由于存在最后所有加完还需要进一位的情况，还需要将最后一个不为零的进位符并入链表。

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        res = None
        cur_res = None
        add = 0
        curNode1 = l1
        curNode2 = l2
        while (curNode1 != None or curNode2 != None):
            sum = None
            if (curNode1 != None and curNode2 != None):
                sum = curNode1.val + curNode2.val + add
                if add > 0:
                    add = 0
                if sum >= 10:
                    sum = sum % 10
                    add = 1
                curNode1 = curNode1.next
                curNode2 = curNode2.next
            elif (curNode1 != None and curNode2 == None):
                sum = curNode1.val + add
                if add > 0:
                    add = 0
                if sum >= 10:
                    sum = sum % 10
                    add = 1
                curNode1 = curNode1.next
            elif (curNode1 == None and curNode2 != None):
                sum = curNode2.val + add
                if add > 0:
                    add = 0
                if sum >= 10:
                    sum = sum % 10
                    add = 1
                curNode2 = curNode2.next
            if res == None:
                res = ListNode(val=sum, next=None)
                cur_res = res
            else:
                new_res = ListNode(val=sum, next=None)
                cur_res.next = new_res
                cur_res = cur_res.next
        if add == 1:
            new_res = ListNode(val=1, next=None)
            cur_res.next = new_res
        return res

3. 无重复字符的最长子串

这道题先大概看了一下题解的思路，然后根据思路再写代码

滑动窗口

1. 这个方法的思路非常巧妙，如果使用暴力遍历的话，时间复杂度将会是$O(n^2)$。而我们根本不需要以每个字符为开头进行遍历。
2. 我们只需要使用两个指针指向当前字符串的起始位置，然后只要长度没有达到最大值，就移动末尾指针加一。在每次无重复字符串长度达到最大值时，把字符串开头指针向右移动一位，然后继续重复上述步骤，并记录最大长度。
3. 这么做的原理是，假设一个不重复的字符串起始位置是$[i, j]$，那么第$j + 1$个字符就会与前面字符串$[i, j]$中的一个字符重复，对于字符串$[i+1, j]$来说，它舍去了第一个位置的字符并且这是一个长度小于字符串$[i, j]$的子字串，那么这一串子字符串就相当于把$[i+1, j]$的字符都遍历了一遍，但是得到的长度是肯定小于$[i, j]$的。因此，我们可以默认这一部分已经遍历过了，从而续接着对后面的字符进行遍历，查看是否与前面的字符串有重复。
4. 在代码实现过程中，首先不要忘记判断0值。我使用了cur1，cur2分别作为首尾指针并使用list列表来模拟队列，实现对字符串的添加，去除和重复查找

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        cur1 = 0
        cur2 = 1
        res = 1
        list = []
        list.append(s[cur1])
        while(cur2 < len(s)):
            while (cur2 < len(s) and s[cur2] not in list ):
                list.append(s[cur2])
                cur2 += 1
                length = cur2 - cur1
                if length > res:
                    res = length
            cur1 += 1
            list.pop(0)
        return res