zcr214

分类

题解(7)

/ 注册

全部文章（共7篇）

题解 | #小米Git#

本质上是一个求最近公共祖先的问题，关键要解决的问题是把输入转换成一个树形结构，这里仍然是用字典来存储：针对给定的样例["01011","10100","01000","10000","10000"],1,2 以当前节点为key，关联节点为value列表，可以转换为： { 0:[1,3,4], 1:...

Python3 递归

2021-12-16

10 987

题解 | #重排链表#

用列表存储每个节点，依次弹出首位、末位的节点，组成新链表即可。没有新建链表，空间复杂度O(n),时间复杂度O(2n)=O(n) # class ListNode: # def __init__(self, x): # self.val = x # self....

Python3

2021-12-13

1 475

题解 | #树的直径#

本题最大的麻烦之处在于输入是离散的一条条边，没有直接保存节点，需要从这些边当中提取节点的信息，从而将他们处理成树的关系，即：要保存节点，以及节点之间的边长由于不是二叉树，每个节点的子节点可能存在多个，则需要用一个二维的结构来保存树。然后再使用“二叉树中的最大路径和”的结题思路，采取动态规划算法即...

Python3

2021-12-10

1 562

题解 | #求二叉树的层序遍历#

深度优先递归，从左到右，依次加入当前层级对应的列表中即可。 global res res=[] def walk(node,i):#节点、层数 global res if node is None: return if len(res)<i+1:#如果该...

Python3

2021-12-09

0 366

题解 | #直方图内最大矩形#

单调栈一个单调递增的栈，栈内数据形成的矩形面积为最低值（栈首）x总长度但是输入不可能是单调递增的，因此要维持单调性，当后续值无法再入栈时必须将末尾较大的值出栈，直到新的数可以入栈。出栈的数计算其形成的面积（高度x累积的宽度），并把出栈的个数累积为宽度，作为新入栈的数所携带的宽度数据。每次计...

Python3

2021-12-09

1 694

题解 | #打家劫舍(三)#

动态规划，单看一个二叉树结构，当前节点取得最大值分为偷或不偷两种情况，取决于左右两边是否偷了每次计算返回当前节点偷和不偷分别能够取得的最大值当前节点偷：则左右两边都不能偷,即： yes=no左+no右+当前值当前节点不偷：则左右两边都偷了，或都不偷，或左右只有一个偷了,即： no=ma...

Python3 二叉树动态规划

2021-12-08

0 479

题解 | #打家劫舍(二)#

到第i家时，最大收益取决于前面一家是否已偷，状态转移为 dp[i]=max(dp[i-1],dp[i-2]+nums[i]) 本题区别于打家劫舍（一）的关键要点在于闭环的位置，即第一家和最后一家衔接可以通过定义2个动态规划数组用来保存第一家偷钱dp1和未偷钱dp2的两种情况，到最后一家时：如果...

Python3

2021-12-03

1 468