1005.K次取反后最大化的数组和
总结：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
可以重复一个数一直正负，变换。
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector& A, int K) {
sort(A.begin(), A.end(), cmp); // 第一步
for (int i = 0; i < A.size(); i++) { // 第二步
if (A[i] < 0 && K > 0) {
A[i] *= -1;
K--;
}
}
if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
int result = 0;
for (int a : A) result += a; // 第四步
return result;
}
};
134. 加油站
总结：
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
1、是贪心 当前能见消耗，不是消耗减当前，
2、不是等于 是累加+=
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
135. 分发糖果
总结：
- 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
- 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
class Solution {
public:
int candy(vector& ratings) {
vector candyVec(ratings.size(), 1);
// 从前向后
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] ) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
// 统计结果
int result = 0;
for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
return result;
}
};
860.柠檬水找零
总结：
咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定。
这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。
如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂了。
```cpp
class Solution {
public:
bool lemonadeChange(vector& bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// 情况一
if (bill == 5) five++;
// 情况二
if (bill == 10) {
if (five <= 0) return false;
ten++;
five--;
}
// 情况三
if (bill == 20) {
// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零
} else if (five >= 3) {
five -= 3;
twenty++; // 同理，这行代码也可以删了
} else return false;
}
}
return true;
}
};
406.根据身高重建队列
总结：
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
优先按身高高的people的k来插入。插入操作过后的people满足队列属性
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n (2)了，甚至可能拷贝好几次，就不止O(n)2)了。
改成链表之后，C++代码如下
class Solution {
public:
// 身高从大到小排（身高相同k小的站前面）
static bool cmp(const vector& a, const vector& b) { //第一个元素降序，第二个元素升序
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector> reconstructQueue(vector>& people) {
sort (people.begin(), people.end(), cmp);
list> que; // list底层是链表实现，插入效率比vector高的多
for (int i = 0; i < people.size(); i++) {
int position = people[i][1]; // 插入到下标为position的位置
std::list>::iterator it = que.begin();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector>(que.begin(), que.end());
}
};
另解：
class Solution {
public:
static bool cmp(vector &a, vector b) { // 第一个元素降序，第二个元素升序
return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
}
vector> reconstructQueue(vector>& people) {
list> ans; // list底层使用链表实现，效率更高
// 按照 h 降序， 按照k升序
sort(people.begin(), people.end(), cmp);
int n = people.size(), k;
for (int i = 0; i < people.size(); i++) {
auto it = ans.begin();
k = people[i][1];
while (k--) {
it++; // 从最开始找应该插入的位置
}
ans.insert(it, people[i]); // 在该位置前插入元素
}
return vector>(ans.begin(), ans.end());
}
};
- 时间复杂度：O(nlog n + n^2)
- 空间复杂度：O(n)
