【每日刷題】Day53
🥕個人主頁：開敲🍉
🔥所屬專欄：每日刷題🍍
🌼文章目錄🌼
1.?1019. 鏈表中的下一個更大節點 - 力扣（LeetCode）
2.?116. 填充每個節點的下一個右側節點指針 - 力扣（LeetCode）
3.?412. Fizz Buzz - 力扣（LeetCode）
1.?1019. 鏈表中的下一個更大節點 - 力扣（LeetCode）
//思路：棧。將鏈表中的元素存入一個數組。遍歷這個數組，將數組元素的下標入棧。
//入棧情況：① 如果當前棧中沒有元素，直接入棧? ② 如果數組當前元素＜數組以當前棧頂元素為下標的元素，直接入棧。
//出棧情況：如果數組當前元素＞數組以當前棧頂元素為下標的元素，將答案數組中當前棧頂元素為下標的位置放為數組當前元素(也就是找到了下一個更大元素)，并繼續從棧頂往棧底比較，直到遇到數組當前元素＜數組以當前棧頂元素為下標的元素的情況，break跳出循環，并將數組當前元素下標放入棧頂。
//當遍歷完數組后，如果棧中還有元素，說明數組中以這些元素為下標的元素沒有找到下一個更大的值，將答案數組中以棧中元素為下標的位置置為0。
typedef struct ListNode LN;
?int* nextLargerNodes(struct ListNode* head, int* returnSize)
{
? ? int arr[10000] = {0};
? ? int stack[10000] = {0};
? ? int* ans = (int*)malloc(sizeof(LN)*10000);
? ? int num = 0;
? ? int count = 0;
? ? LN* pmove = head;
? ? while(pmove)//將鏈表元素存入數組
? ? {
? ? ? ? arr[num++] = pmove->val;
? ? ? ? pmove = pmove->next;
? ? }
? ? for(int i = 0;i<num;i++)//遍歷數組
? ? {
? ? ? ? if(count==0||arr[i]<arr[stack[count-1]])//如果棧中沒有元素或者數組當前元素＜數組以當前棧頂元素為下標的元素，入棧
? ? ? ? ? ? stack[count++] = i;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? while(count)//否則，從棧頂往棧底遍歷棧中的下標元素，直到遍歷到棧底或者數組當前元素＞數組以當前棧頂元素為下標的元素，跳出循環
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(arr[i]>arr[stack[count-1]])
? ? ? ? ? ? ? ? ? ? ans[stack[count-1]] = arr[i];
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? count--;
? ? ? ? ? ? }
? ? ? ? ? ? stack[count++] = i;//將當前數組元素下標放入棧頂
? ? ? ? }
? ? }
? ? for(int i = 0;i<count;i++)
? ? {
? ? ? ? ans[stack[i]] = 0;//如果棧中還有元素，說明數組中以棧中元素為下標的元素沒有找到下一個更大的值，將答案數組以棧中元素為下標的位置置為0。
? ? }
? ? *returnSize = num;
? ? return ans;
}
2.?116. 填充每個節點的下一個右側節點指針 - 力扣（LeetCode）
//思路：層序遍歷。將層序遍歷的結果存入數組中（存放的元素為struct Node* 的指針），因為是完美二叉樹，因此每一層的結點個數都滿足 2^x 。因此，只需要根據每層的節點數改變遍歷的次數。
typedef struct Node* QDataType;
?//隊列節點
typedef struct listnode
{
? ? QDataType val;
? ? struct listnode* next;
}LN;
//隊列頭尾指針
typedef struct queque
{
? ? LN* phead;
? ? LN* ptail;
? ? int size;
}QE;
?//隊列初始化
void QueInit(QE* qe)
{
? ? assert(qe);
? ? qe->phead = NULL;
? ? qe->ptail = NULL;
? ? qe->size = 0;
}
?//判斷隊列是否為空
bool QueEmpty(QE* qe)
{
? ? assert(qe);
? ? return qe->size == 0;
}
?//入列
void QuePush(QE* qe, QDataType x)
{
? ? assert(qe);
? ? LN* newnode = (LN*)malloc(sizeof(LN));
? ? if (newnode == NULL)
? ? {
? ? ? ? perror("malloc:");
? ? ? ? exit(-1);
? ? }
? ? newnode->next = NULL;
? ? newnode->val = x;
? ? if (qe->phead == NULL)
? ? {
? ? ? ? qe->phead = qe->ptail = newnode;
? ? }
? ? else
? ? {
? ? ? ? qe->ptail->next = newnode;
? ? ? ? qe->ptail = qe->ptail->next;
? ? }
? ? qe->size++;
}
//出列
void QuePop(QE* qe)
{
? ? assert(qe);
? ? assert(qe->phead != NULL);
? ? assert(qe->size > 0);
? ? LN* tmp = qe->phead->next;
? ? free(qe->phead);
? ? qe->phead = tmp;
? ? qe->size--;
}
?//獲取列頭元素
QDataType QueGetHead(QE* qe)
{
? ? assert(qe);
? ? assert(qe->phead != NULL);
? ? return qe->phead->val;
}
?struct Node* connect(struct Node* root)
{
? ? if(!root)
? ? ? ? return NULL;
? ? QDataType arr[10000] = {0};
? ? int count = 0;
? ? root->next = NULL;
? ? QE q;
? ? QueInit(&q);
? ? QuePush(&q,root);
? ? while(!QueEmpty(&q))//入列
? ? {
? ? ? ? QDataType tmp = QueGetHead(&q);
? ? ? ? arr[count++] = QueGetHead(&q);//將隊頭元素存入數組中
? ? ? ? QuePop(&q);
? ? ? ? if(tmp->left)//繼續層序遍歷
? ? ? ? ? ? QuePush(&q,tmp->left);
? ? ? ? if(tmp->right)
? ? ? ? ? ? QuePush(&q,tmp->right);
? ? }
? ? int i = 1;
? ? int flag = 1;
? ? while(i<count)//遍歷數組
? ? {
? ? ? ? int j = pow(2,flag);
? ? ? ? while(j-1)//選擇其中的2^flag次方個結點進行next操作
? ? ? ? {
? ? ? ? ? ? arr[i]->next = arr[i+1];
? ? ? ? ? ? i++;
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? arr[i++]->next = NULL;//每一層的最后一個結點的next為NULL
? ? ? ? flag++;
? ? }
? ? return root;
}
3.?412. Fizz Buzz - 力扣（LeetCode）
//思路：題目不難，主要考察對動態內存管理知識的理解能力。
char ** fizzBuzz(int n, int* returnSize)
{
? ? char** ans = (char**)malloc(sizeof(char*)*n);//申請一塊空間，存放指針
? ? for(int i = 0;i<n;i++)
? ? {
? ? ? ? ans[i] = (char*)malloc(sizeof(char)*9);//對這塊空間中的每個指針申請空間
? ? }
? ? for(int i = 1;i<=n;i++)
? ? {
? ? ? ? if(i%3==0&&i%5==0)
? ? ? ? ? ? strcpy(ans[i-1],"FizzBuzz");
? ? ? ? else if(i%3==0)
? ? ? ? ? ? strcpy(ans[i-1],"Fizz");
? ? ? ? else if(i%5==0)
? ? ? ? ? ? strcpy(ans[i-1],"Buzz");
? ? ? ? else
? ? ? ? ? ? sprintf(ans[i-1],"%d",i);
? ? }
? ? *returnSize = n;
? ? return ans;
}
