leetcode记录贴(go语言)

没事的时候打算开始玩一玩leetcode,不然天天写代码,却对算法没啥认识还是有点尴尬的。虽说是做题,其实大部分就是为了看看别人牛逼的思路。尽量每天一题把~

遂溪ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!

1.两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
例:
        给定 nums = [2, 7, 11, 15], target = 9

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

第一种方法就是便利数组,随着数组长度增加,执行时间指数型增加。

#时间复杂度:O(n^2)
#空间复杂度:O(1)
func twoSum(nums []int, target int) []int {
    for firstIndex,firstNum := range nums{
        for secondIndex,secondNum := range nums{
            if firstIndex != secondIndex && firstNum + secondNum == target{
                return []int{firstIndex, secondIndex}
            }
        }
    }
    return nil
}

第二种方式是以空间换时间,把数据存在哈希表里面,最多只用完全遍历一次数组,就能得到结果。

#时间复杂度:O(n)
#空间复杂度:O(n)
func twoSumHash(nums []int, target int) []int {
    m :=  make(map[int]int)
    for index,num := range nums{
        i,ok := m[target - num]
        if ok {
            return []int{i,index}
        }
        m[num] = index
    }
    return nil
}

题目链接:https://leetcode-cn.com/problems/two-sum/description/

作为脑子是条直线的小白,解题的方法是第一种,打死估计都想不到第二种把。

2.两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

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

这个题主要有两个地方卡了我一下,第一,输入的两个链表可能是不一样长的,第二,最后一位相加可能会进1,所以此时,输出比输入多一位数字,就是多一个节点。
我在思考次题目时候,想方设法的想把输出链表的第一个节点,填入数字,其实可以这样。链表第一个节点可以为空,然后从第二个节点赋值,最后return时候,返回head.Next。咳咳,早已忘记当年学数据结构的时候,就是这么干的。
我的答案:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    l := new(ListNode)
    temp := l
    lsum := 0
    for  {
        if l1 != nil{
            lsum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil{
            lsum += l2.Val
            l2 = l2.Next
        }
        temp.Val = lsum % 10
        lsum = lsum / 10
        if lsum != 0 || l1 != nil || l2 != nil{
            nextNode := new(ListNode)
            temp.Next = nextNode
            temp = temp.Next
        }else{
            break
        }

    }
    return l

}

网站给出的答案:

func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
    dummyHead := new(ListNode)
    p,q,curr := l1,l2,dummyHead
    carry := 0
    for p !=nil || q != nil{
        x,y := 0,0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        sum := x + y + carry
        carry = sum /10
        curr.Next = new(ListNode)
        curr = curr.Next
        curr.Val = sum % 10
        if p !=nil{
            p = p.Next
        }
        if q !=nil{
            q = q.Next
        }
    }
    if carry > 0{
        curr.Next = &ListNode{Val:carry}
    }
    return dummyHead.Next
}

网站的答案会把l1和l2赋值给一个临时变量,这样就不会影响函数外的l1,l2,这是我所忽略的。
网站的答案,把sum和carry分成两个变量,增强了可读性,我放在一起,基本上就看不出来为啥,除以10赋值给sum。然后我变量命名过于随意。

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

看见字符串匹配的题的就怂,所以卡了好几天不敢做。我自己的答案倒是尝试快10次了。才通过所有的测试。坑的点还是不少的。说下我的实现思路吧。

