菜鸟刷题Day8

简介: 菜鸟刷题Day8

一.奇偶树:1609. 奇偶树 - 力扣(LeetCode)

描述

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

二叉树根节点所在层下标为 0 ,根的子节点所在层下标为 1 ,根的孙节点所在层下标为 2 ,依此类推。

偶数下标 层上的所有节点的值都是 奇 整数,从左到右按顺序 严格递增

奇数下标 层上的所有节点的值都是 偶 整数,从左到右按顺序 严格递减

给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false

示例 1:

输入:root = [1,10,4,3,null,7,9,12,8,6,null,null,2]

输出:true

解释:每一层的节点值分别是:

0 层:[1]

1 层:[10,4]

2 层:[3,7,9]

3 层:[12,8,6,2]

由于 0 层和 2 层上的节点值都是奇数且严格递增,而 1 层和 3 层上的节点值都是偶数且严格递减,因此这是一棵奇偶树。


解题思路

因为是对某一层的数进行判断,所以一次要拿到一层的数据,于是就可以很自然的想到要用层序遍历(根节点入队列,在根节点出队列的时候带入这个节点的左右孩子),但是也不能手搓一个队列,所以这里还是采取数组模拟队列。如果队列中存在元素就要循环,这个循环既是对队列中的元素进行判断,也是带入队列元素的左右孩子。

将一个数按位与上1,就可以判断这个数的奇偶性,但这样在不同层就要有不同的判断条件,所以我们可以直接多设置一个变量k用来判断,这个变量k在刚开始时是0(第0层是奇数,如果按位与1等等于0,那就说明不满足条件),此后可以用k=1-k来更新这个变量。

还有就是在判断是否严格递增或者递减的时候,为了避免在不同的层有不同的条件判断,可以设置一个flag=1(因为第0层是偶数层要递增),并通过flag= - flag来更新,在不同层只要将相邻的两个数乘上flag来判断.

bool isEvenOddTree(struct TreeNode* root)
{
    struct TreeNode* queue[100000];
    int front = -1;  int rear = -1; //控制队列的首尾
    queue[++rear] = root;           //放入根结点
    int k = 0;                      //判断奇偶性
    int flag = 1;                   // 判断单调性
    while(rear != front)            //队列中还有元素则循环继续
    {
        for(int i = front + 1; i <= rear; i++)
        {
            if((queue[i]->val & 1) == k)
                return false;
            //后续会更新front,所以不能用大于2来判断,只要大于front+1就肯定有两个元素
            if(i > front + 1 && flag * queue[i-1]->val >= flag * queue[i]->val)
                return false;
        }
      //  更新k和flag
        k = 1 - k;                 // 1 ~ 0互换
        flag = -flag;              // 1 ~ -1互换
        int tmp = rear;//后续要将这个赋值给front来更新front
        //带入左右孩子
        for(int i = front + 1; i <= tmp; i++)
        {
            if(queue[i]->left)     //存在则入列
                queue[++rear] = queue[i]->left;
            if(queue[i]->right)
                queue[++rear] = queue[i]->right;
        }
        front = tmp;  //即使更新front,可以看到我并没有出队,我只是控制下标来达到出队的效果
    }
    return true;
}

二.数组的相对排序:1122. 数组的相对排序 - 力扣(LeetCode)

描述

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

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

示例 1:

输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

输出:[2,2,2,1,4,3,3,9,6,7,19]


解题思路

设定一个新数组,将arr1数组中的元素作为新数组的下标统计arr1数组中各元素出现的次数,再用arr2数组中的元素作为新数组的下标,并将这个下标作为元素重新写到arr1数组中。这个思想我们在前面就已经用过好几次了,这种数组就被称为hash数组

这里还要处理一下在arr1数组中出现了,arr2数组中没有的.

int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
    int tmp[1001]={0};
    for(int i=0;i<arr1Size;i++)
    {
        //统计arr1数组中各元素出现的次数
        tmp[arr1[i]]+=1;
    }
    int j=0;
    for(int i=0;i<arr2Size;i++)
    {
    while(tmp[arr2[i]]>0)//如果这个下标不为零,说明这个下标就是arr1和arr2都有的元素
        {
            arr1[j]=arr2[i];
            j++;
            tmp[arr2[i]]--;
        }
    }
    //还要将arr2中没出现的元素按升序排好,直接暴力遍历
    for(int i=0;i<1001;i++)
    {
        while(tmp[i]>0)
        {
            arr1[j]=i;
            j++;
            tmp[i]--;
        }
    }
  *returnSize=arr1Size;
    return arr1;
}

三.最长和谐子序列594. 最长和谐子序列 - 力扣(LeetCode)

描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1:

输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:最长的和谐子序列是 [3,2,2,2,3]

解题思路

最开始我也是想着用hash数组统计次数后,返回相邻位置相减最大值。但是这题的测试用例中会有负数,所以这中办法跑不过,毕竟下标没有负数。

要找的是两者之间差值为1,并且要是最长的。所以首先将这个数组排序,这样会比较好找。排序以后使用双指针,一个指针begin指向数组的首元素,一个指针end指向首元素的下一个,如果begin与end代表的元素之间的差值是1,那么就移动end,否则就移动begin,因为在移动begin的情况下,就代表end与begin之间的元素差值一定不是1,而这个数组是一个有序数组,也就是说在移动begin的时候不用移动end,所以可以直接用end作为循环结束的条件。

int Cmp(const void*a,const void *b)
{
    return *(int*)a-*(int*)b;
}
int findLHS(int* nums, int numsSize)
{
  qsort(nums,numsSize,sizeof(int),Cmp);//使用qsort排序
    //排序完毕以后采用双指针计算长度
  int begin=0;
    int count=0;//用来计算长度
   for(int end=1;end<numsSize;end++)
   {
       if(nums[end]-nums[begin]>1)
           begin++;
       if(nums[end]-nums[begin]==1)
       {
           count=count>end-begin+1?count:end-begin+1;
       }
   }
    return count;
}

那么到这里菜鸟刷题专栏就结束了,如果你有心去统计题目个数就会发现总计只有31道题,而专栏介绍却说有32道。我想说,承诺在兑现之前都是一文不值的,别太相信别人的话。最近突然想起《第一序列》中的一句话:“不要让时代的悲哀成为你的悲哀。”不要看着大家都随便,你也随便。

人们总是高估短期努力带来的提升,却低估长期坚持带来的改变。今天是最后一天了,希望你还在坚持。这个专栏就和大家说再见啦,但是我们的故事还没结束……

相关文章
|
算法
菜鸟刷题Day1
菜鸟刷题Day1
|
算法 索引
菜鸟刷题Day5
菜鸟刷题Day5
|
存储 Java C++
菜鸟刷题Day2
菜鸟刷题Day2
|
算法
菜鸟刷题Day4
菜鸟刷题Day4
|
存储 C语言
菜鸟刷题Day6
菜鸟刷题Day6
|
存储 设计模式 缓存
阿里Java后端面经【记录牛客】(下)
阿里Java后端面经【记录牛客】(下)
261 0
阿里Java后端面经【记录牛客】(下)
|
前端开发 JavaScript
#yyds干货盘点# 前端歌谣的刷题之路-第一百五十九题-new
#yyds干货盘点# 前端歌谣的刷题之路-第一百五十九题-new
96 0
#yyds干货盘点# 前端歌谣的刷题之路-第一百五十九题-new