【每日刷题】Day49

2024-05-26 23:28
文章标签 每日 刷题 day49

本文主要是介绍【每日刷题】Day49,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【每日刷题】Day49

🥕个人主页:开敲🍉

🔥所属专栏:每日刷题🍍

🌼文章目录🌼

1. 110. 平衡二叉树 - 力扣(LeetCode)

2. 501. 二叉搜索树中的众数 - 力扣(LeetCode)

3. 637. 二叉树的层平均值 - 力扣(LeetCode)

1. 110. 平衡二叉树 - 力扣(LeetCode)

//思路:平衡二叉树:对于树中每个结点都满足 左、右子树深度差值不超过1。因此我们递归遍历树的每一个结点,判断每一个结点处是否满足平衡二叉树,只要有一个不满足直接return false。

int TreeHigh(struct TreeNode* root)

{

    if(root==NULL)

        return 0;

    int HighLeft = TreeHigh(root->left);

    int HighRight = TreeHigh(root->right);

    return 1+(HighLeft>HighRight?HighLeft:HighRight);

}

bool isBalanced(struct TreeNode* root)

{

    if(root==NULL)

        return true;

    int HighLeft = TreeHigh(root->left);

    int HighRight = TreeHigh(root->right);

    int tmp = abs(HighLeft-HighRight);

    if(tmp>1)

        return false;

    return isBalanced(root->left)&&isBalanced(root->right);

}

2. 501. 二叉搜索树中的众数 - 力扣(LeetCode)

//思路:哈希表。本题很容易想到使用哈希表存储每个数出现的次数,找出出现次数最多的数。但因为数中的值可能为负数,因此我们需要对哈希表的键进行调整。

void FindMode(struct TreeNode* root,int* arr)

{

    if(root==NULL)

        return;

    arr[root->val+100000]+=1;//将所有负数转变为正数

    FindMode(root->left,arr);

    FindMode(root->right,arr);

}

int* findMode(struct TreeNode* root, int* returnSize)

{

    int hash[200001] = {0};

    FindMode(root,hash);

    int max = 0;

    int* ans = (int*)malloc(sizeof(int)*10000);

    int size = 0;

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

    {

        max = max>hash[i]?max:hash[i];

    }

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

    {

        if(hash[i]==max)

        {

            ans[size++] = i-100000;//将原为负数的值更改回去

        }

    }

    *returnSize = size;

    return ans;

}

3. 637. 二叉树的层平均值 - 力扣(LeetCode)

//思路:使用一个数组存储二叉树每一层结点个数,随后对二叉树进行层序遍历,每次根据每层结点个数将结点的值进行累加,然后除去当前层的结点个数,从而算出每层的平均值,存储进答案数组中返回。注:本题思路需要先明白二叉树层序遍历的实现。

typedef struct TreeNode BT;

typedef struct TreeNode* 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;

}


 

//入列

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;

}


 

//判断队列是否为空

bool QueEmpty(QE* qe)

{

    assert(qe);

    return qe->size == 0;

}


 

//层序遍历二叉树计算平均值(队列实现层序遍历)

void SequenceTraverse(BT* root,int* arr,int size,double* ans,int* count)

{

    QE q;

    QueInit(&q);

    if (root)

        QuePush(&q, root);

    int i = 0;

    while (i<size)

    {

        double tmp = 0;

        int n = arr[i];//记录当前层的节点数

        while(n)

        {

            QDataType front = QueGetHead(&q);//获取队头元素

            QuePop(&q);//将队头元素出列

            if(front)

                tmp+=front->val;//累加

            if(front)

            {

                QuePush(&q, front->left);//继续将当前结点的left和right结点入队列

                QuePush(&q, front->right);

                n--;

            }

        }

        tmp/=arr[i];//计算平均值

        ans[(*count)++] = tmp;

        i++;

    }

}

//求二叉树第K层结点个数

int BinaryTreeKSize(BT* root,int k)

{

    if (root == NULL)

        return 0;

    if (k == 0)

        return 1;

    return BinaryTreeKSize(root->left, k - 1) + BinaryTreeKSize(root->right, k - 1);

}

double* averageOfLevels(struct TreeNode* root, int* returnSize)

{

    int ksize[10000] = {0};

    int size = 0;

    do

    {

        int ret = BinaryTreeKSize(root,size);

        ksize[size++] = ret;

    }while(ksize[size-1]);//将二叉树每层节点数存储起来

    double* ans = (double*)malloc(sizeof(double)*10000);

    int count = 0;

    SequenceTraverse(root,ksize,size,ans,&count);

    *returnSize = count-1;

    return ans;

}

这篇关于【每日刷题】Day49的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1005878

相关文章

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8