1、分发饼干（455、Easy）

1）题目要求

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:

输入: [1,2], [1,2,3]

输出: 2

解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

2）我的解法

c++

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());//参数为起始迭代器（地址）和终止（迭代器）地址sort(s.begin(),s.end());int i=0,j=0,result=0;while(i<g.size()&&j<s.size()){if(s[j]>=g[i]){result++;i++;}j++;}return result;}
};

3）其他解法

int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;int result = 0;while (i != g.size() && j != s.size()){if (g[i] <= s[j]){result++;i++;j++;}elsej++;}return result;
}

作者：Smart_Shelly
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());//参数为起始迭代器（地址）和终止（迭代器）地址sort(s.begin(),s.end());int i=0,j=0,result=0;while(i<g.size()&&j<s.size()){if(s[j]>=g[i]){result++;i++;}j++;}return result;}
};

5）学到的东西

贪心算法：贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：

1.整体的最优解可以通过局部的最优解来求出；

2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。

（参考了博客：link）

c++中sort函数用法：link

2、无重叠区间（435、Medium）

1）题目要求

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

2）我的解法

c++

class Solution {
public:static bool mycompare(vector<int>&a,vector<int>&b)//必须静态{return (a[1]<b[1]);}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),mycompare);int i=0,j=1,result=0;while(i<intervals.size()&&j<intervals.size()){if(intervals[i][1]<=intervals[j][0])i=j;else result++;j++;}return result;}
};

3）其他解法

public class Solution {class myComparator implements Comparator<Interval> {public int compare(Interval a, Interval b) {return a.start - b.start;}}public int eraseOverlapIntervals(Interval[] intervals) {if (intervals.length == 0) {return 0;}Arrays.sort(intervals, new myComparator());int end = intervals[0].end, prev = 0, count = 0;for (int i = 1; i < intervals.length; i++) {if (intervals[prev].end > intervals[i].start) {if (intervals[prev].end > intervals[i].end) {prev = i;}count++;} else {prev = i;}}return count;}
}

public class Solution {class myComparator implements Comparator<Interval> {public int compare(Interval a, Interval b) {return a.end - b.end;}}public int eraseOverlapIntervals(Interval[] intervals) {if (intervals.length == 0) {return 0;}Arrays.sort(intervals, new myComparator());int end = intervals[0].end;int count = 1;for (int i = 1; i < intervals.length; i++) {if (intervals[i].start >= end) {end = intervals[i].end;count++;}}return intervals.length - count;}
}

作者：LeetCode
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

c++
按起点比较

class Solution {
public:static bool mycompare(vector<int>&a,vector<int>&b)//必须静态{return (a[0]<b[0]);}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),mycompare);int i=0,j=1,result=0;while(i<intervals.size()&&j<intervals.size()){if(intervals[i][1]<=intervals[j][0])i=j;else if(intervals[i][1]<intervals[j][1])result++;//删去后面那个else {result++;i=j;}//删去前面那个j++;}return result;}
};

按终点比较

class Solution {
public:static bool mycompare(vector<int>&a,vector<int>&b)//必须静态{return (a[1]<b[1]);}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),mycompare);int i=0,j=1,result=0;while(i<intervals.size()&&j<intervals.size()){if(intervals[i][1]<=intervals[j][0])i=j;else result++;//删去后面那个j++;}return result;}
};

5）学到的东西

贪心算法：按照什么排序不是很重要，重要的是排序后对各种可能情况的分析

一定一定要分析各种可能的情况

C++sort函数的使用：比较函数需要为静态，原因参考博客：link

3、用最少数量的箭引爆气球（452、Medium）

1）题目要求

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

Example:

输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

2）我的解法

c++
和上面那题很像

class Solution {
public:bool static mycompare(vector<int>&a,vector<int>&b){return a[1]<b[1];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),mycompare);int i=0,j=1,result=1;if(points.size()==0)result=0;while(i<points.size()&&j<points.size()){if(points[i][1]<points[j][0]){result++;i=j;}j++;}return result;}
};

3）其他解法

