首页 软件代码

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





文章评论

目录