【每日刷题】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;

}