LeetCode 題解3 (Python)

本文轉(zhuǎn)載自作業(yè)部落的chanvee.

Merge Two Sorted Lists

這個(gè)題的意思是將兩個(gè)排序的鏈表合并為一個(gè)，鏈表的操作，比較簡(jiǎn)單，代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # @param two ListNodes
    # @return a ListNode
    def mergeTwoLists(self, l1, l2):
        result = ListNode(0)
        cur = result
        while l1 or l2:
            tmp = ListNode(0)
            if l1 and not l2:
                tmp = l1
                l1 = l1.next
            elif l2 and not l1:
                tmp = l2
                l2 = l2.next
            else:
                if l1.val < l2.val:
                    tmp = l1
                    l1 = l1.next
                else:
                    tmp = l2
                    l2 = l2.next
            cur.next, cur = tmp, tmp
        return(result.next)

Roman to Integer

將羅馬數(shù)字轉(zhuǎn)化為整數(shù)，只需要弄清楚羅馬數(shù)字的規(guī)則即可，規(guī)則如下：

  1. 相同的數(shù)字連寫(xiě)，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)，如：Ⅲ = 3；
  2. 小的數(shù)字在大的數(shù)字的右邊，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)， 如：Ⅷ = 8；Ⅻ = 12；
  3. 小的數(shù)字，（限于Ⅰ、X 和C）在大的數(shù)字的左邊，所表示的數(shù)等于大數(shù)減小數(shù)得到的數(shù)，如：Ⅳ= 4；Ⅸ= 9；
  4. 正常使用時(shí)，連寫(xiě)的數(shù)字重復(fù)不得超過(guò)三次。（表盤(pán)上的四點(diǎn)鐘“IIII”例外）
  5. 在一個(gè)數(shù)的上面畫(huà)一條橫線(xiàn)，表示這個(gè)數(shù)擴(kuò)大1000倍
    這里第5條沒(méi)有用，因?yàn)檩斎氩粫?huì)出現(xiàn)這種情況，那么只需按著這個(gè)編碼規(guī)則即可，代碼如下：
class Solution:
    # @return an integer
    def romanToInt(self, s):
        result = 0
        for i in range(len(s)):
            if s[i] == 'M':
                result += 1000
            elif s[i] == 'D':
                result += 500
            elif s[i] == 'C':
                if i + 1 < len(s) and (s[i+1] == 'M' or s[i+1] == 'D'):
                    result -= 100
                else:
                    result += 100
            elif s[i] == 'L':
                result += 50 
            elif s[i] == 'X':
                if i + 1 < len(s) and (s[i+1] == 'M' or s[i+1] == 'D' or s[i+1] == 'C' or s[i+1] == 'L'):
                    result -= 10
                else:
                    result += 10
            elif s[i] == 'V':
                result += 5
            else:
                if i + 1 < len(s) and (s[i+1] == 'M' or s[i+1] == 'D' or s[i+1] == 'C' or s[i+1] == 'L' or s[i+1] == 'X' or s[i+1] == 'V'):
                    result -= 1
                else:
                    result += 1
        return(result)

Integer to Roman

這個(gè)題與上個(gè)題目相反，將整數(shù)轉(zhuǎn)化為羅馬數(shù)字。我的方法有點(diǎn)無(wú)恥，先建了3各表：1-9, 10:10:20, 100:100:900,這樣每次就只需要除完之后就可以從表里面提取，不用再去寫(xiě)一遍規(guī)則。代碼如下：

