做一网站要什么,公司做网站费用,电脑制作网站总么做,大连网络推广网站优化找哪家好529 Minesweeper
输入#xff1a;一个二维矩阵#xff0c;一些修改规则。 如果点到一个隐藏的地雷M#xff0c;把它改为X#xff0c;游戏结束 如果点到一个E#xff0c;且其周围8邻接的范围没有地雷#xff0c;那么应该把8邻接的范围的格子全部翻开为E 如果翻开的…529 Minesweeper
输入一个二维矩阵一些修改规则。 如果点到一个隐藏的地雷M把它改为X游戏结束 如果点到一个E且其周围8邻接的范围没有地雷那么应该把8邻接的范围的格子全部翻开为E 如果翻开的格子的八邻接范围有隐藏的地雷就将其标注了地雷的数目1-8而非E。规则拷贝链接
输出扫雷后的矩阵。 分析从第二条规则可以看到这是需要迭代递归的。递归过程可以从一个节点开始不断查找邻接点扩展下去也可以沿着节点一层一层扩展下去。前者是DFS后者是BFS。和前面的几道题目是一样的。 这个题目的难点1是英语问题没有理解 If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively。 难点2 是计算邻接点坐标变化的change数组。知道8个方向上xy坐标值得变化。 看代码会发现依然使用的是BFS的模板。有了套路真好。有时间再回头看看DFS的套路。整个做完DFS并没有目前对BFS的套路感觉。 代码
102. Binary Tree Level Order Traversal
我认为不值得再写个新文章。如果从BFS的习题练习到这里大概已经形成思路。套用即可。最近在用idea写LeetCode的代码。我认为idea就是开发工具界的搜狗输入法。好用好用真好用。 代码
199. Binary Tree Right Side View
输入二叉树 输出从右边站着看二叉树从上到下得到的值。 分析这与102比较102要求记下一层中的每一个节点的值199要求记录下一层中最右边节点的值。用BFS思路的话只要把上一题的代码拷贝过来改改即可。用DFS思路的话也是拷贝上一题的代码改改就能跑起来。如果能先遍历左节点每层只调用一次list的add方法速度会更快。 代码
863. All Nodes Distance K in Binary Tree
输入二叉树目标节点距离K 输出所有距离目标节点距离K路径的节点值列表 思路1
首先找到根节点距离target node 的距离 rootDistance 其次存储所有节点与父节点的map 最后一个节点距离目标节点的距离t 其父节点距离目标的节点 1 假设dist[i] 表示值为i的节点距离目标节点的距离。dist[3]1,dist[5]0,dist[1]dist[3]1,dist[2]dist[5]1。考虑到这里我就认为dist[node]dist[node.parent]1.假设在node3和node5之间加一个节点node9实际dist[9]1按照公式dist[9]dist[3]1.不正确。 这种通过一两个节点特例来总结规律的情况需要考虑全所有的情况。
纠正思路1 1 树的遍历不一定非要从跟节点开始。 2 直观地看。如果target 在一个节点的左子树距离为dist则这个节点的右子树上距离为K-dist的节点都符合要求。当然target节点子树上再遍历K层的元素也符合要求。例如目标节点是6K2。节点5与节点6距离为1那么节点5的右子树上与节点5距离为K-11的节点符合要求。节点6距离节点3的距离为2节点3符合要求。当然对于节点6的子节点距离为K的子节点也符合要求。 3 如果 target在右子树上情形也是一样的。 这道题目最好不要看做树而是看做图。因为当看做树的时候会更多的去考虑父子关系和父子节点。如果看做图则所有节点地位相同。 代码方法distanceKV2
思路2 1 存储所有节点与父节点的map。 2 将node5加入到队列。dist0。 3如果distK, 弹出队列所有元素将每个元素的子节点父节点加入到队列。dist。调回2。 4如果distK弹出队列所有元素将元素值放入list中作为结果集。 做的过程中会发现有重复处理的元素不合理的结果。这时候用一个set在加入到队列之前判断一下是否已经处理过。 代码方法distanceK 代码
