(10/10)补做:到2017-06-25前

补充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:翻转链表




最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,523评论 1 31
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,273评论 0 12
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 18,011评论 2 36
  • 在我们的爱情里,我对你毫无怀疑。然而,我却无数次的被欺骗。在这无数次欺骗之后,我等了很久也没有等到你的道歉,哪怕只...
    沙漏Backpacker阅读 650评论 1 0
  • 不知不觉,时光已穿过宇宙的洪流,不紧不慢,岁月便翻过万水千山,我这才恍然发现,我已不再是小孩子了。在感恩节到来之...
    金梓Penny阅读 301评论 0 0