class Solution {public int findMinArrowShots(int[][] points) {if (points.length == 0) return 0;// sort by x_endArrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});int arrows = 1;int xStart, xEnd, firstEnd = points[0][1];for (int[] p : points) {xStart = p[0];xEnd = p[1];// if the current balloon starts after the end of another one,// one needs one more arrowif (firstEnd < xStart) {arrows++;firstEnd = xEnd;}}return arrows;}
}

作者：LeetCode
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:bool static mycompare(vector<int>&a,vector<int>&b){return a[1]<b[1];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),mycompare);int i=0,j=1,result=1;if(points.size()==0)result=0;while(i<points.size()&&j<points.size()){if(points[i][1]<points[j][0]){result++;i=j;}j++;}return result;}
};

5）学到的东西

转换问题，比如该问题可转换为求有多少个不重叠区间

贪心算法

4、根据身高重建队列（406、Medium）

1）题目要求

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

2）我的解法

c++

class Solution {
public:static bool mycompare(vector<int>&a,vector<int>&b){if(a[0]!=b[0])return a[0]>b[0];else return a[1]<b[1];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),mycompare);for(int i=0;i<people.size();i++){if(people[i][1]!=i){//和插入排序类似，每次前i-1的个数的顺序已经排好//把people[i]放到people[i][1]对应的下标位置上int j=i;int target=people[i][1];//要先把这个存起来，people[i][1]的值会变的vector<int> temp=people[i];while(j>target){people[j]=people[j-1];j--;}people[target]=temp;}}return people;}
};

3）其他解法

我的思路居然和官方思路一模一样，开心
1、

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {// if the heights are equal, compare k-valuesreturn o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];}});List<int[]> output = new LinkedList<>();for(int[] p : people){output.add(p[1], p);}int n = people.length;return output.toArray(new int[n][2]);}
}

作者：LeetCode
链接：link
来源：力扣（LeetCode）

2、
c++
（1）

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {// 先排序// [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]// 再一个一个插入。// [7,0]// [7,0], [7,1]// [7,0], [6,1], [7,1]// [5,0], [7,0], [6,1], [7,1]// [5,0], [7,0], [5,2], [6,1], [7,1]// [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {if (a[0] > b[0]) return true;if (a[0] == b[0] && a[1] < b[1]) return true;return false;});vector<vector<int>> res;for (auto& e : people) {res.insert(res.begin() + e[1], e);}return res;}
};

（2）用 list 会有提速：

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {std::sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b){return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);});list<vector<int>> r;for (auto& e : people) {auto pos = r.begin();advance(pos, e[1]);//将迭代器前进或后退几个位置r.insert(pos, e);}return std::vector<vector<int>>(r.begin(), r.end());}
};

作者：ivan_allen
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:static bool mycompare(vector<int>&a,vector<int>&b){if(a[0]!=b[0])return a[0]>b[0];else return a[1]<b[1];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),mycompare);for(int i=0;i<people.size();i++){if(people[i][1]!=i){//和插入排序类似，每次前i-1的个数的顺序已经排好//把people[i]放到people[i][1]对应的下标位置上int j=i;int target=people[i][1];//要先把这个存起来，people[i][1]的值会变的vector<int> temp=people[i];while(j>target){people[j]=people[j-1];j--;}people[target]=temp;}}return people;}
};

5）学到的东西

利用链表、利用API

贪心思想，去试各种排序方法，并对各种情况进行分析

进行插入排序时，一定要用临时变量把需要保存的值保存下来，因为排序过程中很多值会变

5、买卖股票的最佳时机（121、Easy）

1）题目要求

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2）我的解法

c++
动态规划

class Solution {
public:int maxProfit(vector<int>& prices) {int mi=9999;int result=0;for(int i=0;i<prices.size();i++){mi=min(mi,prices[i]);result=max(result,prices[i]-mi);}return result;}
};

3）其他解法

状态转移方程：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

public class Solution {public int maxProfit(int prices[]) {int minprice = Integer.MAX_VALUE;int maxprofit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice)minprice = prices[i];else if (prices[i] - minprice > maxprofit)maxprofit = prices[i] - minprice;}return maxprofit;}
}

