建设网站的目的及功能,网站建设 博采,杭州建设工程招投标,即墨网站推广199. Binary Tree Right Side View
思路#xff1a;想要得到树的每一层最右侧元素值#xff0c;用BFS最方便。先访问左节点再访问右节点#xff0c;最后访问的一个值就是留下的值。 想要DFS的思路也可以。只是一定要访问所有节点。 代码
491 Increasing Subsequences …199. Binary Tree Right Side View
思路想要得到树的每一层最右侧元素值用BFS最方便。先访问左节点再访问右节点最后访问的一个值就是留下的值。 想要DFS的思路也可以。只是一定要访问所有节点。 代码
491 Increasing Subsequences
思路我的习惯思维是对于nums[idx]可以选择取或者不取。取的话在什么条件下可以取。满足什么条件的结果可以记录到结果中。想好这些就能写代码了。 本题list记录上一步已经取的数字。如果if (list.size() 0 || nums[idx] list.get(list.size()-1)) 的时候就可以取当前元素到列表。只要list.size 大于等于2 就可以加入结果集。题目还需要去重。 学习还有一种dfs的思路是findSequence(int[] nums, int idx, DequeInteger list, SetListInteger result) 前一步放入list中的最后一个元素的下标是idx-1当前可以决定继续加入的元素是从idx到数组末尾中的任何一个元素当然元素也是要符合条件的。 代码
785. Is Graph Bipartite?
思路要把所有的顶点下标分为两个集合lista 和listb。先往lista加入节点0。和0相邻的点加listb。再不断遍历lista和listb加入新的节点。如果相邻节点在同一个list中那就返回false。代码啰嗦笨拙参见isBipartiteV2。 学习1用colors数组来区分两个集合。-1认为还没有加颜色0为一组1为另外一组。在加颜色过程中使用DFS的思路。 例如输入 [[1,3], [0,2], [1,3], [0,2]]。 染色顺序从0到1从1到2从2到33的邻边已经染色完成判断是不是有效就行。 学习2思路同上。在加颜色过程中使用BFS的思路。 例如输入 [[1,3], [0,2], [1,3], [0,2]]。 染色顺序从0到1从0到31,3加入队列一边染色一边判断是否有效 从1到0从1到22加入队列一边染色一边判断是否有效 从3到0从3到2一边染色一边判断是否有效 从2到1从2到3 代码
129. Sum Root to Leaf Numbers
思路深度优先的套路。在处理每个当前节点node的时候把它当做根节点继续dfs找到node与其根节点关系再定返回值。 代码
200. Number of Islands
思路用DFS的思路很简单。找到一个岛屿的起点(i,j)不断向4个方向扩散把相邻的节点都改为2。这样一次完整的dfs遍历算是一个岛屿识别完成。接着再找下个岛屿的起点。 学习UnionFind并查集思路。将二维的grid用一维数组表示父节点信息。 代码
116. Populating Next Right Pointers in Each Node
思路dfs的话先遍历一个节点的右子树在同一深度保持尽可能的右侧节点。但是当同一层的节点称为别的节点的next后当前节点就成为该层右侧节点了。用一个map来存储。 学习同一层次的节点向右指向next其实用BFS的思路最好。不过看别的代码这次BFS没有使用queue来解决而是巧妙的使用了dummy.next和节点next将同一层的节点连起来。是学习的地方。 代码
114. Flatten Binary Tree to Linked List
思路dfs的思路。今天的收获是起一个好的方法名字有利于自己思路形成。以前的代码都直接将方法命名为dfs其实不知道在做什么。今天的方法名flattenNode是对node这一个节点做展开。能够理清楚一个节点做展开应该做哪些事情递归就好写了。 观察发现例如处理node3不需要做什么事情。处理node2能看到node4变成了node3的右子树node3变成了node2的右子树。得出如果有左子树那么左子树称为node的右子树原来node的右子树成为现在node右子树叶子节点的右子树。把node的左子树置为null。 代码
802. Find Eventual Safe States
思路开始不能明白k的作用不能明白例题中0,1,3节点为什么就不可以。 我理解的5,6出度为05,6是terminal node肯定是safe state。节点2节点4可以走到节点5所以节点2节点4也属于safe state。节点0节点1可以走到节点2那么节点0节点1也应该是safe state。 节点3能够走到节点0那节点3也是safe state。所以0,1,2,3,45,6应该都是safe state。 但题目中有句话是starting node is eventually safe if and only if we must eventually walk to a terminal node.“ if and only if ”说明是可以并且只能走到safe state。 节点0可以走节点2到达节点5,但是同时节点0还可以走到节点1节点3,再到节点0。没有任何证据表名节点1或者节点3不是terminal node所以节点0也就不是safe state。也就是不符合 if and only if。这就清楚了一个节点如果它的出度为0或者链接的节点都是safe state的那它才是safe state。 学习从一个节点开始深度优先进行搜索。如果能够走到终点并且只能走到终点则认为无环是一个safe state。我们将访问节点的不同状态称为 白-灰-黑还没有开始访问节点是白(0)开始访问一个节点是灰(1)访问一个节点结束是黑(2)。 如果在访问节点A的过程中遇到了灰色的节点B那么说明A在一个环内。A不是一个safe state。 如果在访问节点A的过程中所有的路径都能达到一个terminal node没有进入环内则A是一个safe state。 时间复杂度O(NE) N是顶点数E是边数。 代码
