wowowo123

题解

动态规划(1) 未归档(4)

/ 注册

全部文章 / 题解（共93篇）

剑指二叉搜索树第k小的结点

中序遍历然后输出数组的k小结点 class Solution: # 返回对应节点TreeNode def KthNode(self, pRoot, k): # write code here result=[] def inorde...

2021-03-23

0 458

剑指二叉树中序遍历下一个节点

通过将出现的节点类型，分类，然后输出结果如果当前节点存在右子树，那么下一个节点就是右子树中没有第一个左子树的节点，也就是最左的节点。如果当前节点不存在右子树，那么下一个节点是父节点往上搜索中，为其父节点左节点的节点，返回其父节点。如果没有满足条件的那么就返回None class Solution:...

2021-03-23

0 734

剑指树的深度

通过递归的方法，先去求左子树的路径长度，再去求右子树的路径长度，看哪一个路径长度大，则返回哪一条路径。 class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here ...

2021-03-21

0 504

剑指复杂链表的复制

通过hashmap 保存节点，然后再去遍历串起链表。 hashmap存储节点时候需要新建一个randomlistnode。注意返回的是 hashmap[pHead] # -*- coding:utf-8 -*- # class RandomListNode: # def __init__(...

2021-03-21

0 438

剑指删除链表重复节点

使用一个栈，和一个数组辅助实现。遍历一次链表将不重复的节点放入栈中，其中判断不重复使用duplicate,然后通过栈来生成链表返回时间O(n) 空间O(n) # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x):...

2021-03-21

0 405

剑指链表环的入口

通过指针方法，设置快慢指针，快指针每次前进两个节点，慢指针每次前进一个节点，当他们第一次相遇后，证明链表中存在环，然后将快指针置为头指针，慢指针与快指针继续每次前进一个节点，当他们再次相遇，就是换的入口位置。如果快慢指针从不相遇，快指针会走到链表结尾，那么就不存在环。O(n) 快指针走了n(n &...

2021-03-20

0 415

剑指第一个重复

因为字符流，先进入的先处理，所以依靠队列存储，和hashmap记数。insert函数插入字符，如果原先队列里没有就直接插入，如果有了就不插入了，然后使用hashmap记数，在first函数中，如果队列开头元素没重复，则输出，如果开头元素重复了则弹出，再继续看下一个元素。 class Solutio...

2021-03-20

0 470

剑指构建乘积数组

对于每一个B[i]值都分为左右两段的乘积，分别循环得到他们的结果。 O(n^2) class Solution: def multiply(self, A): # write code here if len(A)==1: retur...

2021-03-20

0 488

剑指二叉树路径

本题可以通过递归和非递归的方法去解决，需要先理解遍历二叉树所有路径的解法，然后增加路径和约束即可。递归方法也有两种，一个是维护全局变量数组，需要每次在最后进行回溯，第二个是传递参数，这样就不用回溯。非递归的方法就是通过队列帮助,注意在队列中传入节点，以及节点之前的路径。通过递归函数，每次记录下...

2021-03-20

1 550

剑指是否为二叉搜索树

使用递归方法，先找到大于根节点的节点，该节点为左右子树分界点，然后分别去判断左右子树是否为二叉搜索树。注意数组为空时，不是二叉搜索树。 # -*- coding:utf-8 -*- class Solution: def JudgeSquence(self,sequence): ...

2021-03-19

0 507