小李飞刀：刷题第四弹！

随便说点啥

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

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

注释还是很重要的~

我的主要思路是：

strs[0][j]

总结：

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

第二题

13. 罗马数字转整数

难度：简单

我的解题代码如下：

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，当其中一个不存在的时候，就可以直接连接另一条链表了。

总结：

• 链表的结构第一次接触。本题主要是熟悉了下对当前节点部署下一节点的方法。主要方式为将游标指向下一节点即可。每次都对节点进行操作。
• 链表的形式还有多种，包括对其的增删改查，都需要再熟悉。