class Solution:
    # @return a string
    def intToRoman(self, num):
        LesTen = ['I','II','III','IV','V','VI','VII','VIII','IX']
        LesHun = ['X','XX','XXX','XL','L','LX','LXX','LXXX','XC']
        LesThu = ['C','CC','CCC','CD','D','DC','DCC','DCCC','CM']
        result = []
        while num > 0:
            if num // 1000:
                result.append('M'*(num // 1000))
                num %= 1000
            elif num // 100:
                result.append(LesThu[num//100 - 1])
                num %= 100
            elif num // 10:
                result.append(LesHun[num//10 -1])
                num %= 10
            else:
                result.append(LesTen[num -1])
                num //= 10
        result = ''.join(result)
        return(result)

Compare Version Numbers

這個(gè)題的意思是比較兩個(gè)版本號(hào)的大小，方法簡(jiǎn)單，用split將字符串分割，然后依次比較大小即可。注意的特例是01 = 1，和1.0 = 1這兩類(lèi)例子，我們可以先把他們不起成為等長(zhǎng)。代碼如下：

class Solution:
    # @param a, a string
    # @param b, a string
    # @return a boolean
    def compareVersion(self, version1, version2):
        if version1 == version2:
            return(0)
        ver1 = version1.split('.')
        ver2 = version2.split('.')
        flag = 1
        for i in range(abs(len(ver1)-len(ver2))):
            if len(ver1) <= len(ver2):
                ver1.append('0')
            else:
                ver2.append('0')
        for i in range(min(len(ver1), len(ver2))):
            if int(ver1[i]) > int(ver2[i]):
                flag = 0
                return(1)
            if int(ver1[i]) < int(ver2[i]):
                flag = 0
                return(-1)
        if flag:
            if len(ver1) == len(ver2):
                return(0)
            if len(ver1) < len(ver2):
                return(-1)
            if len(ver1) > len(ver2):
                return(1)

Palindrome Number

判斷一個(gè)整數(shù)是不是回文，并且不能利用額外的空間，方法就是每次判斷最高位與最低位是否相同即可。代碼如下：

class Solution:
    # @return a boolean
    def isPalindrome(self, x):
        mode, result= 1, True
        while x//mode >= 10: ## 相當(dāng)于算出有多少位
            mode *= 10
        while x:
            if x // mode != x % 10:
                result = False
                return(result)
            x -= mode*(x//mode) 
            x //= 10
            mode //= 100
        return(result)

Count and Say

這個(gè)題有點(diǎn)不好理解，反正我是看了網(wǎng)上的意思才懂了，意思是比如從1開(kāi)始，因?yàn)橹挥?個(gè)1，所以第二個(gè)數(shù)就是11（表示1個(gè)1），第二個(gè)數(shù)有2個(gè)1，所以第三個(gè)數(shù)為21（表示2個(gè)1），第三個(gè)數(shù)有1個(gè)2,1個(gè)1，所以第四個(gè)數(shù)是（1211）以此類(lèi)推，懂了意思就好做了。代碼如下：

class Solution:
    # @return a string
    def countAndSay(self, n):
        if n == 1:
            return('1')
        if n == 2:
            return('11')
        result = []
        s = '11'
        for i in range(n-2):
            s = self.Trans(s)
        result = ''.join(s)
        return(result)
    def Trans(self, s):
        result = []
        tmp, count = s[0], 1
        for i in range(1,len(s)):
            if s[i] == s[i-1]:
                count += 1
                if i == len(s)-1:
                    result.append(str(count)+s[i-1])
            else:
                result.append(str(count)+s[i-1])
                tmp, count = s[i], 1
                if i == len(s)-1:
                    result.append(str(count)+s[i])
        result = ''.join(result)
        return(result)

Valid Sudoku

判斷給定的數(shù)獨(dú)二維數(shù)組是否合法，我們只要弄清楚數(shù)獨(dú)的規(guī)則就行：

  1. 每一行只包含1-9，既每一行沒(méi)有重復(fù)的數(shù)字
  2. 每一列只包含1-9，即每一列沒(méi)有重復(fù)的數(shù)字
  3. 每個(gè)小九宮格里面只包含1-9....
    接下來(lái)就簡(jiǎn)單了，遍歷他的所有行和列以及九宮格，看是否已經(jīng)存在相同的數(shù)字，如果存在則返回False，否則返回True。代碼如下：
class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        for i in range(9): # 行和列是否符合數(shù)獨(dú)
            tmp = []
            tmp1 = []
            for j  in range(9):
                tmp.append(board[i][j])
                tmp1.append(board[j][i])
            if self.isnodifferent(tmp) == False or self.isnodifferent(tmp1) == False:
                return(False)
        for i in range(0,9,3): # 判斷九宮格是否有相同的數(shù)字
            for j in range(0,9,3):
                tmp = []
                tmp.append(board[i][j])
                tmp.append(board[i][j+1])
                tmp.append(board[i][j+2])
                tmp.append(board[i+1][j])
                tmp.append(board[i+1][j+1])
                tmp.append(board[i+1][j+2])
                tmp.append(board[i+2][j])
                tmp.append(board[i+2][j+1])
                tmp.append(board[i+2][j+2])
                if not self.isnodifferent(tmp): 
                    return(False)
        return(True)
    def isnodifferent(self, s): # 判斷列表中是否有相同的數(shù)字
        while '.' in  s:
            s.remove('.')
        if s == []:
            return(True)
        flag = 0
        tmp = []
        tmp.append(s[0])
        for i in range(1, len(s)):
            if s[i] in tmp:
                flag = 1
                break
            tmp.append(s[i])
        if flag:
            return(False)
        else:
            return(True)

Remove Nth Node From End of List

從鏈表中移除倒數(shù)第N個(gè)數(shù)。思想很簡(jiǎn)單我就不再贅述了，有一個(gè)問(wèn)題是要想知道倒數(shù)，就要知道鏈表中總共有多少個(gè)元素，這里我是先遍歷一遍得到長(zhǎng)度，不知道有沒(méi)有其他更好的辦法。代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # @return a ListNode
    def removeNthFromEnd(self, head, n):
        tmp =  head
        L = 0 
        while tmp:
            L += 1
            tmp = tmp.next
        if n == L:
            return(head.next)
        tmp = head
        for i in range(L):
            if i == L - n -1:
                tmp.next = tmp.next.next
                break
            tmp = tmp.next
        return(head)

Excel Sheet Column Title

給定一個(gè)數(shù)字，將其轉(zhuǎn)換為Excel的title，其實(shí)就相當(dāng)于把一個(gè)數(shù)轉(zhuǎn)化為26進(jìn)制的數(shù)。代碼如下：

class Solution:
    # @return a string
    def convertToTitle(self, num):
        dic = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        result = ''
        while num:
            result = result + dic[(num-1)%26]
            num = (num - 1) // 26
        return(result[::-1])

ZigZag Conversion

按照題目給的意思進(jìn)行字符串的映射，排列的形狀就是由以前的一行變?yōu)轭?lèi)似于多個(gè)倒著的N這種形狀的轉(zhuǎn)換。它的轉(zhuǎn)換規(guī)則如下：

  1. 如果是第一行或者最后一行，那么從第一個(gè)數(shù)開(kāi)始到下一個(gè)數(shù)每次相差(2 * nRows - 2)
  2. 對(duì)于其他行，這一行的數(shù)字的排列是奇數(shù)列和偶數(shù)列交替的，當(dāng)然列號(hào)不一定是連續(xù)的，但是他們的列號(hào)肯定是奇偶交替的
  3. 對(duì)于奇數(shù)列，兩個(gè)相鄰的之間相差2 * (nRows - 1 - i)這么多個(gè)數(shù)
  4. 對(duì)于偶數(shù)列，兩個(gè)相鄰的之間相差2 * (nRows - i)這么多個(gè)數(shù)
    根據(jù)上面的規(guī)則我們就可以對(duì)其進(jìn)行轉(zhuǎn)化了，代碼如下：
class Solution:
    # @return a string
    def convert(self, s, nRows):
        result = ''
        if s == '' or nRows <= 1:
            return(s)
        i = 0
        while(i < len(s) and i < nRows):
            j = i
            result += s[j]
            k = 0
            while j < len(s):
                # 如果是第一行或最后一行 
                if i == 0 or i == nRows - 1:
                    j += 2 * nRows - 2;   
                else:
                    if k == 0: # 如果是奇數(shù)列
                        j += 2 * (nRows - 1 - i)
                        k = 1
                    else: # 如果是偶數(shù)列
                        j += 2 * i 
                        k = 0
                # 不能超過(guò)字符串的長(zhǎng)度
                if j < len(s):
                    result += s[j]  
            i += 1
        return(result)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容