134.加油站
思路
本题中两个数组gas、cost是一个很复杂的东西，而两者作用相反，做差得到类似收益或利润的数组（这是本题的核心思想，很重要）。
图片来源于 灵茶山艾府
上图折线图就是所有的证明：
- 如果
gas总值小于cost，循环跑圈时总油量越来越少，不合实际。 - 如果
gas总值等于cost，在循环中平衡，等价于有解。 - 解是什么？是折线图最低点。
题解
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int count = 0,min = INT_MAX,sum = 0;
for(int i = 0;i<gas.size();i++)
{
gas[i] -= cost[i];
sum += gas[i];
if(sum<min)
{
count = i;
min = sum;
}
}
if(sum>=0)return (count+1)%gas.size();
else return -1;
}
};
135.分发糖果
思路
整体思路很简单：保证比较性，每个节点与左孩子比较一遍，每个节点与右孩子比较一遍。
关键点：要保持累加性，比较方向要与遍历方向相同！（重要思想）
题解
class Solution {
public:
int candy(vector<int>& ratings) {
int count = 0;
vector<int> candy(ratings.size(),1);
for(int i = 0;i<ratings.size()-1;i++)
{
if(ratings[i+1]>ratings[i] && candy[i+1]<=candy[i]) candy[i+1] = candy[i]+1;
}
for(int i = ratings.size()-1;i>=1;i--)
{
if(ratings[i-1]>ratings[i] &&candy[i-1]<=candy[i])candy[i-1] = candy[i]+1;
}
for(auto i:candy)count+=i;
return count;
}
};
860.柠檬水找零
思路
很简单的题目：贪心的点在于能找大的尽量找大的，因为小的更有用。
题解
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0,twenty = 0;
if(bills[0]!=5)return false;
for(int i = 0;i<bills.size();i++)
{
if(bills[i] == 5)five++;
else if(bills[i] == 10)
{
five--;
if(five<0)return false;
ten++;
}
else
{
if(ten>0)
{
ten--;
five--;
if(five<0)return false;
}
else
{
five -= 3;
if(five<0)return false;
}
}
}
return true;
}
};
406.根据身高重建队列
题目链接：406.根据身高重建队列
文档讲解：代码随想录
状态：不会，学习了新思考方向与排序
思路
题目数据有两重，而要求结果是一个有序性问题。
思路：每个元素都要插入到属于它的位置，所以这一步so easy，问题转化为了从哪里开始遍历才能保证插进去是对的？
- 选择给
people数组排序，按k值排序（位置），插入时身高会影响位置，待定······ - 选择按
h值排序（身高），后面插入一定不会影响前面，有戏！- 如果相同
h值k不同咋办呢？小脑筋一动，还是前面不影响后面，问题解决！
- 如果相同
题解
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b)
{
if(a[0] == b[0]) return a[1]<b[1];
return a[0]>b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
list<vector<int>> que;
for(int i = 0;i<people.size();i++)
{
auto it = que.begin();
advance(it,people[i][1]);
//int num = people[i][1];
//while(num--)it++;
que.insert(it,people[i]);
}
return vector<vector<int>>(que.begin(),que.end());
}
};
406题知识补充
小小一个题目蕴含着很大的知识量
sort对多维排序
sort排序写法：
//是针对迭代器，若有高要求自写cmp
sort(people.begin(),people.end(),cmp);
cmp比较函数的写法：
//当作模板记住，包括返回值、参数、大、小于号与排序
//static 函数属于类本身，不属于实例对象
static bool cmp(const vector<int>& a, const vector<int>& b)
{
if(a[0] == b[0]) return a[1]<b[1];
return a[0]>b[0];
}
vector与list容器
vector<int> 代表动态数组，里面的元素都是int类型。
对于406题未初始化数组频繁插入：
对于普通数组，一旦定义了大小就不能改变，例如int a[10]，这个数组a至多只能放10个元素，改不了的。
对于动态数组(vector)，就是可以不用关心初始时候的大小，可以随意往里放数据，那么耗时的原因就在于动态数组的底层实现。
动态数组为什么可以不受初始大小的限制，可以随意push_back数据呢？
当insert数据的时候，如果已经大于capicity，capicity会成倍扩容，但对外暴漏的size其实仅仅是+1。
那么既然vector底层实现是普通数组，怎么扩容的？
就是重新申请一个二倍于原数组大小的数组，然后把数据都拷贝过去，并释放原数组内存。（对，就是这么原始粗暴的方法！）如下图所示：
所以，本题极多次插入，也就是调用了超多次创建（扩容），拷贝操作，复杂度不变的情况下，多于操作增多，时间增加。
list<int> 代表双向链表，里面的元素都是int类型。
它支持在任意位置快速插入和删除元素（时间复杂度极低，参考链表），但不支持随机访问（即不能直接通过索引访问元素，只能通过迭代器遍历（类似cur = cur->next））。这使得它在某些场景下非常有用，尤其是在需要频繁插入和删除元素时。
常见用法：
auto it = que.begin();
advance(it, n);
//等价于advance,不支持.begin()+n操作
//int num = n;
//while(num--)it++;
//n前插入
que.insert(it,n);
所以对于本题频繁插入，使用list明显更实用。