func lengthOfLongestSubstring(s string) int {
    filter := make(map[int32]int)         // 比较喜欢用哈希表统计重复
    lastKey := 0                          // 记录重复时,与本次重复的上一次重复点的下一位的index(非重复开始的位置)
                                                //比如当前字母的index为10,与之重复的字母的index为5,那么lastKey的值就赋值为5
    max := 0                              //最大连续不重复字串的长度
    for k,v := range s{                   //遍历字串
        index,ok := filter[v]            //判断是否发生重复
        if ok {                            //发生重复
            if k - lastKey  >max{         //计算重复点到上一个重复点的长度
                max = k - lastKey         
            }
            for i := lastKey;i max{            //有可能中间某个点,到最后一个字母都没有重复,所以不会触发ok里面的检测,因此判断非重复点到最后一个字母的距离。
        max = len(s) - lastKey
    }
    return max
}

网站给的答案:

1.滑动窗口,网站答案是用集合实现的,因为go本身没有集合的包,所以我还是用map
# i和j就是字串的开始坐标和结束坐标。遍历字符串s,如果当前字母,在字串i,j中没有重复,则j加1,即字串长度加一,如果当前字母在i,j中有重复的,则删除字串的第一个字母。因为有可能重复的字母在i,j中间,所以就会一直删除字串的第一个字母,直到删除至子串中没有重复的字母。就得到了,非重复字串。
#思路是真的好呀。之前我一直纠结怎么,当字串中有重复字母的时候,怎么确定,map中删除哪些key,网站的思路就很流畅呀!!!赞!

func lengthOfLongestSubstring(s string) int {
    filter := make(map[uint8]int)
    n := len(s)
    i,j,max := 0,0,0

    for i < n && j < n {
        _,ok := filter[s[j]]
        if !ok{
            filter[s[j]] = 0
            j++
            if j - i > max{
                max = j - i
            }
        }else {
            delete(filter,s[i])
            i++
        }
    }
    return max
}
2.优化的滑动窗口,原来网站也有map的思路
#其实放入map中的值并不需要删除....对比一下,我写的答案太low了。。。
func lengthOfLongestSubstring(s string) int {
    filter := make(map[uint8]int)
    n := len(s)
    max := 0

    for i,j := 0,0; j < n; j++ {
        index,ok := filter[s[j]]       #判断当前字母是否在map中已存在
        if ok{                               #如果存在,就把index赋值给i
            if index > i {                   #比如map中有一个字母a,他的index为3,如果当前字母也为a,就吧之前a的index保存到i中
                i = index                      #为什么判断大小呢?假如a的index为3,他前面有一个字母b,当前字母为a,所以i为3,如果下一个字母为b,因为上一个a之前有一个b,所以b是存在的,但是上一个b的在字母a前面,所以i不变。这就是map不用删除key的原因
            }
        }
        if j - i +1 > max{
            max = j - i + 1
        }
        filter[s[j]] = j+1
    }
    return max
}

4. 两个排序数组的中位数

题目:给两个有序的数组,取两个长度为n,m的数组的中位数,并且时间复杂度为Olog(min(n,m))
例1:

nums1 = [1, 3]
nums2 = [2]
中位数是 2.0

例2:

nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

其实这道题考的排序算法,所以哪个排序算法的时间复杂度是O(log n)呢,还给了两个有序的数组,第一想到的就是归并排序的最后一步。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    i,j := 0,0
    sorted := make([]int,0)
    for i < len(nums1) && j < len(nums2){
        if nums1[i] > nums2[j]{
            sorted = append(sorted,nums2[j])
            j++
        }else {
            sorted = append(sorted,nums1[i])
            i++
        }
    }
    sorted = append(sorted,nums1[i:]...)
    sorted = append(sorted,nums2[j:]...)
    n := len(sorted)
    if n % 2 ==0{
        return (float64(sorted[n/2-1]) + float64(sorted[n/2]))/2
    }
    return float64(sorted[(n-1)/2])
}

嘤嘤嘤,网站答案看的脑壳疼。。。。
看完网站的答案,我掐指一算,我的时间复杂度是O(min(n,m)),想要时间复杂度为O(log(mint(n,m))),就得用二分法。分析过程好复杂,脑壳疼。实现也复杂,要考虑的因素好多。。。。


当前题目:leetcode记录贴(go语言)
URL地址:http://scjbc.cn/article/jsjcdi.html

其他资讯