【每日刷题】Day62

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 852. 山脉数组的峰顶索引 - 力扣（LeetCode）

2. 2806. 取整购买后的账户余额 - 力扣（LeetCode）

3. 2415. 反转二叉树的奇数层 - 力扣（LeetCode）

1. 852. 山脉数组的峰顶索引 - 力扣（LeetCode）

//O(logN)思路：二分查找。根据题意，我们假设峰顶下标为ans。容易知道，对于每一个＜ans的 i ，都满足arr[i]<arr[i+1]；对于每一个＞ans的 i ，都满足arr[i]>arr[i+1]。因此我们使用二分查找的思路就是定义一个left和right，开始分别指向数组头和尾，再定义一个mid(mid = (left+right)/2)，mid根据lefth和right的变化而改变。

//① 如果arr[mid]<arr[mid+1]，说明峰顶在当前mid下标处或者mid下标右侧，让left＝mid+1，将mid向右挪动

//② 如果arr[mid]>arr[mid+1]，说明峰顶在当前mid下标处或者mid下标左侧，让right = mid-1，将mid向左挪动。

int peakIndexInMountainArray(int* arr, int arrSize)

{

    int ans = 0;

    int left = 0;

    int right = arrSize-1;

    while(left<=right)

    {

        int mid = (left+right)/2;//中间下标

        if(arr[mid]>arr[mid+1])//峰顶在mid处或者mid左侧

        {

            ans = mid;//记下当前下标，可能为峰顶

            right = mid-1;

        }

        else//这里没有记下当前下标，因为是二分查找，只需要记一边即可

            left = mid+1;//峰顶在mid右侧

    }

    return ans;

}

2. 2806. 取整购买后的账户余额 - 力扣（LeetCode）

//思路：遍历取小值。

int accountBalanceAfterPurchase(int purchaseAmount)

{

    int num = 0;

    int flag1 = 0;

    int flag2 = 0;

    for(int i = 0;i<=10;i++)

    {

        if(num<purchaseAmount)

            num+=10;

        else

        {

            flag1 = num-10;//90

            flag2 = num;//100

            break;

        }

    }

    int ans = (abs(flag1-purchaseAmount)<abs(flag2-purchaseAmount))?flag1:flag2;

    return 100-ans;

}

3. 2415. 反转二叉树的奇数层 - 力扣（LeetCode）

//思路：暴力求解。首先层序遍历将二叉树中的值存入数组中，因为是完美二叉树，因此我们很容易可以知道二叉树奇数层在数组中的区域。对数组中属于二叉树奇数层区域的数据进行翻转。翻转后的数组再进行层序遍历存回二叉树中。

typedef struct TreeNode TN;

 

typedef struct listnode

{

    struct TreeNode* val;

    struct listnode* next;

}LN;

struct TreeNode* reverseOddLevels(struct TreeNode* root)

{

    int* arr = (int*)malloc(sizeof(int)*20000);

    int count = 1;

//层序遍历存入数组↓↓↓

    LN* phead = (LN*)malloc(sizeof(LN));

    LN* ptail = phead;

    LN* node = (LN*)malloc(sizeof(LN));

    node->val = root;

    node->next = NULL;

    ptail->next = node;

    ptail = ptail->next;

    while(phead!=ptail)

    {

        struct TreeNode* tmp = phead->next->val;

        phead = phead->next;

        arr[count++] = tmp->val;

        if(tmp->left)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->left;

            node->next = NULL;

            ptail->next = node;

            ptail = ptail->next;

        }

        if(tmp->right)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->right;

            node->next = NULL;

            ptail->next = node;

            ptail = ptail->next;

        }

    }

//层序遍历存入数组↑↑↑

//数组翻转↓↓↓

    int flag = 2;

    while(flag<count)

    {

        int flag1 = flag*2-1;

        int flag2 = flag1;

        while(flag<flag1)

        {

            int tmp = arr[flag];

            arr[flag] = arr[flag1];

            arr[flag1] = tmp;

            flag++;

            flag1--;

        }

        flag = (flag2+1)*2;

    }

//数组翻转↑↑↑

//层序遍历回放二叉树↓↓↓

    LN* phead1 = (LN*)malloc(sizeof(LN));

    LN* ptail1 = phead1;

    LN* node1 = (LN*)malloc(sizeof(LN));

    node1->val = root;

    node1->next = NULL;

    ptail1->next = node1;

    ptail1 = ptail1->next;

    int count1 = 1;

    while(count1<count)

    {

        struct TreeNode* tmp = phead1->next->val;

        phead1 = phead1->next;

        tmp->val = arr[count1++];

        if(count1<count&&tmp->left)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->left;

            node->next = NULL;

            ptail1->next = node;

            ptail1 = ptail1->next;

        }

        if(count1<count&&tmp->right)

        {

            LN* node = (LN*)malloc(sizeof(LN));

            node->val = tmp->right;

            node->next = NULL;

            ptail1->next = node;

            ptail1 = ptail1->next;

        }

    }

    return root;

}