【每日刷题】Day50
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 654. 最大二叉树 - 力扣（LeetCode）
2. 119. 杨辉三角 II - 力扣（LeetCode）
3. 735. 小行星碰撞 - 力扣（LeetCode）
1. 654. 最大二叉树 - 力扣（LeetCode）
//思路：递归遍历，通过不断改变左右区间找到最大值，从而保证在最大值左边构建子树以及最大值右边构建子树。
typedef struct TreeNode TN;
TN* CreatBinaryTree(int* nums,int left,int right)
{
if(left>right)//当区间不存在时，说明已经没有值能找了，直接返回NULL
return NULL;
int max = left;
for(int i = left;i<=right;i++)
{
if(nums[i]>nums[max])//定位当前最大值的下标，作为下一次寻找左右最大结点的区间
{
max = i;
}
}
TN* node = (TN*)malloc(sizeof(TN));
node->val = nums[max];
node->left = CreatBinaryTree(nums,left,max-1);
node->right = CreatBinaryTree(nums,max+1,right);
return node;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize)
{
return CreatBinaryTree(nums,0,numsSize-1);
}
2. 119. 杨辉三角 II - 力扣（LeetCode）
//思路：构建杨辉三角。
int* getRow(int rowIndex, int* returnSize)
{
int** arr = (int**)malloc(sizeof(int*)*34);
for(int i = 0;i<34;i++)
{
arr[i] = (int*)malloc(sizeof(int)*35);
}
for(int i = 0;i<34;i++)
{
arr[i][0] = 1;
arr[i][i] = 1;
}
for(int i = 2;i<34;i++)
{
for(int j = 1;j<i;j++)
{
arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
}
}
int* ans = (int*)malloc(sizeof(int)*34);
int count = 0;
for(int i = 0;i<rowIndex+1;i++)
{
ans[count++] = arr[rowIndex][i];
}
*returnSize = count;
return ans;
}
3. 735. 小行星碰撞 - 力扣（LeetCode）
//思路：栈。遍历数组，入栈情况: ① 如果栈中没有元素则入栈 ② 如果数组当前元素＞0，则不可能发生碰撞，入栈 ③ 如果栈顶元素＜0并且数组当前元素也＜0，入栈
出栈情况: 如果栈顶元素＞0并且数组当前元素＜0，则要判断是否出栈。① 如果数组当前元素的绝对值＞栈顶元素，则将栈顶元素替换为当前数组元素，并继续跟栈顶下一个元素比较
② 如果数组当前元素的绝对值＝栈顶元素，则直接将栈顶元素出栈，不进行入栈操作
③ 如果数组当前元素的绝对值＜栈顶元素，则不进行操作。
注意:这里需要考虑到当 是第①种出栈情况时，需要考虑到栈顶下面元素也为负数，或者栈的下标为0的情况。
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize)
{
int* ans = (int*)malloc(sizeof(int)*10000);
int count = 0;
for(int i = 0;i<asteroidsSize;i++)
{
if(count==0||asteroids[i]>0||(asteroids[i]<0&&ans[count-1]<0))//入栈情况
{
ans[count++] = asteroids[i];
}
else
{
while(count&&(asteroids[i]*(-1))>ans[count-1]&&ans[count-1]>0)//当前数组元素的绝对值大于栈顶元素，并且栈顶元素必须＞0才能发生碰撞
{
ans[--count] = asteroids[i];
}
if(count==0||(asteroids[i]<0&&ans[count-1]<0))//考虑到 10 5 -15 这种一路碰撞到栈下标为0或者栈顶下面元素都为负数的情况，需要将返回大小+1
{
count++;
}
if(count&&(asteroids[i]*(-1))==ans[count-1])//如果当前数组元素绝对值与栈顶元素相同，则同归于尽
{
count--;
}
}
}
*returnSize = count;
return ans;
}
