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

LeetCode 题解三（python版）

LeetCode Python

Merge Two Sorted Lists

这个题的意思是将两个排序的链表合并为一个，链表的操作，比较简单，代码如下：

# 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

将罗马数字转化为整数，只需要弄清楚罗马数字的规则即可，规则如下：
1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
5. 在一个数的上面画一条横线，表示这个数扩大1000倍
这里第5条没有用，因为输入不会出现这种情况，那么只需按着这个编码规则即可，代码如下：

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

这个题与上个题目相反，将整数转化为罗马数字。我的方法有点无耻，先建了3各表：1-9, 10:10:20, 100:100:900,这样每次就只需要除完之后就可以从表里面提取，不用再去写一遍规则。代码如下：

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

这个题的意思是比较两个版本号的大小，方法简单，用split将字符串分割，然后依次比较大小即可。注意的特例是01 = 1，和1.0 = 1这两类例子，我们可以先把他们不起成为等长。代码如下：

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

这个题有点不好理解，反正我是看了网上的意思才懂了，意思是比如从1开始，因为只有1个1，所以第二个数就是11（表示1个1），第二个数有2个1，所以第三个数为21（表示2个1），第三个数有1个2,1个1，所以第四个数是（1211）以此类推，懂了意思就好做了。代码如下：

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....
接下来就简单了，遍历他的所有行和列以及九宫格，看是否已经存在相同的数字，如果存在则返回False，否则返回True。代码如下：

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

从链表中移除倒数第N个数。思想很简单我就不再赘述了，有一个问题是要想知道倒数，就要知道链表中总共有多少个元素，这里我是先遍历一遍得到长度，不知道有没有其他更好的办法。代码如下：

# 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

给定一个数字，将其转换为Excel的title，其实就相当于把一个数转化为26进制的数。代码如下：

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

按照题目给的意思进行字符串的映射，排列的形状就是由以前的一行变为类似于多个倒着的N这种形状的转换。它的转换规则如下：
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)