著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
[1, 104] 范围内-231 <= Node.val <= 231 - 1bfs
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (null == root){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
double sum = 0;
int i=-1;
while (++i < size){
TreeNode node = queue.poll();
sum += (double) node.val;
if (node.left!=null){
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
}
res.add(sum/size);
}
return res;
}
}给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
两个网格块属于同一 连通分量 需满足下述全部条件：
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。
示例 1：
输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3 输出：[[3,3],[3,2]]
示例 2：
输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3 输出：[[1,3,3],[2,3,3]]
示例 3：
输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2 输出：[[2,2,2],[2,1,2],[2,2,2]]
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j], color <= 10000 <= row < m0 <= col < n
海星，理解了题意的话就比较简单了（补充更新）
给个图吧，题目写得太拗口了
给出如图的矩阵grid[][]，给出了对应坐标row = 3，col = 4，和一个color随便是什么，并不重要
要求把row, col位置连通分量的边界的值修改为color值
题目中并给出了连通分量的定义，即四个方向中任意一个方向上相邻，且值相等的区块，那么自然的边界的定义我们就能理解出来，如果上下左右4个方向上有任意一个和连通分量的值不同的话，那么就可以说明这个格子是边框，且如果这个连通分量格子本身是矩阵的边界的话，那么他也是边框
那么按照题意，这个图上的应该要修改的位置就是如下
理解了这层的话就好办了，直接上DFS
class Solution {
int[][] grid;
int m;
int n;
int connectedComponentValue;
int borderColor;
boolean[][] visited;
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid = grid;
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
connectedComponentValue = grid[row][col];
borderColor = color;
dfs(row,col);
return this.grid;
}
public void dfs(int row, int col){
boolean borderFlag = false;
visited[row][col] = true;
for (int[] ints : dir) {
int x = row + ints[0];
int y = col + ints[1];
if (isOutOfBoundary(x,y)){
borderFlag = true;
continue;
}
if (visited[x][y]){
continue;
}
if (grid[x][y] != connectedComponentValue){
borderFlag = true;
continue;
}
dfs(x,y);
}
if (borderFlag){
grid[row][col] = borderColor;
}
}
// boolean isEdge(int row, int col){
// return row == 0 || col == 0 || row == m-1 || col==n-1;
// }
boolean isOutOfBoundary(int row, int col){
return row < 0 || col < 0 || row >= m || col >= n;
}
}补充更新个小细节
isOutOfBoundary判断需要在visited[x][y]之前，为了防止发生越界错误grid[x][y] != connectedComponentValue判断需要在visited[x][y]之后，深搜会先改变染色掉之前访问到的格子，如果不先判断visited[x][y]的话会导致类似缩圈的效果，把整个连通区域全都染色给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
提示：
1000 。[0, 104] 之间。深搜
遍历树并记录更新最大深度
class Solution {
int deep = 0;
public int maxDepth(Node root) {
dfs(root,0);
return deep;
}
public void dfs(Node node,int current){
if (null == node){
return ;
}
current++;
deep = Math.max(deep,current);
for (Node child : node.children){
dfs(child,current);
}
}
}
广搜也可以，按层遍历记录最终的层数，代码比较简单不做赘述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
深搜模板直接套用
dfs()方法返回当前节点下的最大深度class Solution {
public int maxDepth(TreeNode root) {
if (root==null){
return 0;
}
return dfs(root,0);
}
public int dfs(TreeNode node, int deep){
if (node==null){
return deep;
}
deep++;
int left = dfs(node.left,deep);
int right = dfs(node.right,deep);
return Math.max(left,right);
}
}你正在参与祖玛游戏的一个变种。
在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。
你的目标是 清空 桌面上所有的球。每一回合：
给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。
示例 1：
输入：board = "WRRBBW", hand = "RB" 输出：-1 解释：无法移除桌面上的所有球。可以得到的最好局面是： - 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW - 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW 桌面上还剩着球，没有其他球可以插入。
示例 2：
输入：board = "WWRRBBWW", hand = "WRBRW" 输出：2 解释：要想清空桌面上的球，可以按下述步骤： - 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW - 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty 只需从手中出 2 个球就可以清空桌面。
示例 3：
输入：board = "G", hand = "GGGGG" 输出：2 解释：要想清空桌面上的球，可以按下述步骤： - 插入一个 'G' ，使桌面变为 GG 。 - 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty 只需从手中出 2 个球就可以清空桌面。
示例 4：
输入：board = "RBYYBBRRB", hand = "YRBGB" 输出：3 解释：要想清空桌面上的球，可以按下述步骤： - 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B - 插入一个 'B' ，使桌面变为 BB 。 - 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty 只需从手中出 3 个球就可以清空桌面。
提示：
1 <= board.length <= 161 <= hand.length <= 5board 和 hand 由字符 'R'、'Y'、'B'、'G' 和 'W' 组成深度优先搜索方法，board 结尾借个空格好处理点
上班摸鱼，凑合摸了一个小时多，水平有限
深度优先搜索，
删除连续相同颜色的，我在结尾添加了一个空格，代码稍微好写点具体参见reductionChars方法，不过这个还是写的不太完美，需要递归处理，应该有不用递归的写法的，回头再尝试
具体还是看代码吧，有一些注解，应该能看看吧
class Solution {
HashSet<String> visited = new HashSet<>();
int min = 100;
public int findMinStep(String board, String hand) {
//借个空结尾代码好处理点
board = board+" ";
boolean[] handUsed = new boolean[hand.length()];
char[] boardChars = board.toCharArray();
dfs(boardChars,hand,handUsed);
//如果是100表示不能全消除
return min==100?-1:min;
}
public void dfs(char[] chars, String hand , boolean[] handUsed){
if (chars.length==1){
//统计用了几个
int usedCount = 0;
for (boolean used : handUsed) {
if (used){
usedCount++;
}
}
min = Math.min(min,usedCount);
return ;
}
//剪枝已经处理过的情况
if (visited.contains(new String(chars))){
return ;
}
//记录下当前情况已经处理过
visited.add(new String(chars));
//从handUsed所有在handUsed中没有标记的已用过的位置中取一个字符
for (int idx = 0; idx < handUsed.length; idx++) {
if (handUsed[idx]){
continue;
}
//标记已使用
handUsed[idx] = true;
//构造所有可能的组合情况
List<char[]> list = insertChar(chars,hand.charAt(idx));
for (char[] charArr : list) {
//继续递归
dfs(reductionChars(charArr),hand,handUsed);
}
//回溯标记未使用
handUsed[idx] = false;
}
}
/**
* 往`char[] chars` 数组中所有能插入的位置插入一个新的字符`c`
* 如果原来的被 插入位置和当前插入字符相同，只插入到后面一个位置
* @param chars
* @param c
* @return
*/
public List<char[]> insertChar(char[] chars, char c){
List<char[]> list = new ArrayList<>();
int idx = -1;
while (++idx < chars.length){
while (chars[idx]==c){
idx++;
}
char[] newChars = new char[chars.length+1];
System.arraycopy(chars,0,newChars,0,idx);
System.arraycopy(chars,idx,newChars,idx+1,chars.length-idx);
newChars[idx] = c;
list.add(newChars);
}
return list;
}
/**
* 删除字符串数组中连续出现次数大于等于3的区段内容
* @param chars
* @return
*/
public char[] reductionChars(char[] chars){
//记录下当前的长度
int length = chars.length;
int idx = 0;
char lastChar = chars[0];
int lastCharCount = 1;
while (++idx < chars.length){
if (chars[idx] == lastChar){
lastCharCount++;
}else{
//当前字符和前一个不同
if (lastCharCount>=3){
//从当前位置往前删除掉lastCharCount个
char[] newChars = new char[chars.length-lastCharCount];
System.arraycopy(chars,0,newChars,0,idx-lastCharCount);
System.arraycopy(chars,idx,newChars,idx-lastCharCount,chars.length-idx);
chars = newChars;
idx -= lastCharCount;
}
lastChar = chars[idx];
lastCharCount = 1;
}
}
//如果没有能处理删除掉的字符则直接返回
//如果长度发生了变化，尝试再处理一次，防止 WWRRRWW 变成了 WWWW后还要再处理一次的情况
return length == chars.length?chars:reductionChars(chars);
}
}请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
Java层序遍历【联动 1028. 从先序遍历还原二叉树】
就我们在力扣上做二叉树相关的题目的时候，例子说明中常用到的[1,2,3,null,null,4,5]这种写法，
两边方括号可以直接省略，
序列化
Queue反序列化
Queue保存上一层的节点内容Queue中需要拼接上去的上层节点的时候需要先从Queue中找到最先的那个不是空节点的节点中序遍历+前序遍历 或者中序遍历+后序遍历这样的处理办法，但是序列化获得的字符串相应的应该会变大public class Codec {
private String NULL = "N";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null){
return "";
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
StringBuffer sb = new StringBuffer();
while (!queue.isEmpty()){
TreeNode node = queue.poll();
sb.append(node == null?NULL:node.val).append(",");
if (node != null){
queue.offer(node.left);
}
if (node != null){
queue.offer(node.right);
}
}
sb.delete(sb.length()-1,sb.length());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length()==0){
return null;
}
String[] arr = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int idx = 0;
while (++idx < arr.length){
while (!queue.isEmpty() && queue.peek()==null){
queue.poll();
}
TreeNode curr = queue.poll();
TreeNode left = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
queue.offer(left);
curr.left = left;
if (idx+1 < arr.length){
idx++;
TreeNode right = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
curr.right = right;
queue.offer(right);
}
}
return root;
}
}给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s 由小写英文字母以及括号 '(' 和 ')' 组成s 中至多含 20 个括号类似广度优先搜索的处理办法、JAVA（详细注释）
括号字符串匹配问题我们常用的一个方法，遇到‘（’加1，遇到‘）’减1，结果为0的时候能表示形成完美匹配闭合。
这个问题也可以类比的想象为出入栈问题，‘（’入栈，‘）’出栈
另外，括号运算也可以类比的换算为其他结构，比如“树”
这是一个非常有意思的话题，不过题归正传，回到我们这题上
自己搞个字符串分析下看看，第二行标记的对应的映射关系，第三行统计了求和的值
( ( ) ( ) ) ) ) ( ) ) ( ( ( )
1 1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 -1
1 2 1 2 1 0 -1
当我们遇到这个和为-1的时候，很明显的说明了( ( ) ( ) ) )这段中有多余的)了，那么我们就把这段中的多余的)删掉一个再继续处理，可以得到如下两段，其中有一种连续的) )的情况删除任何一个结果都是一样的，这个可以再优化一下。
( ( ) ( ) )
( ( ( ) ) )
取第一种情况继续分析，那么字符串就变成了
( ( ) ( ) ) ) ( ) ) ( ( ( )
1 1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1
1 2 1 2 1 0 -1
再次遇到了-1继续同样的操作，在所有的结果中我们再取其中一种，以下省略数步，得到其中一个如下结果
( ( ) ( ) ) ( ) ( ( ( )
1 2 1 2 1 0 1 0 1 2 3 2
最终的结果为2，这是另外一种情况，对应的我们应该往前删除两个(，但是前面的(很多，我们应该删除哪两个呢？
显然这个不能随意删除任意的(了，而是只能删除最后出现结果为0往后的位置中的(，但是这里面也有很多个(，又要删除哪两个呢？
最直观的办法当然是枚举所有的可能性，但是额外再写个枚举组合的算法好像有点麻烦，那么我们不如每个位置的(都删除一下，生成对应个数的字符串，然后再次处理整个逻辑，直到最后多余的(都处理掉的情况。
当然这里也直观的可以看到了重复( (的时候其实删除任意一个都是一样的，这个也许可以再优化一点点。
那么整个逻辑都清楚了，下面看代码，已经加了一点点额外的剪枝优化，
maxSize记录了已经得到的结果的最长长度，如果新的字符串比这个短就不用再处理了history记录了已经处理过的字符串的哈希表，如果已经处理过了就不用再处理这个了res结果先存入这个哈希表中，直接去重，防止有重复的结果被统计代码
class Solution {
HashSet<String> history = new HashSet<>();
HashSet<String> res = new HashSet<>();
public List<String> removeInvalidParentheses(String s) {
Queue<String> queue = new LinkedList<>();
//加入一个队列待处理
queue.offer(s);
//maxSize 记录下当前得到的符合预期的结果中最长的结果的长度
int maxSize = 0;
while (!queue.isEmpty()){
String currentStr = queue.poll();
if (currentStr.length()<maxSize){
//如果这个字符串的长度已经小于可行结果中的最大长度，那么说明再处理之后得到的结果也不是最少删减个数能得到的
continue;
}
//下标标记
int idx = -1;
//遇到"("加1，遇到")"减1 遍历到idx位置的时候得到的结果
int total = 0;
//最有一个total等于0的时候的位置，后面有多余的"("的时候要用到
int lastZero = -1;
//判断是否遇到了total=-1的情况，其实也可以在下面修改flag = false;的地方用跳出外面一层循环的写法
boolean flag = true;
while (++idx < currentStr.length() && flag){
if (currentStr.charAt(idx) == '('){
//遇到'('加1
total++;
}
if (currentStr.charAt(idx) == ')'){
////遇到'('减1，其他都不用管
total--;
}
if (total==0){
//等于0的时候记录下最后0出现的位置
lastZero = idx;
}
//当到达某个下标的时候total=-1了，说明')'多了一个，需要在前面的所有')'中删除掉一个
if (total==-1){
//标记遇到-1的情况了
flag = false;
for (int i = 0; i <= idx; i++) {
//从头开始找')'
if (currentStr.charAt(i)==')'){
//删除掉指定位置的')'，生成新字符串
String tmpStr = strDeleteIndex(currentStr,i);
//如果没有处理过这种字符串的话，把他加入到queue、并标记为已经处理过这种的
if (!history.contains(tmpStr)){
history.add(tmpStr);
queue.add(tmpStr);
}
}
}
}
}
//如果没有遇到total=-1的情况，说明这里已经遍历到字符串的结尾了
if (flag){
//最终位置结果如果是大于0的，说明前面的lastZero位置到结束位置之间有多余的'('
if (total > 0){
//需要往前遍历找到最后一个0的位置lastZero从里面删除total个"("左括号，但是n个'('里面选total个'（'不是太好处理，需要组合不同情况
//那么我们就换一个简单点的办法，每个'('都删除一下，生成一个字符串，并重新执行上面的之前的逻辑，即把删除了一个'('的字符串
//重新加进queue再处理一遍，每次处理一个'('，直到最终处理掉了所有多余的'('
int i = lastZero;
while (++i < currentStr.length()){
if (currentStr.charAt(i) == '('){
//和上面处理')'一样，删除当前位置的'('，并加入到queue再次处理
String tmpStr = strDeleteIndex(currentStr,i);
if (!history.contains(tmpStr)){
history.add(tmpStr);
queue.add(tmpStr);
}
}
}
}else if (total == 0 && currentStr.length() >= maxSize){
//正好能闭合的添加进结果集，
//另外再判断更新maxSize，如果是长度比已有结果短的字符串就不用处理了
maxSize = currentStr.length();
res.add(currentStr);
}
}
}
List<String> l = new ArrayList<>();
int finalMaxSize = maxSize;
res.forEach(str->{
if (str.length()== finalMaxSize){
//再判断一遍长度，这边我也不确定是不是需要，所以保险起见还是写下吧
l.add(str);
}
});
return l;
}
/**
* 删除字符串指定下标位置的字符的封装方法，返回一个新的删除了指定位置的字符的字符串
* 由于调用的地方已经严格控制的idx不会越界，所以idx的越界问题就没有做判断处理
* @param str 原始字符串
* @param idx 待删除位置下标
* @return 新的删除了指定位置字符的字符串
*/
public String strDeleteIndex (String str, int idx){
char[] arr = new char[str.length()-1];
char[] origin = str.toCharArray();
System.arraycopy(origin,0,arr,0,idx);
System.arraycopy(origin,idx+1,arr,idx,arr.length-idx);
return new String(arr);
}
}