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