LeetCode DAY 1 (1-3)

LeetCode系列 争取每日更新3题 —— 一个为了有工作的fw会坚持下去的！
（自从昨天尝试着做了几道leetcode才发现我的代码能力几乎等于0…照这样下去我怕是要找不到工作了…因此从现在开始每天督促自己刷3道leetcode…并且第二天将前一天的解题过程上传到这里就当作是巩固复习吧…）

1. 两数之和（简单）

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

代码

刚开始看到这道题的时候觉得很简单，虽然题目本来就标的就是简单…..
于是一开始就这样胡乱一写…

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

这样写虽然可以做到题目要求，但是时间复杂度太高了$O(n^{2})$，因此提交的时候有时候可以通过，有时候就是时间超过限制，看了评论区各位大佬的提示，讲到可以利用哈希表查找以空间换取时间的做法降低时间复杂度。于是改写代码如下：

class Solution:
    def twoSum(self, nums, target):
        dict1 = {}
        if len(nums)<2:
        	return 0
        for i in range(0,len(nums)):
            num = target - nums[i]
            if num not in dict1:
                dict1[nums[i]] = i
            else:
                return[dict1[num],i]
        return 0 

在python里，字典就对应着哈希查找表，于是我们相当于多定义了一个字典，最开始字典为空，按nums数组中的顺序取数，首先计算这个数字需要与什么数字相加才能等于target，然后就去字典里查找有没有这个数字，如果没有，那就将当前读的数字添加到字典中，key为数字的值，value为标号，所以最后总会在字典中查找到答案，这样时间复杂度就降低到了$O(n)$
第一题就到这里吧，其实DS里的哈希表我也忘记了，emmmm正好趁现在去复习下吧!

---

2. 两数相加（中等）

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字0之外，这两个数都不会以0开头。

示例

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

代码

这道题明显是提醒我去复习链表操作了，而且最重要的是我好像从来没有在python中使用过链表…没办法只能硬着头皮瞎jb敲了，最开始还是失败了，原因有两个：1.因为要返回结果所以要留一个头指针 2.next指针要熟练。

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

class Solution:
    def addTwoNumbers(self, l1, l2):
        head = ListNode(0) #定义头指针用来返回结果
        l3 = head #l3用来进行链表操作
        count = 0 #判断是否有进位
        while(l1 or l2): 
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            l3.next = ListNode((x+y+count)%10) #从个位数开始计算
            l3 = l3.next #指针移动
            count = (x+y+count)//10 #注意python中的整除有两个//
            if(l1!=None):
                l1 = l1.next
            if(l2!=None):
                l2 = l2.next
        if(count == 1): #如果最后还有有进位
            l3.next = ListNode(1)
        return head.next

虽然这道题的难度标的是中等，但感觉只要链表操作熟练了，这道题还是蛮简单的。算了算了别忘了复习链表操作…一定不要忘了返回结果需要头指针哦…

---

3. 无重复字符的最长子串（中等）

题目描述

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

示例1

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

示例2

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

示例3

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

代码

刚看完题目描述的我觉得这道题目好像很简单啊，用第一题时候一样的字典查找就可以解决了，最后题目给的三个例子倒是通过了，提交检测的几百上千个测试用例却总有通不过的，为了涵盖不同的测试用例代码被我改的又臭又长，折腾了一段时间只好打开了百度放弃了挣扎…所以说到底我的代码能力是真滴弱啊…因此直接附上大佬们的代码吧…

class Solution:
    def lengthOfLongestSubstring(self, s):
        dict1 = {} #定义一个字典用来查找
        i , ans = 0, 0 #i代表重复的最后的位置，ans为结果
        for j in range(len(s)):
            if s[j] in dict1:
                i = max(dict1[s[j]],i) #取重复的最后面的字符位置
                #i = dict1[s[j]]
            ans = max(ans, j-i+1) #取最大的子序列长度
            dict1[s[j]] = j+1 #将不在字典中的也就是不重复的字母放入字典,同时保持位置更新，使用j+1是为了直接跳到重复字符的下一个位置。
        return ans

最后反思一下自己为什么想不到为什么想不到……