本文转载自
作业部落的chanvee.
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
将罗马数字转化为整数，只需要弄清楚罗马数字的规则即可，规则如下：
- 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
- 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
- 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
- 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
- 在一个数的上面画一条横线，表示这个数扩大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-9，既每一行没有重复的数字
- 每一列只包含1-9，即每一列没有重复的数字
- 每个小九宫格里面只包含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这种形状的转换。它的转换规则如下：
- 如果是第一行或者最后一行，那么从第一个数开始到下一个数每次相差
(2 * nRows - 2) - 对于其他行，这一行的数字的排列是奇数列和偶数列交替的，当然列号不一定是连续的，但是他们的列号肯定是奇偶交替的
- 对于奇数列，两个
相邻的之间相差2 * (nRows - 1 - i)这么多个数 - 对于偶数列，两个
相邻的之间相差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)
