摘要：第二題羅馬數(shù)字轉(zhuǎn)整數(shù)難度簡(jiǎn)單羅馬數(shù)字包含以下七種字符，，，，，和。字符數(shù)值例如，羅馬數(shù)字寫做，即為兩個(gè)并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。

TIME:2019-02-01
昨晚其實(shí)刷了題來著，但是沒有解出來，哭泣！
但是，今天重新寫了下，解出來咯~
所以今天的題量要增加咯~
我會(huì)加油的！

14. 最長(zhǎng)公共前綴
難度：簡(jiǎn)單

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。

我的解題代碼如下：

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)#最小的循環(huán)次數(shù)
        for j in range(l):#循環(huán)二維 strs[a][j]
            for a in range(1,length):
                if strs[0][j] == strs[a][j]:#始終按第一個(gè)數(shù)組來做比對(duì)
                    if a == length - 1:#數(shù)組最后一位
                        result = result + strs[0][j]
                else:
                    return result
        return result            

因?yàn)槭堑诙閷懥?，所以加了很多奇怪的注釋，但是思路清晰很多?br>注釋還是很重要的~

我的主要思路是：

判斷數(shù)據(jù)量是否需要繼續(xù)循環(huán)判斷，數(shù)組長(zhǎng)度為0和為1情況下結(jié)果不同。（為1的時(shí)候要返回?cái)?shù)組本身....因?yàn)檫@個(gè)所以執(zhí)行錯(cuò)誤一次）

當(dāng)需要循環(huán)判斷的時(shí)候，始終拿strs[0][j]就是數(shù)組第一項(xiàng)的每一個(gè)字母來做比較。

雙重循環(huán)來判斷，一層是判斷數(shù)組每個(gè)數(shù)，一層是判斷是否有項(xiàng)目超出字母數(shù)量。

總結(jié)：
雙重循環(huán)的效率還是比較低的，可以再考慮優(yōu)化下，看下官方題解的方式。

13. 羅馬數(shù)字轉(zhuǎn)整數(shù)
難度：簡(jiǎn)單

羅馬數(shù)字包含以下七種字符: I， V， X， L，C，D 和 M。
字符          數(shù)值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 羅馬數(shù)字 2 寫做 II ，即為兩個(gè)并列的 1。12 寫做 XII ，即為 X + II 。 27 寫做  XXVII, 即為 XX + V + II 。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。
給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1 到 3999 的范圍內(nèi)。

我的解題代碼如下：

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

執(zhí)行效率上屬于偏慢的那一撥。
我的主要思路是：

用字典來映射字母對(duì)應(yīng)的數(shù)字，包括需要特殊對(duì)待的朋友們

當(dāng)遇到特殊字符的時(shí)候做特殊判斷

總結(jié)：

看了佳揚(yáng)的思路后茅塞頓開，其實(shí)對(duì)于特殊字符可以簡(jiǎn)單的判斷，他們對(duì)應(yīng)數(shù)字的大小。這樣就簡(jiǎn)化判斷為比大小，而不是多重對(duì)比字符內(nèi)容。

字典用來做映射還是比較快，還是要多研究下它的用法。

21. 合并兩個(gè)有序鏈表
難度：簡(jiǎn)單

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

我的解題代碼如下：

# 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)#游標(biāo)
        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            

算是比較大眾的一個(gè)效率。

我的主要思路是：

對(duì)比兩個(gè)鏈表節(jié)點(diǎn)的值，首先取小的值，才會(huì)有序。

判斷每次的l1和l2是否有next，當(dāng)其中一個(gè)不存在的時(shí)候，就可以直接連接另一條鏈表了。

總結(jié)：

鏈表的結(jié)構(gòu)第一次接觸。本題主要是熟悉了下對(duì)當(dāng)前節(jié)點(diǎn)部署下一節(jié)點(diǎn)的方法。主要方式為將游標(biāo)指向下一節(jié)點(diǎn)即可。每次都對(duì)節(jié)點(diǎn)進(jìn)行操作。

鏈表的形式還有多種，包括對(duì)其的增刪改查，都需要再熟悉。