12、12. Integer to Roman
将整数转换为罗马表示
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
roman = [
['','I','II','III','IV','V','VI','VII','VIII','IX'],
['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'],
['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'],
['','M','MM','MMM']]
s = []
i = 0
s_roman = ''
while num != 0:
number = num % 10
num //= 10
s.append(roman[i][number])
i += 1
s.reverse()
for item in s:
s_roman += item
return s_roman
if __name__ == '__main__':
solution = Solution()
print solution.intToRoman(1910)
用了个最笨的办法，一个个查表。不过效率比较高，94%
class Solution:
# @return a string
def intToRoman(self, num):
numeral_map = {1: "I", 4: "IV", 5: "V", 9: "IX", 10: "X", 40: "XL", 50: "L", 90: "XC", 100: "C", 400: "CD", 500: "D", 900: "CM", 1000: "M"}
keyset, result = sorted(numeral_map.keys()), ""
for key in reversed(keyset):
while num / key > 0:
num -= key
result += numeral_map[key]
return result
为什么别人的这么简洁，反思。不过效率不是很高。
14. Longest Common Prefix (easy)
Write a function to find the longest common prefix string amongst an array of strings.
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
length = len(strs)
if length == 0:
return ''
minlen = min(len(str) for str in strs)
for i in xrange(minlen):
for item in strs[1:]:
if item[i] != strs[0][i]:
return strs[0][:i]
return strs[0][:minlen]
if __name__ == '__main__':
solution = Solution()
print solution.longestCommonPrefix(['abcd','abcefg','ab'])
print solution.longestCommonPrefix(['a','b'])
别人的程序：
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
for i in xrange(len(strs[0])):
for string in strs[1:]:
if i >= len(string) or string[i] != strs[0][i]:
return strs[0][:i]
return strs[0]
效率还是自己比较高，但是自己还是不够简洁。
15. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
看起来有点意思，不要使用暴力法。化解为twosum问题，给定一个数a，找到两个数和为-a,先排序，从两边往中间找，如何简化下面程序。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
#print nums
length = len(nums)
i = 0
result = []
while nums[i] <= 0 and i < length - 2:
if i > 0 and nums[i] == nums[i-1]:
i += 1
continue
result = self.twosum(-nums[i], nums[i+1:], result)
i += 1
return result
def twosum(self,num,L,result):
index = len(L) - 1
while L[index] >= 0 and index >= 0:
if L[index] >= num:
pre = 0
while L[pre] <= 0 and pre < index:
if L[pre] + L[index] == num :
result.append([-num,L[pre],L[index]])
break
elif L[pre] + L[index] > num:
break
else:
pre += 1
if L[index] < num:
k = index - 1
while L[k] > 0 and k >= 0:
if L[k] + L[index] == num:
result.append([-num, L[k], L[index]])
break
elif L[k] + L[index] < num:
break
else:
k -= 1
index -= 1
while L[index] == L[index+1] and index >= 0:
index -= 1
return result
if __name__ == '__main__':
solution = Solution()
#print solution.twosum(4,[-1,1,2,2,3,4])
print solution.threeSum([0,0,0,0])
print solution.threeSum([-3,-2,-1,1,2,3,4])
上述为自己写的程序，最后超时了，可能是因为调用函数开销比较大。但也确实做了一些优化，如循环次数。
这个问题比较重要，需要认真理解，考虑细节比较多。如对[-1，-1，0，1，2，4]如何避免出现重复项。
参考
运行下面的也超时了，真是尴尬了。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# Sorted array can save a lot of time
nums.sort()
result = []
i = 0
while i < len(nums) - 2:
j = i + 1
k = len(nums) - 1
while j < k:
l = [nums[i], nums[j], nums[k]]
if sum(l) == 0:
result.append(l)
j += 1
k -= 1
# Ignore repeat numbers
while j < k and nums[j] == nums[j - 1]: #去重复项
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
elif sum(l) > 0:
k -= 1
else:
j += 1
i += 1
# Ignore repeat numbers
while i < len(nums) - 2 and nums[i] == nums[i - 1]: #去重复项
i += 1
return result
if __name__ == "__main__":
assert Solution().threeSum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
参考二
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
res = []
if len(num) < 3:
return res
for i in xrange(len(num)-2):
if i > 0 and num[i-1] == num[i]:
continue
target = -num[i]
j, k = i+1, len(num) - 1
while j < k:
if j > i+1 and num[j] == num[j-1]:
j += 1
continue
if num[j] + num[k] > target:
k -= 1
elif num[j] + num[k] < target:
j += 1
else:
res.append([num[i], num[j], num[k]])
j, k = j + 1, k - 1
return res
16、3sum closeset
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
if len(nums) < 3:
return -1
clos = 1000000
for i in xrange(len(nums)-2):
if i > 0 and nums[i - 1] == nums[i]:
continue
j, k = i + 1, len(nums) - 1
while j < k:
if j > i + 1 and nums[j] == nums[j - 1]:
j += 1
continue
sume = nums[i] + nums[j] + nums[k]
if abs(sume - target) < abs(clos-target):
clos = sume
if sume > target:
k -= 1
elif sume < target:
j += 1
else:
return target
return clos
if __name__ == '__main__':
solution = Solution()
print solution.threeSumClosest([1,1,-1,-1,3],-1)
print solution.threeSumClosest([-3,-2,-1,1,2,3,4],6)
这个题花了很多不必要的时间，关键就是思路不够清晰，和之前求最大水容量基本完全一样。
17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
这个题不算难，但自己由于经验不足很容易转不过弯来，总是想要用多少个for循环，可是又不知道有多少层循环。
深度优先算法
class Solution:
# @return a list of strings, [s1, s2]
def letterCombinations(self, digits):
def dfs(num, string, res):
if num == length:
res.append(string)
return
for letter in dict[digits[num]]:
dfs(num+1, string+letter, res)
dict = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']
}
res = []
length = len(digits)
dfs(0, '', res)
return res
递归，99%，惊呆了
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == '':
return []
self.DigitDict=[' ','1', "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = ['']
for d in digits:
res = self.letterCombBT(int(d),res)
return res
def letterCombBT(self, digit, oldStrList):
return [dstr+i for i in self.DigitDict[digit] for dstr in oldStrList]
自己的方法，96%，也很不错
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
dict = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
if digits == '':
return []
res, temp = [''], []
for i in digits[::-1]: # 将digits反转
for item in dict[int(i)]:
for it_em in res:
temp.append(item + it_em)
res = temp
temp = []
return res
if __name__ == '__main__':
solution = Solution()
#print solution.twosum(4,[-1,1,2,2,3,4])
print solution.letterCombinations('23')
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.res = []
if len(nums) < 4:
return []
nums.sort()
for i in range(len(nums)-3):
if i > 0 and nums[i-1] == nums[i]:
continue
tar = target - nums[i]
self.threeSum(nums[i+1:],tar,nums[i])
return self.res
def threeSum(self, num,tar,item):
for i in xrange(len(num)-2):
if i > 0 and num[i-1] == num[i]:
continue
target = tar-num[i]
j, k = i+1, len(num) - 1
while j < k:
if j > i+1 and num[j] == num[j-1]:
j += 1
continue
if num[j] + num[k] > target:
k -= 1
elif num[j] + num[k] < target:
j += 1
else:
self.res.append([item, num[i], num[j], num[k]])
j, k = j + 1, k - 1
在3sum的基础上改进而得，但是效率有点不高，才41%
19、Remove Nth Node From End of List
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
这个算是很基本的链表删除问题，换了个提法，就是删除倒数第几个，下面的程序还有很多不足，为最一般写法，一是判断是否为只有一个元素，二是判断删除的是否是链表首元素
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
p = head
length = 0
while p != None:
length += 1
p = p.next
if length == 1:
return None
p = head
current = head.next
if length - n != 0:
for i in range(length - n -1):
current = current.next
p = p.next
p.next = current.next
else:
head = head.next
return head
class Solution:
# @return a ListNode
def removeNthFromEnd(self, head, n):
dummy = ListNode(-1)
dummy.next = head
slow, fast = dummy, dummy
for i in xrange(n):
fast = fast.next
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return dummy.next
上面程序比较简单明了，引入一个虚拟头节点，避免了判断删除首元素，而且只遍历一次链表。
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
这个题算是比较熟悉，之前有遇到，主要思路为
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
l = []
match = {'(': ')', '[': ']', '{': '}'}
if s == '':
return False
for char in s:
if char in '([{':
l.append(char)
else:
if l == [] or match[l.pop()] != char:
return False
return l == []
21、Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = ListNode(-1)
current, pre = dummy, dummy
while l1 and l2:
if l1.val < l2.val:
current.next = ListNode(l1.val)
l1 = l1.next
else:
current.next = ListNode(l2.val)
l2 = l2.next
current = current.next
if l1 != None:
current.next = l1
if l2 != None:
current.next = l2
return pre.next
简单，没时间解释了，没上车也不等了。
22、Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
给定n对括号，生成所有匹配好的组合。
class Solution:
# @param an integer
# @return a list of string
def gen(self, s, leftParenNum, rightParenNum):
if leftParenNum == rightParenNum == Solution.n:
Solution.res.append(s)
return
if leftParenNum < Solution.n:
self.gen(s + '(', leftParenNum + 1, rightParenNum)
if rightParenNum < leftParenNum <= Solution.n:
self.gen(s + ')', leftParenNum, rightParenNum + 1)
return
def generateParenthesis(self, n):
Solution.n = n
Solution.res = []
self.gen('', 0, 0)
return Solution.res
class Solution:
# @param an integer
# @return a list of string
# @draw a decision tree when n == 2, and you can understand it!
def helpler(self, l, r, item, res):
if r < l:
return
if l == 0 and r == 0:
res.append(item)
if l > 0:
self.helpler(l - 1, r, item + '(', res)
if r > 0:
self.helpler(l, r - 1, item + ')', res)
def generateParenthesis(self, n):
if n == 0:
return []
res = []
self.helpler(n, n, '', res)
return res
递归的方法好强大，快点理解。DFS
26. Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
last_item = nums[0]
length = 1
for item in nums[1:]:
if item == last_item:
continue
else:
last_item = item
length += 1
nums[length-1] = last_item
nums = nums[:length]
return length
这题不仅仅是要返回不重复的数组长度，还要将原来的数组变为不重复。
27、Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
i = 0
if not nums:
return 0
for item in nums:
if item == val:
continue
else:
nums[i] = item
i += 1
nums = nums[:i]
return i
def removeElement1(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
i, last = 0, len(nums) - 1
while i <= last:
if nums[i] == val:
nums[i], nums[last] = nums[last], nums[i]
last -= 1
else:
i += 1
return last + 1
下面是别人的思路，但是发现性能都差不多。
