思考:
1、(2019年11月18日18:04:40)每种解法:时间复杂度O(n)、空间复杂度O(1)没有考虑,现在只是想怎么解决这些问题。
Part一、LinkedList 部分:
2019年11月18日17:57:26
1、21.合并两个有序链表 迭代,长短链表后面将cur指针在短链表尾部重新指向长链表剩余的节点的首节点,递归
2、83. 删除排序链表中的重复元素由于给定的链表是有序的,之间判段前后节点的大小即可,如果适用于更一般的情况可以使用dict={}记录节点的值,遍历链表中重复的节点并将其删除
3、141. 环形链表方法一、使用哈希表set(head),set.add(),记录节点的引用,存在重复的引用,就是链表有环!方法二、快慢指针,可以设定快指针移速是慢指针的移速的两倍
4、160. 相交链表使用使用哈希表set(head),set.add(),将第一个链表的节点向存储,在遍历第二个链表,判断是否有相交节点
5、203. 移除链表元素遍历链表,判断节点是否与给定元素相等,相等就删除指针(首节点head和在普通节点情况);递归
6、206. 反转链表 方法一、使用stack,容器记录链表节点;方法二、迭代;方法三、递归地反转链表
链表常用解法中:一、容器;二、迭代;三、递归。四、快慢指针:第一直觉使用容器,进阶的要求是:如何用迭代、递归、快慢指针解决该问题!
Part二、Tree 部分:
0、树的题目:一、树中的元素;二、树的属性(深度、高度!、节点个数!)
1、101. 对称二叉树:2019年11月20日09:24:03 思路:使用递归,基线条件是:if root is None:return,中序遍历树的各个元素并用列表存储各个节点的元素,将列表倒序和原列表比较,如果相等则树T是对称二叉树。递归当中主体函数的局部变脸和参数!本来想递归中调用其他函数,但是函数中还是要定义一个列表!共用的参数可以!这个思路是有问题的!调用函数可以传递参数!不能是数据结构,因为肯定要定义!每次调用都会被覆盖!静态变量中间计算值,而且结果不影响!return只会返回一个确定的值或者常数,或者调用函数!
return isSameTree()、return True、print(line)、return 1、isSameTree(data,target,p,q)...
2、104. 二叉树的最大深度 2019年11月20日11:15:50,提交通过,但是没有很清楚的理解这段代码的含义!只是觉得将树最大深度游分成查找左子树最大深度和右子树最大深度的最大值。有点迷糊的原因是:我认为活动纪录在有有右节点时也增加了+1,从而变成元素的个数!所以代码的return值应该大于要求值,但是没有!!!理解错误!:因为将树分成左子树的最大值和右子树的最大值,然后比较大小取较大值加1及return会活动记录保存的“根节点”的执行代码,由内而外递归确认整棵树的深度!两次调用的活动记录的执行位置都是子树对应的根节点!
class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ # 如果左右节点有一个不为空,返回1 if root is None: return 0 # if not (root.left or root.right ): # return 1 return max(1+self.maxDepth(root.left),1+self.maxDepth(root.right))