LeetCode-题库-刷题(1-3)

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
具体题目链接

Python（参考leetcode答案）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {}
        for i, num in enumerate(nums):
            if target - num in hashtable.keys():
                return [hashtable[target - num], i]
            hashtable[num] = i
        return []

思路；通过一次循环建立字典，并在循环中不断判断target - num是否在字典中，不在则以num为key，i为value生成键值对储存在字典中。

GO（参考leetcode答案）

func twoSum(nums []int, target int) []int {
    for i,j:=range nums{
        for t:=i+1;t<len(nums);t++{
            if target-j==nums[t]{
                return []int{i,t}
            }
        }
    }
    return nil
}

思路：通过双循环来不断尝试。

func twoSum(nums []int, target int) []int {
    nummap:=make(map[int]int)
    for i,j:=range nums{
        if t,ok:=nummap[target-j];ok{
            return []int{t,i}
        }
        nummap[j]=i
    }
    return nil
}

思路：同python思路。

2.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
具体题目链接

Python（参考leetcode答案）

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        value=carry=0
        l3=l=ListNode()
        while l1 or l2 or carry:
            value=carry
            if l1:
                value+=l1.val
                l1=l1.next
            if l2:
                value+=l2.val
                l2=l2.next
            carry,value=divmod(value,10)
            l3.next=ListNode(value)
            l3=l3.next
        return l.next

思路：
1.保证l1和l2链表要循环完，并需要保证carry（进位）为0。因此设置while循环的条件
2.对应位链表相加后注意是否进位，因此用divmod函数求商和余数，商为carry，余数为value
3.定义l3和l时为空节点，l的意义是记录首节点的位置（相当于哨兵），l3则一直指向下一个节点进行更新。
4.最后返回的时候要返回l.next，原因就是第一个节点为空，下一个节点才是正确的。

GO（参考leetcode答案）

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry,value:=0,0
    head:=new(ListNode)//创建新节点
    tail:=head//让tail指向head
    for l1!=nil || l2!=nil || carry>0 {
        value=carry
        if l1!=nil{
            value+=l1.Val
            l1=l1.Next
        }
        if l2!=nil{
            value+=l2.Val
            l2=l2.Next
        }
        carry,value=value/10,value%10
        tail.Next =  new(ListNode)//创建出新的空节点
        tail = tail.Next//指向下一个节点
        tail.Val=value//下个节点val=value
    }
    return head.Next//返回head的下一个节点
}

思路：
总体思路和python思路相同，但需要注意的是go判断空节点需要用nil

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
具体题目链接

Python（参考leetcode答案）

class Solution:
    def lengthOfLongestSubstring(self, s):
        st = {}
        i, ans = -1, 0
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i)
            ans = max(ans, j - i)
            st[s[j]] = j
        return ans;

思路：
1.st字典记录每个字母为key,出现的最后位置为value。
2.i代表不重复字符串的起始位置，j-1代表不重复字符串的结束位置，j代表要推进一位的位置,及字符s[j]。每次循环判断字符是否出现过(s[j] in st)，出现过则代表出现重复字符，因此要更新当前不重复字符串，及变更起点，i需要在st字典中查找s[j]上次出现的位置和字符串的起始位置，并选取最大的作为新起始位置，而j作为结束位置。
ans是保留最大的字符长度，st[s[j]] = j显而易见，新增字符索引或更新字符索引。

这里我将代码原作者的解释也写下，留作记录：

i是截至j，以j为最后一个元素的最长不重复子串的起始位置，即索引范围是[i,j]的子串是以索引j为最后一个元素的最长子串。当索引从j-1增加到j时，原来的子串[i,j-1]新增了一个元素变为[i,j]，需要判断j是否与[i,j-1]中元素有重复。所以if s[j] in st:是判断s[j]相同元素上次出现的位置，和i孰大孰小。如果i大，说明[i,j-1]中没有与s[j]相同的元素，起始位置仍取i；如果i小，则在[i,j-1]中有了与s[j]相同的元素，所以起始位置变为st[s[j]]+1，即[st[sj]+1,j]。而省略掉的else部分，由于s[j]是第一次出现所以前面必然没有重复的，仍然用i作为起始位置即可。后面的ans=max(ans,j-i+1)中，括号中前者ans是前j-1个元素最长子串长度，j-i+1是以s[j]结尾的最长子串长度，两者（最长子串要么不包括j，要么包括j）取最大即可更新ans，遍历所有i后得到整个输入的最长子串长度。

GO（参考leetcode答案）

func lengthOfLongestSubstring(s string) int {
    i, ans := -1, 0
    st := make(map[uint8]int)
    for j := 0; j < len(s); j++ {
        if _, ok := st[s[j]]; ok {
            if st[s[j]] > i {
                i = st[s[j]]
            }
        }
        if ans < j-i {
            ans = j - i
        }
        st[s[j]] = j
    }
    return ans
}

思路:参考python，虽然达不到GO语言的一般水平，但代码构思巧妙。
此外GO语言字符串保存是字节形式，因此在对字符串进行切片时返回的uint8数值，所以采用uint8类型作为map的key