LC medium.
这道题看上去简单，其实还是挺考基本功的。主要是hasNext的判断比较难写得很精简。大致意思是，如果j已经超出了这行的长度，那么久更新到新的不为空的一行去。
class Vector2D(object):
def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
self.i = 0
self.j = 0
self.vec2d = vec2d
def next(self):
"""
:rtype: int
"""
res = self.vec2d[self.i][self.j]
self.j += 1
return res
def hasNext(self):
"""
:rtype: bool
"""
while self.i < len(self.vec2d):
if self.j < len(self.vec2d[self.i]):
return True
self.j = 0
self.i += 1
return False
args = [[[],[3]]]
s = Vector2D(*args)
for i in range(9):
if s.hasNext():
ans = s.next()
print(ans)
然后这道题还可以用python的iterator来写。这个答案的discussion简直是iter的教科书！
class Vector2D(object):
def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
def get():
for array in vec2d:
for num in array:
yield num
self.iter = iter(get())
self.latest = next(self.iter, None)
def next(self):
"""
:rtype: int
"""
res = self.latest
self.latest = next(self.iter, None)
return res
def hasNext(self):
"""
:rtype: bool
"""
return self.latest != None
args = [[[],[3]]]
s = Vector2D(*args)
for i in range(9):
if s.hasNext():
ans = s.next()
print(ans)
P2. Mini Parser
哎呀这道题就是属于那种有点恶心的题目，感觉让我想起了当年的basic caculator。
哎呀妈哟，写死个人！
class Solution(object):
def deserialize(self, s):
"""
:type s: str
:rtype: NestedInteger
"""
stack, start = [], -1
stack.append(NestedInteger())
for i, c in enumerate(s):
if c == '[':
stack.append(NestedInteger())
elif c == ']':
if len(stack) > 1:
t = stack.pop()
stack[-1].add(t)
elif c in '1234567890' or c == '-':
if start == -1:
start = i
if i+1==len(s) or s[i+1] not in '1234567890':
stack[-1].add(NestedInteger(int(s[start:i + 1])))
start = -1
return stack[-1].getList()[0]
P3. Maximal Square
经典dp题目嘛。来来来，我们来再写一遍。科科。写得非常不clean。
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
dp = [[0]*len(matrix[0]) for _ in range(len(matrix))]
maxValue = 0
for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min([dp[i-1][j-1], dp[i-1][j], dp[i][j-1]]) + 1
maxValue = max(dp[i][j], maxValue)
return maxValue**2
args = [[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]]
s = Solution()
ans = s.maximalSquare(*args)
print(ans)
P4. Add Two Numbers
这倒题，感觉只是比较恶心。要学会处理有进位和两个linked list长短不一样的情况。
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = tmp = ListNode(-1)
carry = 0
while l1 and l2:
val = carry + l1.val + l2.val
carry = val//10
tmp.next = ListNode(val%10)
tmp = tmp.next
l1, l2 = l1.next, l2.next
rest = l1 or l2
while rest:
val = carry + rest.val
carry = val//10
tmp.next = ListNode(val%10)
tmp = tmp.next
rest = rest.next
if carry:
tmp.next = ListNode(1)
return head.next
a, b, c = ListNode(1), ListNode(2), ListNode(3)
a.next, b.next = b, c
s = Solution()
ans = s.addTwoNumbers(a, a)
print(ans.val)
print(ans.next.val)
这道题，我可是忘得一干二净。我只会用contains duplicate II方法去维护interval之间的数字，剩下的我基本就是暴力解了。
又看了一遍乐爷爷的solution。非常地巧妙，我们下面来讲一遍，为什么这么做。
首先这道题是需要我们找数组里连续长度为t的子数组里是否有相差少于k的pair。
所以第一步我们得按照顺序遍历数组， 然后我们要维护一个数据结构来保证在窗口滑动的时候，添加删除都是O（1）的。这里就不难想到我们要用hash来存。
巧妙的地方在于，hash的key是bucket的index，value是数字，而每个bucket最多只能放一个数字。在存数的时候只用检查相邻的bucket就行了。删数直接删O（1）。妈妈问我为什么跪着看代码！
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
if t < 0: return False
dic = {}
n = len(nums)
w = t + 1
for i in range(n):
index = nums[i] / w
if index in dic:
return True
if index - 1 in dic and abs(dic[index - 1] - nums[i]) < w:
return True
if index + 1 in dic and abs(dic[index + 1] - nums[i]) < w:
return True
dic[index] = nums[i]
if i >= k: del dic[nums[i - k] / w]
return False
s = Solution()
ans = s.containsNearbyAlmostDuplicate(*args)
print(ans)
这倒题太恶心了，我先留着哈。