【LeetCode】1609. 奇偶树、1122. 数组的相对排序

这篇具有很好参考价值的文章主要介绍了【LeetCode】1609. 奇偶树、1122. 数组的相对排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 作者:小卢 

专栏:《Leetcode》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

【LeetCode】1609. 奇偶树、1122. 数组的相对排序


 1609. 奇偶树

1609. 奇偶树 

题目描述:

如果一棵二叉树满足下述几个条件,则可以称为 奇偶树 :

二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。
偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减
给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false 。

示例:

【LeetCode】1609. 奇偶树、1122. 数组的相对排序

思路:

奇偶树:就当层数level为奇数,节点递减,当层数level为偶数,节点递增

 很明显本题需要用到层序遍历。

判断一棵二叉树是否为奇偶树,需要考虑两个条件,一是节点值的奇偶性,二是节点值的单调性,这两个条件都由层下标的奇偶性决定。因此,需要维护搜索到的层下标,以及对于每一层搜索都需要维护上一个节点值。

如果当前层下标是偶数,则要求当前层的所有节点的值都是奇数,且节点值从左到右严格递增。如果遇到节点值是偶数,或者当前节点值小于等于上一个节点值,则二叉树一定不是奇偶树。

如果当前层下标是奇数,则要求当前层的所有节点的值都是偶数,且节点值从左到右严格递减。如果遇到节点值是奇数,或者当前节点值大于等于上一个节点值,则二叉树一定不是奇偶树。

如果二叉树的所有节点都满足奇偶树的条件,则二叉树是奇偶树。

更详细的可以看看注释,我写很详细!!!

代码:

bool isEvenOddTree(struct TreeNode* root) {
    //Queue为队列
    //level为层数
    //head为二叉树的遍历位置
    //tail为队列的遍历位置
    struct TreeNode* Queue[100010];
    int level = 0;
    int head = 0;
    int tail = 0;
    Queue[head++] = root;
    while (tail < head)//当队列的位置tail大于二叉树的位置head遍历完成
    {
        //front为每次出队列的元素
        //size为队列的有效长度
        int size = head - tail;
        //prev为上一个节点的val
        //INT_MAX为int类型的最大值,INT_MIN为int类型的最小值
        //奇偶树:当level为奇数,节点是递减的,所以第一个节点要大于第二个节点
        //而在层序遍历中,最左边的节点一定是小于INT_MAX
        //同理可得,当leve为偶数,最左边的节点大于INT_MIN
        int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
        for (int i = 0; i < size; i++)
        {
            struct TreeNode* front = Queue[tail++];
            if (level % 2 == (front->val) % 2)//level为奇数,节点为偶数,level为偶数,节点为奇数
                return false;
            if ((level % 2 == 0 && prev >= front->val) || (level % 2 == 1 && prev <= front->val))
                return false;//当level为奇数,节点是递减的,当level为偶数,节点是递增的
            prev = front->val;
            if (front->left)
                Queue[head++] = front->left;
            if (front->right)
                Queue[head++] = front->right;
        }
        level++;
    }
    return true;
}//LeetCode1609

1122. 数组的相对排序

1122. 数组的相对排序

题目描述:

给你两个数组,arr1 和 arr2,arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例:

【LeetCode】1609. 奇偶树、1122. 数组的相对排序

 代码:文章来源地址https://www.toymoban.com/news/detail-408551.html

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    int upper = 0;
    for (int i = 0; i < arr1Size; i++) {
        upper = fmax(upper, arr1[i]);
    }
    int frequency[upper + 1];
    memset(frequency, 0, sizeof(frequency));
    for (int i = 0; i < arr1Size; i++) {
        frequency[arr1[i]]++;
    }
    int* ans = malloc(sizeof(int) * arr1Size);
    *returnSize = 0;
    for (int i = 0; i < arr2Size; i++) {
        int x = arr2[i];
        for (int j = 0; j < frequency[x]; j++) {
            ans[(*returnSize)++] = x;
        }
        frequency[x] = 0;
    }
    for (int x = 0; x <= upper; x++) {
        for (int i = 0; i < frequency[x]; i++) {
            ans[(*returnSize)++] = x;
        }
    }
    return ans;
}

到了这里,关于【LeetCode】1609. 奇偶树、1122. 数组的相对排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 33题:搜索旋转排序数组

    目录 题目 思路 代码 暴力解法 分方向法 二分法 整数数组  nums  按升序排列,数组中的值  互不相同  。 在传递给函数之前, nums  在预先未知的某个下标  k ( 0 = k nums.length )上进行了  旋转 ,使数组变为  [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (下标 

    2024年02月13日
    浏览(43)
  • LeetCode - #81 搜索旋转排序数组 II

    我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我们已经更新了 80 期,我们会保持更新时间和进度( 周一、周三、周五早上 9:00 发布 ),每期的内容不多,

    2024年02月10日
    浏览(39)
  • 【LeetCode刷题(数组and排序)】:存在重复元素

    给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 示例 1: 输入:nums = [1,2,3,1] 输出:true 示例 2: 输入:nums = [1,2,3,4] 输出:false 示例 3: 输入:nums = [1,1,1,3,3,4,3,2,4,2] 输出:true 在对数字从小到大排序之后,数

    2024年02月07日
    浏览(50)
  • LeetCode 26.删除排序数组中的重复项

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月03日
    浏览(45)
  • 快排&超详细,Leetcode排序数组题目带你升华掌握

    大家好,这里是Dark FalmeMater。 这篇文章我将超级仔细地讲解快速排序,快排之所以叫快排,到底有多快,为什么这么快,还有快速排序的优化和改进,通过这篇文章你一定会对快排有进一步的掌握。 快排的历史及介绍 快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是:通

    2024年02月08日
    浏览(52)
  • 算法leetcode|81. 搜索旋转排序数组 II(rust重拳出击)

    已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。 在传递给函数之前, nums 在预先未知的某个下标 k ( 0 = k nums.length )上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,

    2024年02月07日
    浏览(44)
  • python练习 | 奇偶排序

    题目名称: 奇偶排序 时间限制: 1000ms 内存限制: 256M 题目描述: 给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。(测试用例仅做参考,我们会根据代码质量进行评分) 输入描述: 第一行输入整数n。(1=n=1000)表示数组大小 第二行输入n个整数a

    2024年02月13日
    浏览(41)
  • (排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

    难度:中等 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 提示 : 0 nums.length = 100 说明: 输出结果可能非常大,所以你需要返回一个字符串而不

    2024年02月10日
    浏览(49)
  • (排序) 剑指 Offer 51. 数组中的逆序对 ——【Leetcode每日一题】

    难度:困难 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制 : 0 = 数组长度 = 50000 💡思路:归并排序 预备知识 「 归并排序 」是用 分治 思想,分

    2024年02月11日
    浏览(45)
  • LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

    在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums ,和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target ,返回 [-1, -1] 。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此

    2024年02月02日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包