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)