【每日刷题】Day82

【每日刷题】Day82

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. LCR 044. 在每个树行中找最大值 - 力扣（LeetCode）

2. 面试题 16.07. 最大数值 - 力扣（LeetCode）

3. LCR 133. 位 1 的个数 - 力扣（LeetCode）

1. LCR 044. 在每个树行中找最大值 - 力扣（LeetCode）

//思路：数组+深度优先遍历。利用一个变量来表示某一层，用当前root->val与数组中以当前层为下标的值进行比较，存储较大的值。因此我们需要将数组中的值全部初始化为INT_MIN。

void _largestValues(struct TreeNode* root,int* ans,int flag)

{

    if(!root)

        return;

//存储较大值

    if(root->val>ans[flag])

        ans[flag] = root->val;

    _largestValues(root->left,ans,flag+1);

    _largestValues(root->right,ans,flag+1);

}

//求树的最大深度，作为返回数组的长度

int TreeHigh(struct TreeNode* root)

{

    if(!root)

        return 0;

    int left = TreeHigh(root->left);

    int right = TreeHigh(root->right);

    return 1+(left>right?left:right);

}

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

{

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

//使用循环赋值，简单粗暴(memset赋值范围为unsigned char)

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

    {

        ans[i] = -2147483648;

    }

    int flag = 0;

    _largestValues(root,ans,flag);

    *returnSize = TreeHigh(root);

    return ans;

}

2. 面试题 16.07. 最大数值 - 力扣（LeetCode）

//思路：核心在于 (1+k)*a-k*b 这个公式，当k =0 时，return a；当k = -1时， return b。现在我们来处理k

//我们如何让k = 0时 return a就是没问题的呢？重点在于二进制的除符号位外的最高位。

//试想一下，如果a>b，那么a-b一定是正数，则a-b的结果的最高位一定是0

//如果a<b，那么a-b一定是负数，则a-b的结果的除符号位外的最高位一定是1，且符号位一定是1

//综上，我们可以定义k = a-b，这里为了避免int类型的溢出，我们需要定义 long k = (long)a-(long)b。随后将k >> 62，以获取除符号位外的最高位。这样，如果a>b，则k = 0，return a；如果a<b，则k = -1，return b。

//想出这个方法的简直是个天才

int maximum(int a, int b)

{

    long flag = (long)a-(long)b;

    int k = (int)(flag>>62);

    return (1+k)*a-k*b;

}

3. LCR 133. 位 1 的个数 - 力扣（LeetCode）

//思路：位运算。

int hammingWeight(uint32_t n)

{

    long flag = 1;

    int ans = 0;

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

    {

        if(flag&n)

            ans++;

        flag<<=1;

    }

    return ans;

}