本文主要是介绍【每日刷题】Day62,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【每日刷题】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;
}
这篇关于【每日刷题】Day62的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!