一.奇偶树：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道。我想说，承诺在兑现之前都是一文不值的，别太相信别人的话。最近突然想起《第一序列》中的一句话：“不要让时代的悲哀成为你的悲哀。”不要看着大家都随便，你也随便。
人们总是高估短期努力带来的提升，却低估长期坚持带来的改变。今天是最后一天了，希望你还在坚持。这个专栏就和大家说再见啦，但是我们的故事还没结束……
