LeetCode解题思路(golang)

LeetCode解题思路及相关解法

1.两数之和

题目描述

给定一个整数数组 nums 和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

实例

给定 nums = [2, 7, 11, 15], target = 9  
​  
因为 nums[0] + nums[1] = 2 + 7 = 9  
所以返回 [0, 1]

解题思路

首先说明白,今天的我是一个小白,这个题的第一种解法,我完全没有使用任何算法,直接使用暴力破解的思路解出了第一题,后续学习到相关算法以后,会使用更加优秀的算法来解决这个题

首先今天的这个题很简单,我只是简单地将整个数组遍历,在接下来的循环中,从这个元素的下一个元素开始,将这个数组遍历,知道得到将两个数加起来等于target为止,否则就返nil

func twoSum(nums []int, target int) []int {  
     //第一个循环,从小到大遍历  
     for i := 0; i < len(nums) - 1; i++ {  
         for j := i + 1; j < len(nums); j++ {  
         //第二个循环从i+1开始,开始遍历这个数组  
             if nums[i] + nums[j]  == target {  
             //判断两数相加是否等于target  
                 return []int{ i , j }  
             }  
         return nil  
         }  
     }  
}

踩坑之路

首先,好长时间没有写Golang了,语法不怎么熟悉了,编程能力也在不断的下降了,最后写返回值的时候,写成了 return i ,return j 结果报了错,我才记起来,我函数当中返回的是一个数组而不是一个单纯的int 最后经过提醒以后,我将这个地方改过来了

算法分析

  • 时间复杂度:O(N2)

  • 空间复杂度:O(1)

贪心算法

2. Assign Cookies

题目描述

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子i,都有一个胃口值g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

题目示例

输入: g = [1,2,3], s = [1,1]  
输出: 1  
解释:   
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。  
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。  
所以你应该输出1。
输入: g = [1,2], s = [1,2,3]  
输出: 2  
解释:   
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。  
你拥有的饼干数量和尺寸都足以让所有孩子满足。  
所以你应该输出2.

解题思路

今天也是除了两数之和外写的第一个题,也是我通过算法做的第一个题,这个题使用了一个很简单的贪心算法,贪心算法是什么呢,我来先解释一下,首先,我们知道,所有资源都是有限的,我们可以将一些有限的资源,首先分配给需要这些资源比较少的人来使用,来满足他们的具体要求,而占用资源更大的成员也只能比较靠后的满足,因为,他们如果使用了这些资源,可能就会导致,满足了他一个人,结果牺牲了其他人的使用。当然作为一个网络工程专业的学生,我突然想起了IP地址的划分,我们在划分一些有限子网的时候,总是先满足要求最大的用户,然后其他用户逐步细分下去,我觉得这也算是一种变相的贪心算法。所以我们就来做这个题吧:我的理解是这样的,我先要满足胃口最小的孩子,所以我就需要对所有的孩子的胃口和小饼干的尺寸做一个排序 然后通过这个排序,我们先满足最小孩子的吃饼干需求。同时因为,每个孩子只能得到一块饼干,所以不能存在数字,我们都会使用int类型的变量,不允许分割。接下来通过循环遍历,得到能够满足条件的孩子,然后返回出孩子的数量就可以了。代码如下:

func findContentChildren(g []int, s []int) int {  
    sort.Ints(g)          //对两个数组进行排序  
    sort.Ints(s)  
    child := 0  
    for  cookie := 0 ;child < len(g) && cookie < len(s); cookie++ {  
        if g[child] <= s[cookie]{  //判断饼干是否大于或者等于孩子的胃口  
            child++                //如果相等,则满足的孩子加一  
        }  
    }  
    return child  
}

特别提醒

首先,我们要搞清楚弹性算法的实质是什么:贪心算法或贪心思想采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到的结果是全局最优的。

算法分析

  • 时间复杂度:O(N)

  • 空间复杂度:O(1)

3.分发糖果(LeetCode 135)

题目描述

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。

  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

    那么这样下来,老师至少需要准备多少颗糖果呢?

输入输出样例

输入:[1,0,2]  
输出:5  
解释:你可以分别给这三个孩子分发 2、1、2 颗糖果。
输入:[1,2,2]  
输出:4  
解释:你可以分别给这三个孩子分发 1、2、1 颗糖果。  
第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

解题思路

这些题都是我通过一本书来给我推荐的做题顺序,这个题LeetCode显示的是难题,也许可能是一个Hard 就把我吓坏了,我看了半天不知道哦怎么办,后来我才意识到,这些题放在一起都是同类的题,都是贪心算法的题,所以我使用贪心的思路来考虑这个题是如何去刷。首先,我们看到题目当中的两个条件,我发现,其实第一个条件是可以比较简单的满足的,就是首先每个人都可以满足一颗糖果的条件,我可以先给每一个人一个糖果,然后再通过和右边人的分数比较,如果我的分数比左边人的分数高,我给我的糖果为右边的人的糖果数加一,然后遍历完成这个数组以后,我在从右边开始,遍历数组,来判断我的分数是否比我左边的人的分数高,如果高了,就对我的糖果加上右边的人的糖果数的加一,最后把所有人的糖果相加,得到就是最少的糖果数量。

代码

func candy(ratings []int) int {  
    lenRa := len(ratings)  
    l := make([]int, lenRa)   //l mean left   
    r := make([]int, lenRa)   //r mean right  
    for i := 0; i < lenRa; i++ {  
        l[i] = 1  
        r[i] = 1  
    }                         //将数组默认值设置为1  
 //left  
    for i := 1; i < lenRa; i++ {  
        if ratings[i] > ratings[i-1] { // 判断我的分数和我左边的人的分数  
            l[i] = l[i-1] + 1          // 如果我的分数大于我左边的人的分数,则我的糖果数就是左边人的糖果数加一  
            }  
    }  
 //right  
    for i := lenRa - 1; i > 0; i-- {  
        if ratings[i-1] > ratings[i] {  
            r[i-1] = r[i] + 1  
        }  
    }  
    sum := 0  
 //compare left and right   
    for i := 0; i < lenRa; i++ {  
        if l[i] > r[i] {  
            sum += l[i]                // 左边和右边作比较,哪边大加哪个  
        } else {  
            sum += r[i]  
            }  
        }  
    return sum  
}

算法分析

  • 时间复杂度:O(N)

  • 空间复杂度:O(1)

赞赏

微信赞赏支付宝赞赏

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