代码随想录：贪心算法
贪心算法的本质是选择每一阶段的局部最优从而实现全局最优
贪心算法的难点在于如何通过局部最优推出全局最优，验证可不可以使用贪心算法可以举反例，如果举不出反例就可以尝试贪心算法
贪心算法解题一般分四部：
1.将问题分解成子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优堆叠成全局最优
力扣455：分发饼干
public class Solution {
int Cookies(int[] g, int[] s)
{
int result = 0;
int j = g.Length-1;
for (int i = s.Length-1; i >=0 ; i--)
{
while (i>=0&&j>=0&& s[i]<g[j])
{
j--;
//当前最大的饼干不能满足胃口最大的孩子就看下一个孩子
}
if (j>=0)
{
result++;
j--;
//满足了就计数并接着指定下一个孩子
}
if (j<0)
{
break;
//没有下一个孩子就结束
}
}
return result;
}
public int FindContentChildren(int[] g, int[] s) {
Array.Sort(g);
Array.Sort(s);
return Cookies(g, s);
}
}
力扣376：摆动序列
public class Solution {
//局部最优就是要删除出现的每个单调坡度上面除两端以外的节点，最后剩下的就是摆动序列
int Wiggle(int[] nums, bool[] relation)
{
int count = 1;
int i = 1;
while (i<nums.Length&&nums[i]-nums[i-1]==0)
{
i++;
//找到开头第一次出现差值不为0的位置，第二次提交因为这里条件中忘写i<nums.Length导致数据异常，在使用下标指定数字时要先判断下标的范围
}
if (i!=nums.Length)
{
count++;
relation[i - 1] = nums[i] - nums[i - 1] > 0;
i++;
//第一次遇到差值计数加一
}
for (; i < nums.Length; i++)
{
if (nums[i]-nums[i-1]!=0)
{
relation[i-1] = nums[i] - nums[i - 1] > 0;
if (relation[i-1]!=relation[i-2])
{
count++;
//差值不等于0就看跟前一次差值正负是否相同，不同计数就+1
}
}
else if (nums[i]-nums[i-1]==0)
{
relation[i-1] =relation[i-2];
//差值等于0就继承前一次的正负属性
}
}
return count;
}
public int WiggleMaxLength(int[] nums)
{
if (nums.Length<2)
{
return nums.Length;
}
bool[] relation = new bool[nums.Length];
return Wiggle(nums, relation);
}
}
//第一次写这个的时候为了应对前几个数全都相同的情况，将开头差值为0的情况判断写到了for循环中间，因此导致中间出现差值为0的情况也被这样处理，导致结果错误，开头的情况就要在循环前处理完成，循环内再处理循环内出现的特殊情况
力扣53：最大子数组和
public class Solution {
//遇到子数组和为负数时就放弃，从下一个元素继续寻找新的子数组，最后统计和最大的子数组就行
int sub(int[] nums)
{
int result = nums[0],temp=0;
for (int i = 0; i < nums.Length; i++)
{
temp += nums[i];
result = Math.Max(result, temp);
//先更新result再判断是否重置temp，否则数组只有一个负数时结果会变成0
if (temp<0)
{
temp = 0;
}
}
return result;
}
public int MaxSubArray(int[] nums)
{
return sub(nums);
}
}
力扣155：买卖股票的最佳时机II
public class Solution {
//假设股票在第一天买进第三天卖出，利润i=i[3]-i[1]，可以拆解为i=(i[3]-i[2])+(i[2]-i[1])，因此在哪天买进卖出最终受益都是这几天每两天的利润和，分别计算每两天的利润并相加求出利润为正的区间，并将全部正利润结果加入到结果中即可得到最终利润
int Profit(int[] prices)
{
int[] profit = new int[prices.Length - 1];
int count = 0;
for (int i = 1; i < prices.Length; i++)
{
profit[i - 1] = prices[i] - prices[i - 1];
if (profit[i-1]>0)
{
count += profit[i - 1];
}
}
return count;
}
public int MaxProfit(int[] prices)
{
return Profit(prices);
}
}
力扣55：跳跃游戏
public class Solution {
//每一个数字都指定了跳跃范围，只要在范围内的数字都可以跳到，对于在范围内的数字又指定了下一个跳跃范围，因此只要不停更新跳跃范围最后范围包括最后一位数就一定能跳跃到
public bool CanJump(int[] nums)
{
int cover = 0;
if (nums.Length==1)
{
return true;
//只有一个元素一定能到最后
}
for (int i = 0; i <= cover; i++)
{
//这里将循环终止条件设置为i<=cover，会随着循环一起更新cover的值
cover=Math.Max(i+nums[i],cover);
//如果写cover+=nums[i]则会出现范围不正确，会一直增加cover范围，正确的范围是当前坐标加当前数字
if (cover>=nums.Length-1)
{
return true;
}
}
return false;
}
}
力扣45：跳跃游戏II
public class Solution {
//与上题不同，因为要找最小步数所以不能随便跳跃，需要在当前覆盖范围中寻找下次覆盖范围最大的位置进行跳跃，因此需要额外记录下次跳跃范围
public int Jump(int[] nums)
{
int curCover = 0,count=0,nextCover=0;
if (nums.Length==1)
{
return 0;
}
for (int i = 0; i <nums.Length-1; i++)
{
//遍历整个数组，终止条件设定为i<nums.Length-1，这样在遍历的时候会停在倒数第二位，如果这时当前覆盖范围不是下标说明最后一个数被覆盖到，是下标说则根据判断还要多走一步，这样做就不需要考虑当移动下标到达当前覆盖距离最远下标时当前下标是不是集合终点。
nextCover = Math.Max(i + nums[i], nextCover);
//寻找当前覆盖范围内的最大下次覆盖范围
if (i==curCover)
{
//当前覆盖范围到头了，需要多走一步才能到下次覆盖范围
count++;
curCover = nextCover;
//更新当前覆盖范围为最大的下次覆盖范围
}
}
return count;
}
}
力扣134：加油站
public class Solution {
public int CanCompleteCircuit(int[] gas, int[] cost)
{
int[] rest = new int[gas.Length];
int sum = 0,start=0;
for (int i = 0; i < gas.Length; i++)
{
rest[i] = gas[i] - cost[i];
sum += rest[i];
}
if (sum<0)
{
return -1;
//先判断如果总耗油高于总油量说明走不完一圈
}
//油量-油耗大于等于0一定有走完一圈的解
int curSum = 0;
for (int i = 0; i < rest.Length; i++)
{
curSum += rest[i];
//能走完一圈的话就找起点，如果当前油耗大于油量说明不能从这里出发，重置油耗差总和从下一个起点继续开始找，循环结束时显示的起点的位置就是要找的起点
if (curSum<0)
{
start = i + 1;
curSum = 0;
}
}
return start;
}
}
力扣135：分发糖果
public class Solution {
public int Candy(int[] ratings) {
int[] candy=new int[ratings.Length];
int count = 0;
candy[0]=1;
//循环中不会给首位赋值，因此在这里提前赋值为1
for (int i = 1; i < ratings.Length; i++)
{
candy[i] = 1;
if (ratings[i]>ratings[i-1])
{
candy[i] = candy[i - 1] + 1;
//从左向右遍历，当前比左边评分高就糖果数量+1
}
}
count += candy[candy.Length - 1];
//循环中不会统计最后一个人得到的糖所以在这提前加上
for (int i = candy.Length-2; i >=0 ; i--)
{
if (ratings[i]>ratings[i+1])
{
candy[i] = Math.Max(candy[i], candy[i + 1] + 1);
//从右往左遍历，当前比右边评分高就将当前和右边糖果数量+1取最大值作为当前糖果数量，这样就能保证当前糖果数量比左右都多而且是最少所需要的
}
count += candy[i];
//每次循环中将总糖果数量加到结果
}
return count;
}
}
力扣860：柠檬水找零
public class Solution {
//从头开始分别处理收到三种面值的情况即可
public bool LemonadeChange(int[] bills)
{
int five = 0, ten = 0;
for (int i = 0; i < bills.Length; i++)
{
if (bills[i]==5)
{
five++;
//收到5就直接收下
}
else if (bills[i]==10)
{
five--;
ten++;
if (five<0)
{
return false;
//收到10就用5找零，找不了就return false
}
}
else if (bills[i]==20)
{
if (ten!=0)
{
ten--;
five--;
if (five<0)
{
return false;
}
}
else
{
five -= 3;
if (five<0)
{
return false;
}
//收到20就先尝试用一张10和一张5找零，没有10就用三张5找零，找不了就return false
}
}
}
return true;
}
}
力扣452：用最少数量的箭引爆气球
public class Solution {
public int FindMinArrowShots(int[][] points) {
Array.Sort(points,new CompareMethod());
//使用接口实现对数组内元素按下标为0的元素排序
if (points.Length==0)
{
return 0;
}
int count = 1;
//数组长度不为零，至少需要一支箭
for (int i = 1; i < points.Length; i++)
{
if (points[i][0]>points[i-1][1])
{
count++;
//如果新气球在老气球外面就需要多用一支箭
}
else
{
points[i][1] = Math.Min(points[i][1], points[i - 1][1]);
//跟老气球有重叠就更新下标
}
}
return count;
}
}
public class CompareMethod : IComparer<int[]>
{
public int Compare(int[] x, int[] y)
{
if (x[0]>y[0])
{
return 1;
}
else if (x[0] == y[0])
{
return 0;
}
else return -1;
//实现接口，最开始的时候接口内的实现为returnx[0]-y[0]，但是这样会造成数据溢出，在x[0]和y[0]相减的结果会超出数据定义范围的时候得到的结果就是不正确的，因此改为比较x[0]与y[0]的大小，按比较结果返回-1，0或1最终实现排序
}
}
力扣56：合并区间
public class Solution {
public int[][] Merge(int[][] intervals) {
Array.Sort(intervals,new CompareMethod());
if (intervals.Length==0)
{
return null;
}
IList<int[]> list = new List<int[]>();
int[] temp = new []{intervals[0][0],intervals[0][1]};
if (intervals.Length==1)
{
list.Add(new []{intervals[0][0],intervals[0][1]});
//特殊情况，只有一组数就直接输出
}
for (int i = 1; i < intervals.Length; i++)
{
if (intervals[i][0]<=intervals[i-1][1])
{
intervals[i][0] = intervals[i - 1][0];
intervals[i][1] = Math.Max(intervals[i - 1][1], intervals[i][1]);
temp[0] = intervals[i][0];
temp[1] = intervals[i][1];
//能合并就先更新当前下标的数再将合并后的区间写进temp里
if (i==intervals.Length-1)
{
list.Add(new []{temp[0],temp[1]});
//特殊情况只有两组数需要额外加一次统计结果
}
}
else
{
list.Add(new int[] {temp[0],temp[1]});
//发现不能合并了就将上一组的区间加入结果，注意加入结果时需要得到这个temp数组的引用而不能直接将temp加入结果
if (i==intervals.Length-1)
{
temp[0] = intervals[i][0];
temp[1] = intervals[i][1];
list.Add(new []{temp[0],temp[1]});
//如果是不能合并的新区间还是最后一组数就将这组也加入结果
}
temp[0] = intervals[i][0];
temp[1] = intervals[i][1];
//更新temp内的数据
}
}
int[][] result = new int[list.Count][];
for (int i = 0; i < list.Count; i++)
{
result[i] = list[i];
//将IList<int[]>转换成int[][]数组形式作为结果
}
return result;
}
}
public class CompareMethod : IComparer<int[]>
{
public int Compare(int[] x, int[] y)
{
if (x[0]>y[0])
{
return 1;
}
else if (x[0] == y[0])
{
return 0;
}
else return -1;
}
}
力扣738：单调递增的数字
using System.Text;
public class Solution {
public int MonotoneIncreasingDigits(int n)
{
if (n<10)
{
return n;
}
StringBuilder str = new StringBuilder();
str.Append(System.Convert.ToString(n));
//将给的int类型转换成为StringBuilder类型方便操作
for (int i = str.Length-2; i >= 0; i--)
{
//当遇到非首位的高一位比低一位大时高一位数字减一，后面所有数字变成9
if (str[i]>str[i+1])
{
str[i]--;
if (i!=0 ||(i==0&& str[i]!=0))
{
for (int j=i+1; j < str.Length; j++)
{
str[j] = '9';
}
}
else
{
str.Remove(0, 1);
for (int j = 0; j < str.Length; j++)
{
str[j] = '9';
//首位特殊处理，这时候就要删掉首位了
}
}
}
}
return System.Convert.ToInt32(str.ToString());
//使用Convert只能将string类型转换为int类型，不能直接转换StringBuilder
}
}