作者：LeetCode-Solution
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:int maxProfit(vector<int>& prices) {int mi=9999;int result=0;for(int i=0;i<prices.size();i++){mi=min(mi,prices[i]);result=max(result,prices[i]-mi);}return result;}
};

5）学到的东西

分类有点问题。。这题应该放在动态规划部分。。。不过无所谓了

动态规划思想

6、买卖股票的最佳时机 II（122、Easy）

1）题目要求

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

2）我的解法

c++
把每段上升段都加上

class Solution {
public:int maxProfit(vector<int>& prices) {int result=0;if(prices.size()<=1)return 0;for(int i=1;i<prices.size();i++){if(prices[i]>prices[i-1])result+=prices[i]-prices[i-1];}return result;}
};

3）其他解法

public class Solution {private int res;public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}this.res = 0;dfs(prices, 0, len, 0, res);return this.res;}/*** @param prices 股价数组* @param index  当前是第几天，从 0 开始* @param status 0 表示不持有股票，1表示持有股票，* @param profit 当前收益*/private void dfs(int[] prices, int index, int len, int status, int profit) {if (index == len) {this.res = Math.max(this.res, profit);return;}dfs(prices, index + 1, len, status, profit);if (status == 0) {// 可以尝试转向 1dfs(prices, index + 1, len, 1, profit - prices[index]);} else {// 此时 status == 1，可以尝试转向 0dfs(prices, index + 1, len, 0, profit + prices[index]);}}
}

public class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}// 0：持有现金// 1：持有股票// 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < len; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);//存放的即前i个数最大收益//dp[i - 1][0]为前i-1天的最大收益//dp[i - 1][1] + prices[i]为买入前一天股票，并在今天卖出//（并不是真的进行了交易，但是等价于进行了交易，具体解释参考下面的贪心算法）dp[i][1]=dp[i][0]-prices[i];//存放的即如果买入当前股票，还剩的钱}return dp[len - 1][0];}
}

public class Solution {public int maxProfit(int[] prices) {int res = 0;int len = prices.length;for (int i = 0; i < len - 1; i++) {int diff = prices[i + 1] - prices[i];if (diff > 0) {res += diff;}}return res;}
}

作者：liweiwei1419
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:int maxProfit(vector<int>& prices) {int result=0;if(prices.size()<=1)return 0;for(int i=1;i<prices.size();i++){if(prices[i]>prices[i-1])result+=prices[i]-prices[i-1];}return result;}
};

5）学到的东西

画出递归树再进行暴力搜索（改变状态，遍历每种情况）（递归到最下面再回溯）

贪心：不一定排序，每次仅对小范围的几个数进行操作。思考如何拆分成小问题，如本题就是看今天的是否大于昨天的

动态规划：状态转移方程有时是根据暴力法想出来的。

可以对问题进行等价操作，比如本题中虽然不允许卖完又在当天立刻买回来，但在贪心计算时可以这样操作

因为 (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
等价于 prices[3] - prices[0]

7、种花（605、Easy）

1）题目要求

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

2）我的解法

c++

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int result=0;for(int i=0;i<flowerbed.size();i++){if(flowerbed[i]==0){if(flowerbed.size()==1)result++;else if(i==0&&flowerbed[i+1]==0)result++;else if(i==flowerbed.size()-1&&flowerbed[i-1]==0)result++;else if(i>0&&i<flowerbed.size()-1&&flowerbed[i-1]==0&&flowerbed[i+1]==0)result++;else continue;flowerbed[i]=1;}}return n<=result;}
};

3）其他解法

public class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int i = 0, count = 0;while (i < flowerbed.length) {if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {flowerbed[i] = 1;count++;}i++;}return count >= n;}
}

public class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int i = 0, count = 0;while (i < flowerbed.length) {if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {flowerbed[i++] = 1;count++;}if(count>=n)return true;i++;}return false;}
}

作者：LeetCode
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int result=0;for(int i=0;i<flowerbed.size();i++){if(flowerbed[i]==0){if((i==0||flowerbed[i-1]==0)&&(i==flowerbed.size()-1||flowerbed[i+1]==0)){result++;flowerbed[i]=1;}}}return n<=result;}
};

5）学到的东西

