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)

