小李飞刀：刷题第四弹！

luffyZh 发布于2019-07-31 10:02 / 2663人阅读

摘要：第二题罗马数字转整数难度简单罗马数字包含以下七种字符，，，，，和。字符数值例如，罗马数字写做，即为两个并列的。通常情况下，罗马数字中小的数字在大的数字的右边。给定一个罗马数字，将其转换成整数。

随便说点啥

TIME:2019-02-01
昨晚其实刷了题来着，但是没有解出来，哭泣！
但是，今天重新写了下，解出来咯~
所以今天的题量要增加咯~
我会加油的！

第一题

14. 最长公共前缀
难度：简单

</>复制代码 
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

我的解题代码如下：

</>复制代码 
class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        length = len(strs)
        result = ""
        if length < 1:#如果空就不需要比较
            return result
        if length < 2:
            result = strs[0]
            return result
        #找到最短词，避免越界
        l = len(strs[0])
        for i in strs[1:]:
            if l > len(i):
                l = len(i)#最小的循环次数
        for j in range(l):#循环二维 strs[a][j]
            for a in range(1,length):
                if strs[0][j] == strs[a][j]:#始终按第一个数组来做比对
                    if a == length - 1:#数组最后一位
                        result = result + strs[0][j]
                else:
                    return result
        return result

因为是第二遍写了，所以加了很多奇怪的注释，但是思路清晰很多。
注释还是很重要的~

我的主要思路是：

判断数据量是否需要继续循环判断，数组长度为0和为1情况下结果不同。（为1的时候要返回数组本身....因为这个所以执行错误一次）

当需要循环判断的时候，始终拿strs[0][j]就是数组第一项的每一个字母来做比较。

双重循环来判断，一层是判断数组每个数，一层是判断是否有项目超出字母数量。

总结：
双重循环的效率还是比较低的，可以再考虑优化下，看下官方题解的方式。

第二题

13. 罗马数字转整数
难度：简单

</>复制代码 
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

我的解题代码如下：

</>复制代码 
class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000,"IV":4,"IX":9,"XL":40,"XC":90,"CD":400,"CM":900}
        if len(s) < 2:
            result = dic[s[0]]
            return result
        length = len(s)
        l = 0
        while l < length:
            point = s[l]
            if l + 1 == length:
                l = l + 1
            elif point == "I" and (s[l+1] == "V" or s[l+1] == "X"):
                point = point + s[l+1]
                l = l + 2
            elif point == "X" and (s[l+1] == "L" or s[l+1] == "C"):
                point = point + s[l+1]
                l = l + 2
            elif point == "C" and (s[l+1] == "D" or s[l+1] == "M"):
                point = point + s[l+1]
                l = l + 2
            else:
                l = l + 1
            result = result + dic[point]
        return result

执行效率上属于偏慢的那一拨。
我的主要思路是：

用字典来映射字母对应的数字，包括需要特殊对待的朋友们

当遇到特殊字符的时候做特殊判断

总结：

看了佳扬的思路后茅塞顿开，其实对于特殊字符可以简单的判断，他们对应数字的大小。这样就简化判断为比大小，而不是多重对比字符内容。

字典用来做映射还是比较快，还是要多研究下它的用法。

第三题

21. 合并两个有序链表
难度：简单

</>复制代码 
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

我的解题代码如下：

</>复制代码 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        r = ListNode(0)#游标
        result = r
        while 1:
            if l1 is None and l2 is None:
                return None
            elif l1 is None:
                return l2
            elif l2 is None:
                return l1
            elif l1.val < l2.val:
                r.val = l1.val
                l1 = l1.next
                if l1 is None:
                    r.next = l2
                    break
                r.next = ListNode(0)
                r = r.next
            else:
                r.val = l2.val
                l2 = l2.next
                if l2 is None:
                    r.next = l1
                    break
                r.next = ListNode(0)
                r = r.next
        return result

算是比较大众的一个效率。

我的主要思路是：

对比两个链表节点的值，首先取小的值，才会有序。

判断每次的l1和l2是否有next，当其中一个不存在的时候，就可以直接连接另一条链表了。

总结：

链表的结构第一次接触。本题主要是熟悉了下对当前节点部署下一节点的方法。主要方式为将游标指向下一节点即可。每次都对节点进行操作。

链表的形式还有多种，包括对其的增删改查，都需要再熟悉。

GPU云服务器云服务器飞刀小李刷题时刷题后

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43140.html

小李飞刀：刷题第五弹！

摘要：写在前面的话好几天木有刷题啦，今天猛刷了一把，要梳理一个顺序好好的学习啦一定要好好执行每天做题的计划最近真的好忙碌啊，还要做视频。第二题最大子序和难度简单给定一个整数数组，找到一个具有最大和的连续子数组子数组最少包含一个元素，返回其最大和。写在前面的话好几天木有刷题啦，今天猛刷了一把，要梳理一个顺序好好的学习啦~一定要好好执行每天做题的计划！最近真的好忙碌啊，还要做视频。不过呢，看...

Miracle 2019-07-31 10:08 评论0 收藏0
小李飞刀：刷题第三弹！

摘要：刷题第三天正式刷题第三天。注意空字符串可被认为是有效字符串。错误的一次是因为没有考虑空字符串，当存在为的时候，结果应该为。第二题加一难度简单类型给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。刷题第三天正式刷题第三天。之前看了个说法，挺认可的。就是不要太在意一天的能呈现的价值，但是要在意累计的价值。之前很多时候我会对今天一天没有完成的计划而沮丧，事实上，算法的实践...

SillyMonkey 2019-07-31 10:02 评论0 收藏0
小李飞刀：刷题第十三弹！

摘要：写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。排序算法冒泡排序主要是比对相邻两个数之间的大小关系，不断将较大值交换至最后。写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。认真做题的分割线第一题 215. 数组中的第K个最大元素难度：中等在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的...

lixiang 2019-07-31 10:20 评论0 收藏0
小李飞刀：做题第七弹！

摘要：给定一个大小为的数组，找到其中的众数。第五题合并两个有序数组难度简单给定两个有序整数数组和，将合并到中，使得成为一个有序数组。说明初始化和的元素数量分别为和。第六题二叉树的最大深度难度简单给定一个二叉树，找出其最大深度。写在前面的话做做做题，慢慢上手了就觉得刷题速度变快了，果然还是有点笨~希望最后一窍快点通吧~ 开始做题第一题 169. 求众数难度：简单给定一个大小为 n 的数组...

AlphaWatch 2019-07-31 10:09 评论0 收藏0
小李飞刀：做题第十二弹！

摘要：写在前面今天没有叨逼叨但是又一次错过了竞赛爱睡觉的小李下周要上班，下下周一定要参加了握拳认真做题的分割线第一题两地调度公司计划面试人。第人飞往市的费用为，飞往市的费用为。示例输入输出解释第一个人去市，费用为。写在前面今天没有叨逼叨...但是又一次错过了竞赛...爱睡觉的小李...下周要上班，下下周一定要参加了（握拳认真做题的分割线第一题 1029. 两地调度公司计划面试2N人。...

yagami 2019-07-31 10:19 评论0 收藏0