【每日刷题】Day17
🥕个人主页:开敲🍉
🔥所属专栏:每日刷题🍍
🌼文章目录🌼
1. 19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
2. 162. 寻找峰值 - 力扣(LeetCode)
3. 164. 最大间距 - 力扣(LeetCode)
1. 19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
//思路:两个指针分别定位要删除的节点以及要删除节点的上一个节点。
typedef struct ListNode LN;
int ListNodeQua(LN* phead)//计算链表节点数
{
LN* pmove = phead;
int count = 0;
while(pmove)
{
count++;
pmove = pmove->next;
}
return count;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
if(head==NULL||head->next==NULL)//因为n≥1,因此链表如果只有一个节点,则直接返回NULL
{
return NULL;
}
LN* pcur = head;//定位要删除的节点的指针
LN* prev = head;//定位要删除节点的上一个节点的指针
int count = ListNodeQua(head)-n;//第一个节点与要删除节点的距离
while(count)//定位要删除节点
{
pcur = pcur->next;
count--;
}
if(prev==pcur)//这里需要考虑头删的情况,头删则prev和pcur都指向第一个节点,则直接让head指向head->next返回即可
{
head = head->next;
return head;
}
while(prev->next!=pcur)//定位要删除节点的上一个节点
{
prev = prev->next;
}
prev->next = pcur->next;//将要删除节点的上一个节点的next指向要删除节点的下一个节点
free(pcur);//直接释放pcur以删除节点
return head;
}
2. 162. 寻找峰值 - 力扣(LeetCode)
//0ms 100%思路:使用一个新的数组存储所给数组的数据,新数组的长度为原数组长度+2,因为第一个以及最后一个元素放INT_MIN,用于解决峰值出现在原数组第一个以及最后一个的情况
int findPeakElement(int* nums, int numsSize)
{
int i = 0;
int arr[numsSize+2];
arr[0] = INT_MIN;
arr[numsSize+1] = INT_MIN;
for(i = 0;i<numsSize;i++)
{
arr[i+1] = nums[i];
}
for(i = 1;i<=numsSize;i++)
{
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
return i-1;
}
}
return 0;
}
3. 164. 最大间距 - 力扣(LeetCode)
//思路:暴力遍历。使用qsort库函数将数组排为升序,然后暴力遍历数组,计算每个相邻数据的间距,使用max接收最大的,直接返回max
int cmp(const void* x,const void* y)
{
return *(int*)x-*(int*)y;
}
int maximumGap(int* nums, int numsSize)
{
if(numsSize<2)
{
return 0;
}
qsort(nums,numsSize,sizeof(int),cmp);
int max = 0;
for(int i = 0;i<numsSize-1;i++)
{
if(nums[i+1]-nums[i]>max)
{
max = nums[i+1]-nums[i];
}
}
return max;
}