LeetCode解题记录(贪心算法)（二）
1. 前言
由于后面还有很多题型要写，贪心算法目前可能就到此为止了，上一篇博客的地址为
LeetCode解题记录(贪心算法)（一）
下面正式开始我们的刷题之旅
2. 贪心
763. 划分字母区间（中等）
思路
想切割，要有首尾两个指针，确定了结尾指针，就能确定下一个切割的开始指针。
遍历字符串，如果已扫描部分的所有字符，都只出现在已扫描的范围内，即可做切割。
注意 ： 贪心的思想为，只要是扫描过的字符，都出现在我扫描的范围之类，我就切割，不去考虑其他的条件，这样能保证切割的数量最多
代码实现思路
- result 用来保存结果
- start end，片断的首尾指针
- map 存放每一个字符的最远位置
首先通过一个map，记录了每个字符的最远的位置，接下来遍历字符串，end是用来记录，当前已经扫描的字符串的最远的出现的位置，如果当前的位置，等于扫描的字符串的最远位置，则，可以证明，到达了切割的条件，然后切割，存到result里
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> result;
unordered_map<char, int> map; //记录char c 和其最后出现位置的 map
int start = 0, end = 0;
// 初始化map，记录每一个字符的最后位置
for (int i = 0; i < S.size(); i ++) {
map[S[i]] = i;
}
for (int i = 0; i < S.size(); i ++) {
end = max(end, map[S[i]]);//记录已扫描字符的最后一次出现的位置
if (i == end) {//说明后面的片段没有出现重复的字母了
result.push_back(end - start + 1);//记录结果
start = i + 1;
}
}
return result;
}
};
406. 根据身高重建队列(中等)
解题思路
贪心算法：按照身高从高到低进行排序，矮的放后面，因为矮的即使放在了高的前面，也不会对之前高的产生影响；但高的放在前面，对矮的结果就会产生影响了。
重写 compare() 方法：身高相同，按照个数升序排序；身高不同，按照身高降序排序。
public int compare(int[] o1, int[] o2) {
// 先按身高降序，若身高相同则按 k 值升序。
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}
第二个数字作为索引位置，把数组放在目标索引位置上，如果原来有数了，会往后移。（在一个 ListList 中的指定位置插入一个元素，当前指定位置的元素会往后面移动一个位置。）
遍历排序后的数组，根据 K 插入到 K 的位置上。
class Solution {
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
int m = people[0].length;
if (n == 0 || m == 0) return new int[0][0];
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// 先按身高降序，若身高相同则按 k 值升序。
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}
});
// 遍历排序后的数组，根据 K 插入到 K 的位置上。
List<int[]> list = new ArrayList<>();
for (int[] i : people) {
list.add(i[1], i);
}
return list.toArray(new int[list.size()][2]);
}
}
665. 非递减数列
给你一个长度为 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
题解:
贪心算法
本题是要维持一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。
但是本题唯一的易错点就在这，
如果将nums[i]缩小，可能会导致其无法融入前面已经遍历过的非递减子数列；
如果将nums[i + 1]放大，可能会导致其后续的继续出现递减；
所以要采取贪心的策略，在遍历时，每次需要看连续的三个元素，也就是瞻前顾后，遵循以下两个原则：
需要尽可能不放大nums[i + 1]，这样会让后续非递减更困难；
就是能不放大就不放大，尽量与前面持平
如果缩小nums[i]，但不破坏前面的子序列的非递减性；
算法步骤：
遍历数组，如果遇到递减：
还能修改：
修改方案1：将nums[i]缩小至nums[i + 1]；
这个方案是，用i-1,i,i+1,来表示三个数的位置，其中i是我们发现大于i+1的数，那么当i+1大于i-1的时候，我们应该将i缩小至i+1，为什么呢，你想啊，你右边的数比你小，你左边的数比你小，但是呢，你右边的数比你左边的数高，你是不是只需要和你右边的一样高，就能保持非递减？如果你不这样，你让右边的数增加，这就违反了上面的第一条原则：需要尽可能不放大nums[i + 1]，这样会让后续非递减更困难，因为这种情况，我们的选择是缩小i
修改方案2：将nums[i + 1]放大至nums[i]；
这种情况是什么呢，与上一种相反，你左边右边的数都比你小，但是你右边的数比你左边的数要小，这个时候我们就应该将右边的数放大，放大至nums[i]，也就是你的大小，这种情况下是没有争论的，只能将右边的数放大，不明白的同学可以自己在纸上画一画
如果不能修改了：直接返回false；
这个代码需要修改两个地方，显然不符合题目要求，返回false
代码如下
flag 代表修改机会，因为只有一次，所以用掉了，flag就变成false
class Solution {
public:
bool checkPossibility(vector<int>& nums)
{
if (nums.size() == 1) return true;
bool flag = nums[0] <= nums[1] ? true : false; // 标识是否还能修改
// 遍历时，每次需要看连续的三个元素
for (int i = 1; i < nums.size() - 1; i++)
{
if (nums[i] > nums[i + 1]) // 出现递减
{
if (flag) // 如果还有修改机会，进行修改
{
if (nums[i + 1] >= nums[ i - 1])// 修改方案1
nums[i] = nums[i + 1];
else // 修改方案2
nums[i + 1] = nums[i];
flag = false; // 用掉唯一的修改机会
}
else // 没有修改机会，直接结束
return false;
}
}
return true;
}
};
执行结果
3. 总结
对不起各位，我算法这块更新的实在是太慢了，不过最近真的很忙很忙，当然有时候我也会娱乐一下，没有做到自律，下个星期我还准备开始写计算机网络和操作系统的专栏，所以算法这块，我尽量多写（其实我就是懒，有时候晚上回家真的好累，不想写算法题，，，，）
总之，下个星期，继续努力，与昨天的自己比较！
