【每日刷题】Day75
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1833. 雪糕的最大数量 - 力扣（LeetCode）
2. 面试题 17.14. 最小K个数 - 力扣（LeetCode）
3. 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
1. 1833. 雪糕的最大数量 - 力扣（LeetCode）
//思路：记数排序。
//记数排序
void CountSort(int* arr,int size)
{
int* hash = (int*)calloc(100001,sizeof(int));
int max = 0;
int count = 0;
for(int i = 0;i<size;i++)
{
hash[arr[i]]+=1;
if(arr[i]>max)
max = arr[i];
}
for(int i = 1;i<=max;i++)
{
while(hash[i])
{
arr[count++] = i;
hash[i]--;
}
}
}
int maxIceCream(int* costs, int costsSize, int coins)
{
int ans = 0;
CountSort(costs,costsSize);
for(int i = 0;i<costsSize;i++)
{
if(coins-costs[i]>=0)
{
coins-=costs[i];
ans++;
}
else
break;
}
return ans;
}
2. 面试题 17.14. 最小K个数 - 力扣（LeetCode）
//思路：TopK问题。采用堆排序将所求的K个数排入堆底。
//交换
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向下调整
void AdjustDown(int* arr, int parents, int size)
{
int child = parents * 2 + 1;
while (child < size)
{
if (child + 1 < size && arr[child + 1] < arr[child])
child++;
if (arr[child] < arr[parents])
Swap(&arr[child], &arr[parents]);
else
break;
parents = child;
child = parents * 2 + 1;
}
}
void TopK(int* arr, int size, int k)
{
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(arr, i, size);
}
while (k)//循环K次，每次将最小的数排入堆底
{
Swap(&arr[0], &arr[size - 1]);
k--;
size--;
AdjustDown(arr, 0, size);
}
}
int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{
TopK(arr,arrSize,k);
int* ans = (int*)malloc(sizeof(int)*100000);
int count = 0;
for(int i = arrSize-1;i>=arrSize-k;i--)
{
ans[count++] = arr[i];//拿取堆底的K个数
}
*returnSize = count;
return ans;
}
3. 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
//思路①：哈希
bool isUnique(char* astr)
{
int hash[27] = {0};
for(int i = 0;i<strlen(astr);i++)
{
hash[astr[i]-'a']+=1;
}
for(int i = 0;i<27;i++)
{
if(hash[i]>1)
return false;
}
return true;
}
//思路②：排序+一次遍历。选用插入排序，不需要开辟额外的空间，效率也不错。
//插入排序
void Insert(char* arr)
{
for(int i = 0;i<strlen(arr)-1;i++)
{
int end = i+1;
char tmp = arr[end];
while(end-1>=0)
{
if(arr[end-1]>tmp)
arr[end] = arr[end-1];
else
break;
end--;
}
arr[end] = tmp;
}
}
bool isUnique(char* astr)
{
if(!strlen(astr))
return true;
Insert(astr);
for(int i = 0;i<strlen(astr)-1;i++)
{
if(astr[i]==astr[i+1])
return false;
}
return true;
}
