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

LeetCode 题解三(python版)

LeetCode Python


Markdown版请移步

Merge Two Sorted Lists


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

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. # @param two ListNodes
  8. # @return a ListNode
  9. def mergeTwoLists(self, l1, l2):
  10. result = ListNode(0)
  11. cur = result
  12. while l1 or l2:
  13. tmp = ListNode(0)
  14. if l1 and not l2:
  15. tmp = l1
  16. l1 = l1.next
  17. elif l2 and not l1:
  18. tmp = l2
  19. l2 = l2.next
  20. else:
  21. if l1.val < l2.val:
  22. tmp = l1
  23. l1 = l1.next
  24. else:
  25. tmp = l2
  26. l2 = l2.next
  27. cur.next, cur = tmp, tmp
  28. return(result.next)

Roman to Integer


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

  1. class Solution:
  2. # @return an integer
  3. def romanToInt(self, s):
  4. result = 0
  5. for i in range(len(s)):
  6. if s[i] == 'M':
  7. result += 1000
  8. elif s[i] == 'D':
  9. result += 500
  10. elif s[i] == 'C':
  11. if i + 1 < len(s) and (s[i+1] == 'M' or s[i+1] == 'D'):
  12. result -= 100
  13. else:
  14. result += 100
  15. elif s[i] == 'L':
  16. result += 50
  17. elif s[i] == 'X':
  18. 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'):
  19. result -= 10
  20. else:
  21. result += 10
  22. elif s[i] == 'V':
  23. result += 5
  24. else:
  25. 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'):
  26. result -= 1
  27. else:
  28. result += 1
  29. return(result)

