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