贪心思想：思考如何把问题拆分成小问题

尽量简洁的进行判断

8、判断子序列（392、Easy）

1）题目要求

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
s = “abc”, t = “ahbgdc”

返回 true.

示例 2:
s = “axc”, t = “ahbgdc”

返回 false.

后续挑战 :

如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

2）我的解法

c++

class Solution {
public:bool isSubsequence(string s, string t) {int i=0,j=0;while(i<s.length()&&j<t.length()){if(s[i]==t[j])i++;j++;}return i==s.length();}
};

3）其他解法

1、一个一个找

class Solution {public boolean isSubsequence(String s, String t) {int index = -1;for (char c : s.toCharArray()){index = t.indexOf(c, index+1);if (index == -1) return false;}return true;}
}

作者：张英俊
链接：评论区
来源：力扣（LeetCode）

2、动态规划

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size(), m = t.size();vector<vector<int> > f(m + 1, vector<int>(26, 0));for (int i = 0; i < 26; i++) {f[m][i] = m;}for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < 26; j++) {if (t[i] == j + 'a')f[i][j] = i;elsef[i][j] = f[i + 1][j];}}int add = 0;for (int i = 0; i < n; i++) {if (f[add][s[i] - 'a'] == m) {return false;}add = f[add][s[i] - 'a'] + 1;}return true;}
};

作者：LeetCode-Solution
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {
public:bool isSubsequence(string s, string t) {int tlength=t.length();vector<vector<int>> dp(tlength+1,vector<int>(26,-1));for(int i=tlength-1;i>=0;i--){for(int j=0;j<26;j++){if(t[i]==char(j+'a'))dp[i][j]=i;else dp[i][j]=dp[i+1][j];}}int j=0;for(int i=0;i<s.length()&&j<tlength+1;i++){if(dp[j][s[i]-'a']==-1)return false;else j=dp[j][s[i]-'a']+1;}return true;}
};

5）学到的东西

双指针思想

动态规划思想

9、非递减数列（665、Easy）

1）题目要求

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明：

1 <= n <= 10 ^ 4

• 10 ^ 5 <= nums[i] <= 10 ^ 5

2）我的解法

c++

class Solution {
public:bool checkPossibility(vector<int>& nums) {bool tag=false;for(int i=0;i<nums.size()-1;i++){if(nums[i]>nums[i+1]){if(tag)return false;else {if(i>0&&nums[i-1]>nums[i+1]&&i<nums.size()-2&&nums[i]>nums[i+2])return false;else tag=true;}}}return true;}
};

3）其他解法

class Solution {public boolean checkPossibility(int[] nums) {if(nums.length < 3){return true;}int count = 0;for(int i=0;i<nums.length-1;i++){if(nums[i] > nums[i+1]){count++;if(count > 1){break;}if(i-1 >=0&&nums[i-1] > nums[i+1]){nums[i+1] = nums[i];}else{nums[i] = nums[i+1];}}}return count <= 1;}
}

作者：but-2
链接：link
来源：力扣（LeetCode）。

4）自己的优化代码

c++

class Solution {
public:bool checkPossibility(vector<int>& nums) {bool tag=false;for(int i=0;i<nums.size()-1;i++){if(nums[i]>nums[i+1]){if(tag)return false;else {if(i>0&&nums[i-1]>nums[i+1]&&i<nums.size()-2&&nums[i]>nums[i+2])return false;else tag=true;}}}return true;}
};

5）学到的东西

贪心思想

10、最大子序和（53、Easy）

1）题目要求

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

2）我的解法

class Solution {public int maxSubArray(int[] nums) {int result=0,temp=0,temp1=0;if(nums.length==0)return 0;result=nums[0];temp=result;for(int i=1;i<nums.length;i++){temp1=nums[i];temp+=nums[i];if(temp1>=temp){temp=temp1;}result=Math.max(result,temp);}return result;}
}

3）其他解法

class Solution {
public:int maxSubArray(vector<int>& nums) {int pre = 0, maxAns = nums[0];for (const auto &x: nums) {pre = max(pre + x, x);maxAns = max(maxAns, pre);}return maxAns;}
};

