一、860 柠檬水找零
题目解析:注意一开始是没有零钱,也只会取5 10 20三类数字,因此从这3类数字出发,去判断。
1 如果是5元,那么直接收,five++;
2 如果是10元,那么需要five--,ten++,但是如果five本身就小于0,那么不可能找零成功,返回false;
3 如果是20元,这里需要看有多少种零钱找零方式:1)10元+5元组合; 2)5+5+5组合;首先需要消耗10元,因为5元可以兑换零钱方式更多,先把兑换方式少的减掉。
bool lemonadeChange(int* bills, int billsSize) {
int five = 0, ten = 0, twenty = 0;
for(int i = 0; i < billsSize; i++)
{
if(bills[i] == 5)
{
five++;
}
else if(bills[i] == 10)
{
ten++;
if(five > 0)
{
five--;
}
else
{
//five没有 无法找零
return false;
}
}
else
{
if(ten > 0 && five > 0)
{
ten--;
five--;
}
else if(five >= 3)
{
five -=3;
}
else
{
return false;
}
}
}
return true;
}
二、406 根据身高重建队列
题目要求重建队列,保证身高和前面的人数两个方面,需要从两个方面去拆分排序。
1 先考虑身高,从高到低,如果身高相同,那么k(人数)少的排前面。
2 排序k(人数)因为身高已经排序成功,所以需要考虑的是k值,把k插入对应的位置,这样people身高是排序的,只需要考虑k的位置,就满足了两个条件。
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void insert(int**arr, int size, int pos, int* val)
{
int** tmp = (int**)malloc(sizeof(int*) * size);
int index = 0;
for(int i = pos; i < size; i++)
{
tmp[index] = malloc(sizeof(int) * 2);
tmp[index][0] = arr[i][0];
tmp[index][1] = arr[i][1];
index++;
}
//改值
arr[pos][0] = val[0];
arr[pos][1] = val[1];
index = 0;
for(int i = pos + 1; i < size; i++)
{
arr[i][0] = tmp[index][0];
arr[i][1] = tmp[index][1];
index++;
}
// for(int i = 0; i < size; i++)
// {
// printf("val = %d %d\n", arr[i][0], arr[i][1]);
// }
}
void swap(int* a, int* b)
{
int tmp_1 = a[0];
int tmp_2 = a[1];
a[0] = b[0];
a[1] = b[1];
b[0] = tmp_1;
b[1] = tmp_2;
}
int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = peopleSize;
*returnColumnSizes = (int*)malloc(peopleSize * sizeof(int));
//先排列身高
for(int i = 0; i < peopleSize - 1; i++)
{
for(int j = i + 1; j < peopleSize; j++)
{
if(people[j][0] == people[i][0])
{
if(people[j][1] < people[i][1])
{
// int tmp_1 = people[j][0];
// int tmp_2 = people[j][1];
// people[j][0] = people[i][0];
// people[j][1] = people[i][1];
// people[i][0] = tmp_1;
// people[i][1] = tmp_2;
swap(people[j], people[i]);
}
}
else if(people[j][0] > people[i][0])
{
// int tmp_1 = people[j][0];
// int tmp_2 = people[j][1];
// people[j][0] = people[i][0];
// people[j][1] = people[i][1];
// people[i][0] = tmp_1;
// people[i][1] = tmp_2;
swap(people[j], people[i]);
}
}
}
//再查看 k值
int** queue = (int**)malloc(sizeof(int*) * peopleSize);
for(int i = 0; i < peopleSize; i++)
{
queue[i] = (int*)malloc(sizeof(int) * 2);
queue[i][0] = people[i][0];
queue[i][1] = people[i][1];
}
for(int i = 0; i < peopleSize; i++)
{
(*returnColumnSizes)[i] = 2;
//printf("%d -> pepeple %d %d\n", i, people[i][0], people[i][1]);
insert(queue, peopleSize, people[i][1], people[i]);
}
return queue;
}
三、452. 用最少数量的箭引爆气球
题目分析:用最少的箭引爆气球,主要是考虑重叠情况,如果重叠区间越多,那么使用的箭数量越少,利用排序 + 贪心算法:
void swap(int* a, int* b)
{
int tmp_1 = a[0];
int tmp_2 = a[1];
a[0] = b[0];
a[1] = b[1];
b[0] = tmp_1;
b[1] = tmp_2;
}
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
*pointsColSize = 2;
if(pointsSize == 0)
{
return 0;
}
int result = 1;
//按照左边界排序
for(int i = 0; i < pointsSize - 1; i++)
{
for(int j = i + 1; j < pointsSize; j++)
{
if(points[j][0] < points[i][0])
{
swap(points[i], points[j]);
}
}
}
for(int i = 1; i < pointsSize; i++)
{
if(points[i][0] > points[i -1][1])
{
result++;
}
else
{
points[i][1] = points[i][1] < points[i -1][1]? points[i][1] : points[i - 1][1];//最小右边界
}
}
return result;
}
上面的code在LeetCode上面会超时,分析了下,应该是排序算法导致的,因此参考快排的算法:
void swap(int* a, int* b)
{
int tmp_1 = a[0];
int tmp_2 = a[1];
a[0] = b[0];
a[1] = b[1];
b[0] = tmp_1;
b[1] = tmp_2;
}
int Partition(int **points, int low, int high){ // 从小到大排序
int base = points[low][0];
int index = points[low][1];
int left,right;
while(low < high){
while(low < high && points[high][0] >= base){
high--;
}
left = points[low][0];
right = points[low][1];
points[low][0] = points[high][0];
points[low][1] = points[high][1];
points[high][0] = left;
points[high][1] = right;
while(low < high && points[low][0] <= base){
low++;
}
left = points[low][0];
right = points[low][1];
points[low][0] = points[high][0];
points[low][1] = points[high][1];
points[high][0] = left;
points[high][1] = right;
}
return low;
}
void QuickSort(int **points, int low, int high){
if(low < high){
int base = Partition(points,low,high);
QuickSort(points,low,base - 1);
QuickSort(points, base + 1, high);
}
}
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
*pointsColSize = 2;
if(pointsSize == 0)
{
return 0;
}
int result = 1;
//按照左边界排序
// for(int i = 0; i < pointsSize - 1; i++)
// {
// for(int j = i + 1; j < pointsSize; j++)
// {
// if(points[j][0] < points[i][0])
// {
// swap(points[i], points[j]);
// }
// }
// }
QuickSort(points, 0 , pointsSize - 1);//左闭右闭区间
for(int i = 1; i < pointsSize; i++)
{
if(points[i][0] > points[i -1][1])//如果当前的左边超过了上一个的右边边界,不重叠
{
result++;
}
else//找到重叠区间最小右边界
{
points[i][1] = points[i][1] < points[i -1][1]? points[i][1] : points[i - 1][1];//最小右边界
}
}
return result;
}