【每日刷题】Day54
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 575. 分糖果 - 力扣（LeetCode）
2. 147. 对链表进行插入排序 - 力扣（LeetCode）
3. 137. 只出现一次的数字 II - 力扣（LeetCode）
1. 575. 分糖果 - 力扣（LeetCode）
//思路：哈希表。维护一个哈希表，由于给定数组中的元素可能为负数，因此需要对哈希表的键进行改良。
int distributeCandies(int* candyType, int candyTypeSize)
{
int count = candyTypeSize/2;
int hash[200001] = {0};//题目所给数在 -10^5~10^5，因此我们将所有负数加上10^5
for(int i = 0;i<candyTypeSize;i++)
{
hash[candyType[i]+100000]+=1;
}
int ans = 0;
for(int i = 0;i<200001;i++)
{
if(hash[i]>0)
ans++;
}
if(ans<count)
return ans;
return count;
}
2. 147. 对链表进行插入排序 - 力扣（LeetCode）
//思路：插入排序。对链表插入排序十分困难，因此我们可以将链表存储进数组，对数组进行插入排序，再将数组转换为链表。
typedef struct ListNode LN;
//插入排序
void InsertSort(int* arr,int size)
{
for (int i = 0; i < size-1; i++)
{
int end = i + 1;
int tmp = arr[end];
while (end - 1 >= 0)
{
if (tmp < arr[end - 1])
{
arr[end] = arr[end - 1];
}
else
{
break;
}
end--;
}
arr[end] = tmp;
}
}
struct ListNode* insertionSortList(struct ListNode* head)
{
int arr[5001] = {0};
LN* pmove = head;
int count = 0;
while(pmove)//链表转数组
{
arr[count++] = pmove->val;
pmove = pmove->next;
}
InsertSort(arr,count);//插入排序
LN* newhead = (LN*)malloc(sizeof(LN));
LN* Sentry = newhead;
for(int i = 0;i<count;i++)//数组转链表
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = arr[i];
newhead->next = newnode;
newhead = newhead->next;
}
return Sentry->next;
}
3. 137. 只出现一次的数字 II - 力扣（LeetCode）
//思路：排序。对原数组进行排序。只有一个元素出现一次，其余元素均出现三次，因此我们对排序后的数组遍历，出现三次的元素一定是相邻的。如果相邻的两个元素相同，则i+=3继续向后遍历；否则，只出现一次的元素一定是当前i下标的元素。本题采用的快排为自行实现。
//交换
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//三数取中
int GetMid(int* arr,int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] > arr[right])
{
if (arr[mid] > arr[left])
{
return left;
}
else if (arr[right] > arr[mid])
{
return right;
}
else
{
return mid;
}
}
else
{
if (arr[right] < arr[mid])
{
return right;
}
else if (arr[mid] > arr[left])
{
return mid;
}
else
{
return left;
}
}
}
//插入排序
void InsertSort(int* arr,int size)
{
for (int i = 0; i < size-1; i++)
{
int end = i + 1;
int tmp = arr[end];
while (end - 1 >= 0)
{
if (tmp < arr[end - 1])
{
arr[end] = arr[end - 1];
}
else
{
break;
}
end--;
}
arr[end] = tmp;
}
}
//快速排序
void QuickSort(int* arr,int left,int right)
{
if (left >= right)
return;
//小区间优化
if ((right - left + 1) < 10)
{
InsertSort(arr + left, right - left + 1);
}
else
{
//三数取中优化
int mid = GetMid(arr, left, right);
Swap(&arr[mid], &arr[left]);
int key = left;
int begin = left;
int end = right;
while (begin < end)
{
while (begin < end && arr[end] >= arr[key])
{
end--;
}
while (begin < end && arr[begin] <= arr[key])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[begin], &arr[key]);//相遇后与key交换
key = begin;
QuickSort(arr, left, key - 1);
QuickSort(arr, key + 1, right);
}
}
int singleNumber(int* nums, int numsSize)
{
QuickSort(nums,0,numsSize-1);
int i = 0;
for(;i<numsSize-1;i+=3)
{
if(nums[i]!=nums[i+1])
return nums[i];
}
return nums[i];
}
