@chanvee
2014-12-21T16:50:21.000000Z
字数 5551
阅读 4232
LeetCode
Python
这个题的意思是将两个排序的链表合并为一个,链表的操作,比较简单,代码如下:
# 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)
将罗马数字转化为整数,只需要弄清楚罗马数字的规则即可,规则如下:
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)
这个题与上个题目相反,将整数转化为罗马数字。我的方法有点无耻,先建了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)
这个题的意思是比较两个版本号的大小,方法简单,用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)
判断一个整数是不是回文,并且不能利用额外的空间,方法就是每次判断最高位与最低位是否相同即可。代码如下:
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)
这个题有点不好理解,反正我是看了网上的意思才懂了,意思是比如从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)
判断给定的数独二维数组是否合法,我们只要弄清楚数独的规则就行:
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)
从链表中移除倒数第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的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])
按照题目给的意思进行字符串的映射,排列的形状就是由以前的一行变为类似于多个倒着的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)