力扣209周周赛题解记录（上）

题目思路与算法代码实现复杂度分析

题目

特殊数组的特征值 奇偶树

思路与算法

第一题单纯的暴力就行，应该是可以用二分之类的改善复杂度，没必要赘述，直接上暴力遍历，带注释。第二题典型的按层遍历的BFS，使用队列数据结构实现，自己构建一个带level标签的数据类型比较方便。

代码实现

特殊数组的特征值 class Solution { public int specialArray(int[] nums) { int len = nums.length; // 遍历，特征值最大为len for (int i = 0; i <= len; i++) { // 清零计数 int cnt = 0; // 判断数组比当前i大的值有几个，直到找到那个符合条件的，则为特征值 for (int num : nums) { if (num >= i) { cnt++; } } if (cnt == i) { return i; } } return -1; } } 奇偶树 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // 自定义工具类存储节点和当前level class Mypair{ TreeNode node; int index; Mypair(TreeNode node,int index){ this.node = node; this.index = index; } } public boolean isEvenOddTree(TreeNode root) { // 新建队列将其level也传入 Queue<Mypair> queue = new ArrayDeque<>(); // root的level为0 queue.add(new Mypair(root,0)); int pre = Integer.MIN_VALUE; int cur = -1; while (!queue.isEmpty()) { // 获取队首的节点和索引进行判断 Mypair tmp = queue.poll(); TreeNode tmpNode = tmp.node; int tmpIndex = tmp.index; // 一定记得处理这个特殊情况 if (tmpNode == null) { continue; } // 层之间的转移情况，根据层的奇偶性来初始化pre if (cur != tmpIndex) { // 偶数层和奇数层因为排序的要求，更新并设置不同的pre if (tmpIndex % 2 == 0) { pre = Integer.MIN_VALUE; } else { pre = Integer.MAX_VALUE; } cur = tmpIndex; } // 如果当前层数为偶数层 if (cur % 2 == 0) { // 偶数层若出现偶数或不符合单调递增，则返回false if (tmpNode.val % 2 == 0 || tmpNode.val <= pre) { return false; } // 如果当前层数为奇数层 } else if (cur % 2 != 0) { // 奇数层若出现奇数或不符合单调递减，则返回false if (tmpNode.val % 2 != 0 || tmpNode.val >= pre) { return false; } } // 一轮结束将已遍历的节点设为pre pre = tmpNode.val; // 剩下的BFS即可 queue.add(new Mypair(tmpNode.left, tmpIndex+1)); queue.add(new Mypair(tmpNode.right, tmpIndex+1)); } return true; } }

复杂度分析

第一题复杂度为O（N²），树的复杂度不做讨论。