Integer to Roman


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

  1. class Solution:
  2. # @return a string
  3. def intToRoman(self, num):
  4. LesTen = ['I','II','III','IV','V','VI','VII','VIII','IX']
  5. LesHun = ['X','XX','XXX','XL','L','LX','LXX','LXXX','XC']
  6. LesThu = ['C','CC','CCC','CD','D','DC','DCC','DCCC','CM']
  7. result = []
  8. while num > 0:
  9. if num // 1000:
  10. result.append('M'*(num // 1000))
  11. num %= 1000
  12. elif num // 100:
  13. result.append(LesThu[num//100 - 1])
  14. num %= 100
  15. elif num // 10:
  16. result.append(LesHun[num//10 -1])
  17. num %= 10
  18. else:
  19. result.append(LesTen[num -1])
  20. num //= 10
  21. result = ''.join(result)
  22. return(result)

Compare Version Numbers


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

  1. class Solution:
  2. # @param a, a string
  3. # @param b, a string
  4. # @return a boolean
  5. def compareVersion(self, version1, version2):
  6. if version1 == version2:
  7. return(0)
  8. ver1 = version1.split('.')
  9. ver2 = version2.split('.')
  10. flag = 1
  11. for i in range(abs(len(ver1)-len(ver2))):
  12. if len(ver1) <= len(ver2):
  13. ver1.append('0')
  14. else:
  15. ver2.append('0')
  16. for i in range(min(len(ver1), len(ver2))):
  17. if int(ver1[i]) > int(ver2[i]):
  18. flag = 0
  19. return(1)
  20. if int(ver1[i]) < int(ver2[i]):
  21. flag = 0
  22. return(-1)
  23. if flag:
  24. if len(ver1) == len(ver2):
  25. return(0)
  26. if len(ver1) < len(ver2):
  27. return(-1)
  28. if len(ver1) > len(ver2):
  29. return(1)

Palindrome Number


判断一个整数是不是回文,并且不能利用额外的空间,方法就是每次判断最高位与最低位是否相同即可。代码如下:

  1. class Solution:
  2. # @return a boolean
  3. def isPalindrome(self, x):
  4. mode, result= 1, True
  5. while x//mode >= 10: ## 相当于算出有多少位
  6. mode *= 10
  7. while x:
  8. if x // mode != x % 10:
  9. result = False
  10. return(result)
  11. x -= mode*(x//mode)
  12. x //= 10
  13. mode //= 100
  14. return(result)

Count and Say


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

  1. class Solution:
  2. # @return a string
  3. def countAndSay(self, n):
  4. if n == 1:
  5. return('1')
  6. if n == 2:
  7. return('11')
  8. result = []
  9. s = '11'
  10. for i in range(n-2):
  11. s = self.Trans(s)
  12. result = ''.join(s)
  13. return(result)
  14. def Trans(self, s):
  15. result = []
  16. tmp, count = s[0], 1
  17. for i in range(1,len(s)):
  18. if s[i] == s[i-1]:
  19. count += 1
  20. if i == len(s)-1:
  21. result.append(str(count)+s[i-1])
  22. else:
  23. result.append(str(count)+s[i-1])
  24. tmp, count = s[i], 1
  25. if i == len(s)-1:
  26. result.append(str(count)+s[i])
  27. result = ''.join(result)
  28. return(result)

Valid Sudoku


判断给定的数独二维数组是否合法,我们只要弄清楚数独的规则就行:
1. 每一行只包含1-9,既每一行没有重复的数字
2. 每一列只包含1-9,即每一列没有重复的数字
3. 每个小九宫格里面只包含1-9....
接下来就简单了,遍历他的所有行和列以及九宫格,看是否已经存在相同的数字,如果存在则返回False,否则返回True。代码如下:

  1. class Solution:
  2. # @param board, a 9x9 2D array
  3. # @return a boolean
  4. def isValidSudoku(self, board):
  5. for i in range(9): # 行和列是否符合数独
  6. tmp = []
  7. tmp1 = []
  8. for j in range(9):
  9. tmp.append(board[i][j])
  10. tmp1.append(board[j][i])
  11. if self.isnodifferent(tmp) == False or self.isnodifferent(tmp1) == False:
  12. return(False)
  13. for i in range(0,9,3): # 判断九宫格是否有相同的数字
  14. for j in range(0,9,3):
  15. tmp = []
  16. tmp.append(board[i][j])
  17. tmp.append(board[i][j+1])
  18. tmp.append(board[i][j+2])
  19. tmp.append(board[i+1][j])
  20. tmp.append(board[i+1][j+1])
  21. tmp.append(board[i+1][j+2])
  22. tmp.append(board[i+2][j])
  23. tmp.append(board[i+2][j+1])
  24. tmp.append(board[i+2][j+2])
  25. if not self.isnodifferent(tmp):
  26. return(False)
  27. return(True)
  28. def isnodifferent(self, s): # 判断列表中是否有相同的数字
  29. while '.' in s:
  30. s.remove('.')
  31. if s == []:
  32. return(True)
  33. flag = 0
  34. tmp = []
  35. tmp.append(s[0])
  36. for i in range(1, len(s)):
  37. if s[i] in tmp:
  38. flag = 1
  39. break
  40. tmp.append(s[i])
  41. if flag:
  42. return(False)
  43. else:
  44. return(True)

Remove Nth Node From End of List


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

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. # @return a ListNode
  8. def removeNthFromEnd(self, head, n):
  9. tmp = head
  10. L = 0
  11. while tmp:
  12. L += 1
  13. tmp = tmp.next
  14. if n == L:
  15. return(head.next)
  16. tmp = head
  17. for i in range(L):
  18. if i == L - n -1:
  19. tmp.next = tmp.next.next
  20. break
  21. tmp = tmp.next
  22. return(head)

Excel Sheet Column Title


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

  1. class Solution:
  2. # @return a string
  3. def convertToTitle(self, num):
  4. dic = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  5. result = ''
  6. while num:
  7. result = result + dic[(num-1)%26]
  8. num = (num - 1) // 26
  9. return(result[::-1])

ZigZag Conversion


按照题目给的意思进行字符串的映射,排列的形状就是由以前的一行变为类似于多个倒着的N这种形状的转换。它的转换规则如下:
1. 如果是第一行或者最后一行,那么从第一个数开始到下一个数每次相差(2 * nRows - 2)
2. 对于其他行,这一行的数字的排列是奇数列和偶数列交替的,当然列号不一定是连续的,但是他们的列号肯定是奇偶交替的
3. 对于奇数列,两个“相邻”的之间相差2 * (nRows - 1 - i)这么多个数
4. 对于偶数列,两个“相邻”的之间相差2 * (nRows - i)这么多个数
根据上面的规则我们就可以对其进行转化了,代码如下:

  1. class Solution:
  2. # @return a string
  3. def convert(self, s, nRows):
  4. result = ''
  5. if s == '' or nRows <= 1:
  6. return(s)
  7. i = 0
  8. while(i < len(s) and i < nRows):
  9. j = i
  10. result += s[j]
  11. k = 0
  12. while j < len(s):
  13. # 如果是第一行或最后一行
  14. if i == 0 or i == nRows - 1:
  15. j += 2 * nRows - 2;
  16. else:
  17. if k == 0: # 如果是奇数列
  18. j += 2 * (nRows - 1 - i)
  19. k = 1
  20. else: # 如果是偶数列
  21. j += 2 * i
  22. k = 0
  23. # 不能超过字符串的长度
  24. if j < len(s):
  25. result += s[j]
  26. i += 1
  27. return(result)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注