【每日刷题】Day58
【每日刷题】Day58
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 3038. 相同分数的最大操作数目 I - 力扣（LeetCode）
2. 868. 二进制间距 - 力扣（LeetCode）
3. 287. 寻找重复数 - 力扣（LeetCode）
1. 3038. 相同分数的最大操作数目 I - 力扣（LeetCode）
//思路：放松题，无思路。
int maxOperations(int* nums, int numsSize)
{
int ans = 1;
int flag = nums[0]+nums[1];
for(int i = 2;i<numsSize-1;i+=2)
{
if((nums[i]+nums[i+1])==flag)
ans++;
else
break;
}
return ans;
}
2. 868. 二进制间距 - 力扣（LeetCode）
//0ms 100％思路：简易队列。将n的每一个为1的位入列，队列中保证只有两个元素，将队列中第二个元素减去第一个元素就是相邻为1的位的距离，队列满了以后将队头元素删除，整体向前挪动一位。
int binaryGap(int n)
{
int ans = 0;
int q[2] = { 0 };
int flag = 1;
int num = 0;
for (int i = 1; i <= 30; i++)
{
if ((n & flag) != 0)
q[num++] = i;
if (num == 2)
{
ans = ans > (q[1] - q[0]) ? ans : (q[1] - q[0]);
q[0] = q[1];
num = 1;
}
flag <<= 1;
}
return ans;
}
3. 287. 寻找重复数 - 力扣（LeetCode）
//思路：排序+遍历。将数组进行排序，由于题目要求不能使用额外空间，同时还需要考虑排序效率的问题，这里采用堆排对数组进行排序。排序后前后指针遍历数组，如果双指针指向下标数组元素相等，直接返回。
void Swap(int* x,int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整建堆void AdjustUp(int* arr,int child)
{
int parents = (child-1)/2;
while(child>0)
{
if(arr[child]>arr[parents])
Swap(&arr[child],&arr[parents]);
else
break;
child = parents;
parents = (child-1)/2;
}
}
//向下调整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]);
parents = child;
child = parents*2+1;
}
}
//堆排void HeapSort(int* arr,int size)
{
for(int i = 0;i<size;i++)
{
AdjustUp(arr,i);
}
while(size)
{
Swap(&arr[0],&arr[size-1]);
size--;
AdjustDown(arr,0,size);
}
}
int findDuplicate(int* nums, int numsSize)
{
int ans = 0;
HeapSort(nums,numsSize);
for(int i = 0;i<numsSize-1;i++)
{
if(nums[i]==nums[i+1])
{
ans = nums[i];
break;
}
}
return ans;
}