Array & Strings
我一直觉得Array & Strings的题目是最烦的。因为不仅仅要考虑corner case。写起来还非常费力。
283 Move Zeroes
一开始写的办法真是笨，类似于冒泡排序的办法，不停的把数字往前面冒泡，这样sort完，0就在最后面了。 后来发现，其实只要把数字按照顺序移动到前面去，然后把后面的数全部制0就行了。
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
index = 1
while index<len(nums):
if nums[index-1] == 0:
tmpIndex = index
while tmpIndex != 0 and nums[tmpIndex-1] == 0:
nums[tmpIndex], nums[tmpIndex -1] = nums[tmpIndex - 1], nums[tmpIndex]
tmpIndex -= 1
index += 1
return nums
s = Solution()
print s.moveZeroes([0, 1, 0, 3, 12])
#Better Solution
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
pos = 0
for n in nums:
if n!=0:
nums[pos] = n
pos+=1
nums[pos:] = [0]*(len(nums)-pos)
s = Solution()
print s.moveZeroes([0, 1, 0, 3, 12])
68 Add Binary
这道题其实用python黑魔法一行就出来了。不过面试肯定不能这样。最后的写法还是类似于big number sum。
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
# print bin(int(a,2) + int(b,2))[2:]
a = list(a)[::-1]
b = list(b)[::-1]
if len(a)<len(b):
a, b = b, a
carry = 0
i = 0
while i<len(a):
bVal = int(b[i]) if i<len(b) else 0
curSum = bVal + int(a[i]) + carry
a[i] = str(curSum%2)
carry = curSum//2
i += 1
if carry:
a.append(str(carry))
return ''.join(a[::-1])
s = Solution()
print s.addBinary("11", "1")
350 Intersection of Two Arrays II
这道题除了用conter取巧以外，还可以先sort了，然后再用两个pointer来存结果。
import collections
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
c1 = collections.Counter(nums1)
c2 = collections.Counter(nums2)
c = c1 & c2
return [ k for k, v in c.items() for _ in range(v) ]
s = Solution()
s.intersect([1, 2, 2, 1], [2, 2])
15 3Sum
这道经典种的经典题目。其实可以用combination sum的套路来解。不过复杂度是O(n^3)，而且超时了。所以还是得用。sort()后，定点然后左右两个pointer来做。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
return self.helper(nums, [], 0, [])
def helper(self, nums, path, sum, res):
if len(path) == 3 and sum == 0:
res.append(path)
return
if not nums:
return
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:
continue
self.helper(nums[i+1:], path + [nums[i]], sum + nums[i], res)
return res
s = Solution()
print s.threeSum([-1, 0, 1, 2, -1, -4])
然后我们再用经典做法。我的建议是先写出不handle dup的，然后再一点一点往上加dedup。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
res = []
for i in range(len(nums)-2):
if i>0 and nums[i] == nums[i-1]: # dedup
continue
num = nums[i]
l, r = i+1, len(nums)-1
while l<r:
sum = num + nums[l] + nums[r]
if l>i+1 and nums[l]==nums[l-1]: # dedup
l += 1
elif sum == 0:
res.append([num, nums[l], nums[r]])
l, r = l+1, r-1
elif sum > 0:
r -= 1
else:
l += 1
return res
s = Solution()
print s.threeSum([-2,0,0,2,2])
125 Valid Palindrome
嗯。两个pointer.
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
l, r = 0, len(s)-1
while l <= r:
while l<r and not s[l].isalnum():
l += 1
while r>l and not s[r].isalnum():
r -= 1
if s[l].lower() == s[r].lower():
l += 1
r -= 1
else:
return False
return True
s = Solution()
print s.isPalindrome("P0")
Trapping Rain Water
我记得这道题，还有一个2D的版本。具体思想就是我们一直找那个最短的木板向里推进。然后存好外围最矮的那个。
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
l, r = 0, len(height) - 1
l_height, r_height = height[l], height[r]
res = 0
while l < r:
if height[l] <= height[r]:
l += 1
if height[l] < l_height:
res += l_height - height[l]
else:
l_height = height[l]
else:
r -= 1
if height[r] < r_height:
res += r_height - height[r]
else:
r_height = height[r]
return res