@chanvee 2014-12-21T08:50:21.000000Z 字数 5551 阅读 4171

# LeetCode 题解三（python版）

LeetCode Python

Markdown版请移步

## Merge Two Sorted Lists

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass 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

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
5. 在一个数的上面画一条横线，表示这个数扩大1000倍

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

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

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

class Solution:    # @return a boolean    def isPalindrome(self, x):        mode, result= 1, True        while x//mode >= 10: ## 相当于算出有多少位            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

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

1. 每一行只包含1-9，既每一行没有重复的数字
2. 每一列只包含1-9，即每一列没有重复的数字
3. 每个小九宫格里面只包含1-9....

class Solution:    # @param board, a 9x9 2D array    # @return a boolean    def isValidSudoku(self, board):        for i in range(9): # 行和列是否符合数独            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): # 判断九宫格是否有相同的数字            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): # 判断列表中是否有相同的数字        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

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass 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

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

1. 如果是第一行或者最后一行，那么从第一个数开始到下一个数每次相差（2 * nRows - 2）
2. 对于其他行，这一行的数字的排列是奇数列和偶数列交替的，当然列号不一定是连续的，但是他们的列号肯定是奇偶交替的
3. 对于奇数列，两个“相邻”的之间相差2 * (nRows - 1 - i)这么多个数
4. 对于偶数列，两个“相邻”的之间相差2 * (nRows - i)这么多个数

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: # 如果是奇数列                        j += 2 * (nRows - 1 - i)                        k = 1                    else: # 如果是偶数列                        j += 2 * i                         k = 0                # 不能超过字符串的长度                if j < len(s):                    result += s[j]              i += 1        return(result)

• 私有
• 公开
• 删除