补充10道题(10/10)
1.求矩阵中最大数的个数
特别注意ops是2-d的
我的答案:
显然,operation里面的列表和顺序是没有关系的,最大值和len(operation)有关,而最大值的个数和row 和col的最小值的乘积有关(因为最小,所以每一次+1都会参与)
别人的答案:
想法一样,但是用zip来分开两个列表。注意星号(*)的使用,表示收集输入的参数,用元组来打包。首先*ops先解包,zip函数的参数输入可以为0~n任意
*ops会将列表转换成len(ops)长度的元组,作为函数参数传递进入zip,zip再将对应位置的元素提取组成新的元组输出
比如ops=[[1,2,3],[4,5,6]] 则 *ops=(1,2,3),(4,5,6)
所以zip(*ops)== zip((1,2,3),(4,5,6))
2.求两个列表的交集
利用内置的数据结构set能够很容易的解决这个问题
假如不用内置的数据结构,可以考虑用hash 表,也就是用字典结构
方法一: 速度86.51%
方法二:速度 55%
方法三:33%
question 3:
我的答案:
question 4 删除链表中的指定节点
给定一个链表,要求删除链表值为指定值的节点
答案:典型的链表操作题目
别人的答案:用递归函数找到链表的最底端,再重新构建链表
首先在这道题目里面会因为链表太长而导致递归深度太大而超时,但是这种简洁的代码和递归思想很好,值得学习
question 5 比较两个二叉树
给定两个二叉树,比较这两个树是不是相同的(结构,值)
我的答案:
直接利用递归方法检查
qusetion 6 查询一个二叉树的最小深度
给定一个二叉树,找出最小深度
我的答案:
利用递归思想,统计每一个节点的深度,有两种情况 :
没有子节点:深度为1 有子节点:深度为2
将每个节点的深度取最小值加起来,就是最小深度了。
这里有一种情况是 2
/
1
那么对于节点 1,深度为1,对于节点2,左子节点深度为1,右子节点深度为0
假如返回 1+min(DR+DL)显然结果为 1,不符合
像这种情况需要特别处理,对于这样的不平衡节点,母节点的深度应该是自身加上最大的子节点深度
qusetion 7查询一个二叉树的最大深度
这类问题的相似:查找二叉树的最大深度。显然最大深度就没有上面的问题了,对于不平衡的节点(一边有子节点,一边没有子节点)肯定是取最大的子节点深度。所以任何情况都是去子节点的最大深度
答案:
question 8:字符串查找
给定两个字符串,看是不是每一个字符都相等
我的答案:
简单的hash表查询
注意下面注释掉的方法也是可行的,但是时间复杂度是 O(4N)
用字典查询是 O(2N)
结果也显示第一种方法(62ms)用的时间是第二种(112ms)的一半
别人的方法:
实际上思路是一样的,但是代码就简洁很多
用了字典方法get来建立字符串统计,就避免了啰嗦的逻辑判断,这点值得学习
question 9:最大回文长度
给定一个字符串,返回最大可组成的回文长度
我的答案:
直接统计字符串,对于出现偶数次(2n)的,整体都能构成回文。对于出现奇数次(2n-1)的,有2n-1-1能构成回文,最后再只出现一次的字符中选一个出来,就是整体的回文了
question 10:翻转链表