用列表存储每个节点，依次弹出首位、末位的节点，组成新链表即可。 没有新建链表，空间复杂度O(n),时间复杂度O(2n)=O(n) # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return void # class Solution: def reorderList(self , head ): # write code here if he...

本题最大的麻烦之处在于输入是离散的一条条边，没有直接保存节点，需要从这些边当中提取节点的信息，从而将他们处理成树的关系，即：要保存节点，以及节点之间的边长 由于不是二叉树，每个节点的子节点可能存在多个，则需要用一个二维的结构来保存树。 然后再使用“二叉树中的最大路径和”的结题思路，采取动态规划算法即可。 这里我是用了字典结构，键是起始节点，值是终止节点，遍历一次可以得到每个节点到其他节点的关系。为了避免输入有向性造成树的构建不完整，因此每个节点都单独保存，在递归计算的时候把上级节点序号传入，用来避免原路返回，以题中的样例，即： { 0:[1], 1:[0,2,5], 2:[1,3,4],...

深度优先递归，从左到右，依次加入当前层级对应的列表中即可。 global res res=[] def walk(node,i):#节点、层数 global res if node is None: return if len(res)<i+1:#如果该层还没有，则新增一层，即新加一列 res.append([]) res[i].append(node.val)#当前值加入对应的层列表 l=walk(node.left,i+1)#从左到右依次深入 r=walk(node.right,i+1) cla...

单调栈 一个单调递增的栈，栈内数据形成的矩形面积为 最低值（栈首）x总长度 但是输入不可能是单调递增的，因此要维持单调性，当后续值无法再入栈时必须将末尾较大的值出栈，直到新的数可以入栈。 出栈的数计算其形成的面积（高度x累积的宽度），并把出栈的个数累积为宽度，作为新入栈的数所携带的宽度数据。 每次计算面积，都更新最大面积。 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param heights int整型一维数组 # @return int整型 # def walk2(heights):#单调栈思路 if len(...

动态规划，单看一个二叉树结构，当前节点取得最大值分为偷或不偷两种情况，取决于左右两边是否偷了 每次计算返回当前节点偷和不偷分别能够取得的最大值 当前节点偷：则左右两边都不能偷,即： yes=no左+no右+当前值 当前节点不偷：则左右两边都偷了，或都不偷，或左右只有一个偷了,即： no=max(no左+no右,yes左+yes右,yes左+no右,no左+yes右) 然后更新最大收益: maxVal=max(yes,no) 代码如下 global maxVal maxVal=0#初始化为0 def walk(node): global maxVal if node is...

到第i家时，最大收益取决于前面一家是否已偷，状态转移为 dp[i]=max(dp[i-1],dp[i-2]+nums[i]) 本题区别于打家劫舍（一）的关键要点在于闭环的位置，即第一家和最后一家衔接 可以通过定义2个动态规划数组用来保存第一家偷钱dp1和未偷钱dp2的两种情况，到最后一家时： 如果第一家偷了，则最后一家必然不能拿，则dp1[i]=dp[i-1] 如果第一家没偷，则最后一家可以正常选择，保持不变dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i]) 然后取2者最大值即可。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 #...