决定整理一下算法相关的东西，简单的就不弄了，先从贪心算法开始吧，会结合例子，希望最起码自己能够讲明白这些东西。（概念源自百度百科，主要是结合例子，解释概念，提前坦白，以及所有代码都是 go 语言书写，自己实现的）
概念
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是某种意义上的局部最优解。
算法思路
1.建立数学模型描述问题
2.把求解的问题分成若干个子问题。
3.对每个子问题求解，得最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
算法例子
例子一：分发饼干问题
https://leetcode-cn.com/problems/assign-cookies/description/
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
解题思路如下：
1.要尽可能多的让孩子得到满足，就是要用最小代价满足孩子的胃口值
2.若是每个饼干都用于满足恰好胃口值的孩子，就能得到最大值
3.每个孩子从小到大的胃口值，被从小到大的饼干满足，这样用的结果就是我们能得到的最大满足孩子个数
func findContentChildren(g []int, s []int) int { sort.Ints(g) sort.Ints(s) var number int //能满足学生总数 var sindex int //已被满足学生坐标 for i := 0; i < len(s); i++ { if sindex < len(g) && s[i] >= g[sindex] { number++ sindex++ } } return number}
复制代码
例子二：无重叠区间
https://leetcode-cn.com/problems/non-overlapping-intervals/description/?utmsource=LCUS&utmmedium=ipredirect&utmcampaign=transfer2china
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
解题思路如下：
1.要无重叠区间，若右闭合一致，区间间隔更长的比区间间隔更短的更容易有重叠，本着贪心思想遇到这种情况直接选择左闭合更大的保留(重复的直接剔除)
2.按照 1 情况处理一遍以后，从小到大的筛选重叠区间就是最优解
func eraseOverlapIntervals(intervals [][]int) int { if len(intervals)==0{ return 0 } var number int //需要剔除的区间数目 qmap := make(map[int][]int)//key为区间结尾 rightv:=make([]int,0) //记录右闭合值 for i:=0;i<len(intervals);i++{ if qmap[intervals[i][1]] == nil{ //这个结尾还没有存在 qmap[intervals[i][1]] = intervals[i] rightv = append(rightv,intervals[i][1]) }else{ //结尾已经存在，如果左闭合更大，说明要替换 if qmap[intervals[i][1]][0] < intervals[i][0]{ qmap[intervals[i][1]] = intervals[i] } number++ } } if len(rightv)==1{ return number } sort.Ints(rightv) last:=rightv[0] for i:=1;i<len(rightv);i++{ if qmap[rightv[i]][0] < last{ number++ }else{ last = rightv[i] } } return number}
复制代码
例子三：投飞镖刺破气球
https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/description/
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
解题思路如下：
同款题目
上一题找无重叠区间，重点是上一个区间的结尾与下一个的开始，这一题，思考的是每一箭要引爆尽可能多的气球，只要每一箭引爆的气球数目最多，那么就可以用最少的弓箭数目解决。
1.去除所有同开头，但是右闭合更大的气球，因为他们一定会跟另一个一起爆炸
2.按照开头从小打大，注意每一箭能覆盖的长度范围，左闭合一定小于第一个要射爆气球的右闭合，右闭合取一起射爆气球的最小右闭合。
3.最终结果就是最少可用弓箭数目
func findMinArrowShots(points [][]int) int { if len(points) == 0 { return 0 } qmap := make(map[int][]int) //key为区间结尾 leftv := make([]int, 0) //记录左闭合值 for i := 0; i < len(points); i++ { if qmap[points[i][0]] == nil { //这个开头还没有存在 qmap[points[i][0]] = points[i] leftv = append(leftv, points[i][0]) } else { //开头已经存在，如果右闭合更大，说明一定会一起爆， if qmap[points[i][0]][1] > points[i][1] { qmap[points[i][0]] = points[i] } } } if len(leftv) == 1 { return 1 } sort.Ints(leftv) last := qmap[leftv[0]][1] var number int //弓箭数目 number = 1 for i := 1; i < len(leftv); i++ { if qmap[leftv[i]][0] <= last { //可以一起爆，但是要注意边界 if qmap[leftv[i]][1] < last { last = qmap[leftv[i]][1] } continue } else { //上一轮的结束了 number++ last = qmap[leftv[i]][1] } } return number}
复制代码
例子四：根据身高重建队列
https://leetcode-cn.com/problems/queue-reconstruction-by-height/description/
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
解题思路如下：
1.无论怎么解，只要能把单个人放到正确的位置，最后综合的结果就是正确的结论
2.我们按照身高顺序，从高往后排序，先确定高的，将低的按照顺序插入，由于 ki 是身高比他高的人的计数，所以用这个方法可以保证每次都是局部最优，整合是整体最优
func reconstructQueue(people [][]int) [][]int { if len(people) <= 1 { return people } //0 是身高 //1 是前面比他高的人数 length := len(people) res := make([][]int, length) high := make([]int, 0) pmap := make(map[int][][]int) for i := 0; i < len(people); i++ { pmap[people[i][0]] = append(pmap[people[i][0]], people[i]) if len(pmap[people[i][0]]) == 1 { high = append(high, people[i][0]) }
} sort.Ints(high) for i := len(high) - 1; i >= 0; i-- { //排序，同高度的要保证k小的优先排序，不然顺序就乱掉了 sort.Slice(pmap[high[i]], func(k, z int) bool { if pmap[high[i]][k][1] < pmap[high[i]][z][1] { return true } return false }) arrs := pmap[high[i]]
for j := 0; j < len(arrs); j++ { index := arrs[j][1] if res[index] == nil { res[index] = arrs[j] } else { //全部向后一位，没集齐的时候最后一位一定是空 for k := length - 1; k > index; k-- { res[k] = res[k-1] } res[index] = arrs[j] } } } return res}
复制代码
例子五：经典股票问题
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解题思路如下：
1.从第一天，第二天开始找最优，目标是找到前面最小的股票价钱，再从后面找到与最小股票价钱相差最大的值
2.假设有 7 天，前 3 天股票获取的最大收益如果整个流程没有能超过的，那么前 3 天获得的最优解就是整个流程的最优解
func maxProfit(prices []int) int { if len(prices) <= 1 { return 0 } var max int //前几日最小的值 min := prices[0] for i := 1; i < len(prices); i++ { if prices[i]-min < 0 { min = prices[i] } else { if prices[i]-min > max { max = prices[i] - min } } } return max}
复制代码
例子六：非递减数列
https://leetcode-cn.com/problems/non-decreasing-array/
给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
解题思路如下：
最多改变一个元素，就说明非递减的情况只能出现一次
我们可以从这个判断条件入手，分析具体情况
1.若是在边界，开头出现 0>1，我们为了递减必然删除 0，计数加 1，结尾出现，处理掉，计数加 1，计数超过 1 则无法达成条件
2.在数组中间，有以下处理方式
1 2 3 5 4 6 7 ==》删除
3 4 2 3 ==》 由于 3>2 所以失败，3 要小于 2，也就是 i-1<i+1，若是 i-1 不小于 i+1，那么可以直接删除 i
2 3 1 5 ==》处理的不再是逆序开始的 i，而是要处理 i+1，不同原因是 i<i+2
所以可以得出结论
计数大于 1，false
在数组中间 i-1>i+1，且 i<i+2 才能造成无法处理的情况，也就是 3 4 2 3，虽然走下去只有一个 count 但是也无法处理
func checkPossibility(nums []int) bool { length := len(nums) counter := 0 for i := 0; i < length-1; i++ { if nums[i] > nums[i+1] { counter++ isOutOfBounds := i != 0 && i+2 < length if counter > 1 || (isOutOfBounds && nums[i] > nums[i+2] && nums[i-1] > nums[i+1]) { return false } } } return true}
复制代码
例子六：最大子序和
https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路如下：
1.求最大子序和，那么任何一段的和取最大就是
2.tmp 为中转值，若是 tmp+nums[i]<0 再往下加必然不会是最大，就从 0 开始，又考虑到数组可能为全负数，此种情况就变成了 max 取数组中最大的负数，所以也要考虑
3.若是 tmp+nums[i]>0 就说明加下去还是有可能得出更大的值，拿结果与之前的 max 判断，进行替换。
func maxSubArray(nums []int) int { max := nums[0] var tmp int for i:=0;i<len(nums);i++{ if tmp + nums[i] < 0{ tmp = 0 if nums[i]>max{ max = nums[i] } }else{ tmp = tmp + nums[i] if tmp>max{ max = tmp } } } return max}
复制代码
例子七：分隔字符串使同种字符出现在一起
https://leetcode-cn.com/problems/partition-labels/
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
解题思路如下：
1.要尽可能多的分段，那么以最小的字母数为一段，每段区分，所有的集合就是最优解
func partitionLabels(S string) []int { smap:=make(map[uint8]int) send:=make(map[uint8]int) for i:=0;i<len(S);i++{ smap[S[i]]++ send[S[i]] = i } var arrs []int star:=0 for star<len(S){ number:=smap[S[star]] end:=send[S[star]] if number+star==end+1{ //数目和字母number一样 arrs = append(arrs,number) star = end+1 }else{ str:=make(map[uint8]bool) str[S[star]] = true for i:=star;i<=end;i++{ if S[star]!=S[i]&&str[S[i]]==false{ //有新字母 str[S[i]] = true number = number + smap[S[i]] if send[S[i]] > end{ end = send[S[i]] } if end+1==number+star{ arrs = append(arrs,number) star = end+1 break } } } } } return arrs}
复制代码
参考：
https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md
评论