LeetCode 3392、LCR106、3447题解

今天的每日一题比较简单，暴力都只需要很少的代码就能解决，我来说一下我的做题思路吧。

示例

输入：nums = [1,2,1,4,1]输出：1解释：只有子数组 [1,4,1]包含 3 个元素且第一个和第三个数字之和是中间数字的一半。number.

首先根据题目我们能知道子数组的长度为3，也就是滑动窗口，窗口的大小为3，所以我们设置l为0，向右移动，而r则等于l+2，那么中间的值的下标便为l+1。现在我们知道了子数组的滑动可以通过一次遍历完成，我们现在就要去记录完成条件的子数组的数量了，首先我们知道这是一个整数数组，所以当我们的nums[l+1]为1、3、5、7这些奇数的时候，除以2一定无法等于nums[l]+nums[l+2],所以我们只需要限制两个条件即可对数量进行++

代码如下

class Solution {public int countSubarrays(int[] nums) {int n = nums.length;int ans = 0;for(int l=0,r=2;r<n;l++,r++){if(nums[l]+nums[r]==nums[l+1]/2&&nums[l+1]%2==0) ans++;}return ans;}
}

判断是否为二分图最基本的做法就是染色+bfs，以下举几个基本的示例：

graph = [[1,3],   // 0号节点连着1、3[0,2],   // 1号节点连着0、2[1,3],   // 2号节点连着1、3[0,2]    // 3号节点连着0、2
]

0 --- 1
|     |
3 --- 2

思路很简单，就是通过定义颜色然后bfs检索判断所有的组是否存在相交，如果相交了就说明组内有交集无法得到二分图，返回false

先定义一个数组和栈，数组用来标记点是否已经访问过了，且其颜色用来区别组，而栈则是用来遍历节点用的，访问节点，推出节点，新增节点，而颜色的定义我们通过1代表红色，-1代表蓝色，0代表没有访问来进行区分

拿上述示例举个例子，当graph数组为示例所示，我们先将n个节点通过Arrays.fill(color,0)将节点的颜色都进行初始化一遍。

重点：对于样例可能存在多个连通分量

graph = [[1],     // 0连着1[0],     // 1连着0[3],     // 2连着3[2],     // 3连着2[],      // 4孤立节点[6],     // 5连着6[5]      // 6连着5
]

画出来大概是这样的

0 - 1       2 - 3      4       5 - 6

所以我们需要一个for循环去遍历，防止漏掉通过栈获取到的节点，当进入连通分量的for循环后再进栈queue.offer(i),并给i初始化一个颜色，我就使用红色了，然后再在while(!=queue.isEmpty())中实行出栈进栈的操作，防止当前连通分量的节点没有全部遍历染色完，而染色也有相应的规则，找到对应的相同组中出现了连接，那么二分图就不成立了。

规则如下：
如果对应节点的graph数组中的节点没有染色(即为0)，则染色成相反的颜色(即-color[ans],ans是queue.poll()后得到)
如果对应节点的graph数组中的节点和当前节点的颜色出现相同的情况，即视为不是二分图(出现了内连接)。

class Solution {public boolean isBipartite(int[][] graph) {int n = graph.length;int[] color = new int[n];Arrays.fill(color,0);//初始化//0未访问 1为红色 -1为蓝色Queue<Integer> queue = new LinkedList<>();//可能存在多个连通分量for(int i=0;i<n;i++){if(color[i]!=0) continue;//初始化红色queue.offer(i);color[i] = 1;while(!queue.isEmpty()){int ans = queue.poll();for(int num:graph[ans]){if(color[num]==color[ans]) return false;if(color[num]==0){color[num] = -color[ans];queue.offer(num);}}}}return true;}
}

这题我的思路比较简单，也是铁铁的超时了。用map去掉elements中重复的元素并记录下其最小的下标，然后通过o(n*n)的时间复杂度进行遍历，遍历到的返回下标并加入到list中，没有遍历到的就在list中加入-1。

class Solution {public int[] assignElements(int[] groups, int[] elements) {int n = groups.length;int m = elements.length;HashMap<Integer,Integer> map = new HashMap<>();map.put(0,elements[0]);//初始化for(int i=1;i<m;i++){if(map.getOrDefault(i,0)==0&&elements[i]!=elements[0]) map.put(i,elements[i]);// System.out.println(map.getOrDefault(elements[i],0));}List<Integer> loser = new ArrayList<>();for(int i=0;i<n;i++){boolean found = false;for(Map.Entry<Integer, Integer> entry : map.entrySet()){// System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());if(groups[i]%entry.getValue()==0) {loser.add(entry.getKey());found = true;break;}}if (!found) { // 如果内层循环结束后标志变量为 false，说明没有找到满足条件的元素loser.add(-1);}}return loser.stream().mapToInt(Integer::intValue).toArray();}
}

想要优化却无从下手的无力感，气死我啦，只能委屈的再去看题解并理解答者的做题方法。

看了下题解后终于是理解了双elements的优化应该是怎么来的了，这题我们需要逆向思维，且遍历一遍groups确立最大的边界值mx，然后再遍历elements数组（找到最小下标的整余数，并打上了标记防止二次更新相同位置的下标）
举个例子就能明白
比如示例groups = [8,4,3,2,4], elements = [4,2]
我们遍历elements数组当i=0时，对于4、8这两个值的对应的最小下标为0，而当i=1时，对于2这个值的对应最小下标为1，且由于之前已经使得4、8两个已经有了对应的值，那么就不会再去更新，这也是为什么我们要一开始使用Arrays.fill(target,-1)的原因

class Solution {public int[] assignElements(int[] groups, int[] elements) {int mx = 0;for (int x : groups) {mx = Math.max(mx, x);}int[] target = new int[mx + 1];Arrays.fill(target, -1);for (int i = 0; i < elements.length; i++) {int x = elements[i];if (x > mx || target[x] >= 0) { // x 及其倍数一定已被标记，跳过continue;}for (int y = x; y <= mx; y += x) { // 枚举 x 的倍数 yif (target[y] < 0) { // 没有标记过target[y] = i; // 标记 y 可以被 x 整除（记录 x 的下标）}}}// 回答询问for (int i = 0; i < groups.length; i++) {groups[i] = target[groups[i]]; // 原地修改}return groups;}
}

之后我们只需要遍历并且更新groups数组即可。