作者：LeetCode-Solution
链接：link
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2、贪心

class Solution
{
public:int maxSubArray(vector<int> &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int result = INT_MIN;int numsSize = int(nums.size());int sum = 0;for (int i = 0; i < numsSize; i++){sum += nums[i];result = max(result, sum);//如果sum < 0，重新开始找子序串if (sum < 0){sum = 0;}}return result;}
};

作者：pinku-2
链接：link
来源：力扣（LeetCode）

3、分治

public class Solution {public int maxSubArray(int[] nums) {int len = nums.length;if (len == 0) {return 0;}return maxSubArraySum(nums, 0, len - 1);}private int maxCrossingSum(int[] nums, int left, int mid, int right) {// 一定会包含 nums[mid] 这个元素int sum = 0;int leftSum = Integer.MIN_VALUE;// 左半边包含 nums[mid] 元素，最多可以到什么地方// 走到最边界，看看最值是什么// 计算以 mid 结尾的最大的子数组的和for (int i = mid; i >= left; i--) {sum += nums[i];if (sum > leftSum) {leftSum = sum;}}sum = 0;int rightSum = Integer.MIN_VALUE;// 右半边不包含 nums[mid] 元素，最多可以到什么地方// 计算以 mid+1 开始的最大的子数组的和for (int i = mid + 1; i <= right; i++) {sum += nums[i];if (sum > rightSum) {rightSum = sum;}}return leftSum + rightSum;}private int maxSubArraySum(int[] nums, int left, int right) {if (left == right) {return nums[left];}int mid = (left + right) >>> 1;return max3(maxSubArraySum(nums, left, mid),maxSubArraySum(nums, mid + 1, right),maxCrossingSum(nums, left, mid, right));}private int max3(int num1, int num2, int num3) {return Math.max(num1, Math.max(num2, num3));}
}

作者：liweiwei1419
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

动态规划：

class Solution {public int maxSubArray(int[] nums) {int result=0,temp=0,temp1=0;if(nums.length==0)return 0;result=nums[0];temp=result;for(int i=1;i<nums.length;i++){temp=Math.max(nums[i],temp+nums[i]);result=Math.max(result,temp);}return result;}
}

贪心：

class Solution {public int maxSubArray(int[] nums) {int result=Integer.MIN_VALUE,sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];result=Math.max(sum,result);if(sum<0)sum=0;}return result;}
}

5）学到的东西

动态规划：后面结果依赖于前面部分的结果之上

贪心没有上述特点

没必要纠结这题到底属于什么类型，无论是动态规划还是贪心，能解出来就好

分治：
分开----合并
分类讨论

11、划分字母区间（763、Medium）

1）题目要求

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 ‘a’ 到 ‘z’ 。

2）我的解法

class Solution {public List<Integer> partitionLabels(String S) {List<Integer> result=new ArrayList<>();int[] list=new int[26];Arrays.fill(list,-1);for(int i=0;i<S.length();i++){list[S.charAt(i)-'a']=i;}int j=0,end=0;for(int i=0;i<S.length();i++){end=Math.max(end,list[S.charAt(i)-'a']);j++;if(i==end){result.add(j);j=0;}}return result;}
}

3）其他解法

class Solution {public List<Integer> partitionLabels(String S) {int[] last = new int[26];for (int i = 0; i < S.length(); ++i)last[S.charAt(i) - 'a'] = i;int j = 0, anchor = 0;List<Integer> ans = new ArrayList();for (int i = 0; i < S.length(); ++i) {j = Math.max(j, last[S.charAt(i) - 'a']);if (i == j) {ans.add(i - anchor + 1);anchor = i + 1;}}return ans;}
}

作者：LeetCode
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

c++

class Solution {public List<Integer> partitionLabels(String S) {List<Integer> result=new ArrayList<>();int[] list=new int[26];Arrays.fill(list,-1);for(int i=0;i<S.length();i++){list[S.charAt(i)-'a']=i;}int j=0,end=0;for(int i=0;i<S.length();i++){end=Math.max(end,list[S.charAt(i)-'a']);j++;if(i==end){result.add(j);j=0;}}return result;}
}

5）学到的东西

贪心思想