GG Easy
1 Island Perimeter
这道题我一年过后再来写，居然被当年的算法震惊了。大概思想就是如果我们找到一个1，那么我们就从这个1从4个方向开始DFS。
在dfs任何一个点的时候，如果没有上下左右哪个方向上没有1，那就说明这个方向是其中的一条边，那么我们就对边+1.
class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
self.cnt = 0
visited = set()
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
visited.add((i, j))
self.helper(i, j, visited, grid)
return self.cnt
return self.cnt
def helper(self, x, y, visited, grid):
for d, p in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
i, j = x+d, y+p
if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]==1:
if (i, j) not in visited:
visited.add((i, j))
self.helper(i, j, visited, grid)
else:
self.cnt += 1
2 Longest Uncommon Subsequence II
这道题真是神经病题目。大概思想就是，我把string按照他们的length sort一遍，然后从长到短一个个去判定，一旦找到一个string不是其他的subsequence。那么这个就是我要找的Longest subsequence。
class Solution(object):
def findLUSlength(self, strs):
"""
:type strs: List[str]
:rtype: int
"""
strs.sort(key = len, reverse = True)
for i in range(len(strs)):
if all(not self.isSubSeq(strs[i], strs[j]) for j in range(len(strs)) if i!=j):
return len(strs[i])
return -1
def isSubSeq(self, w1, w2):
if len(w1)>len(w2):
return False
index = 0
for c in w2:
if index<len(w1) and c == w1[index] :
index += 1
return index == len(w1)
3 Max Consecutive Ones II
这道题主要是最多出现过一个0，所以我们直接用两个pointer就行了。如果碰到第二个零的时候，就把start pointer更新到前一个0的后一位。连续的0的情况也能自动被handle。
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
pos = None
start = 0
res = 0
for i, val in enumerate(nums):
if val == 1:
res = max(res, i-start + 1)
else:
if pos is None:
pos = i
res = max(res, i-start + 1)
else:
start = pos+1
pos = i
return res
s = Solution()
print s.findMaxConsecutiveOnes([0, 0])
4 Find All Numbers Disappeared in an Array
这道题有点像find missing number。不过方法很巧妙，大概思想就是loop一遍list, 如果碰到一个数为n，然后我们就把这个array第n-1位的数翻转为负数。其实就是不浪费额外内存来把这个数字表示出来。最后再扫一遍处理后的array， 如果第i位的数字不是负的话。那么久说明这个index+1的数字没有出现过。因为怕重复翻转的情况，所以每次翻转数字都加abs再加负号。
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
for num in nums:
index = abs(num)-1
nums[index] = -abs(nums[index])
return [i+1 for i, num in enumerate(nums) if num>0]
5 Minimum Absolute Difference in BST
这道题目非常有意思。主要思想是我们每访问一个点的时候，我们想要知道这个点跟比他小的那个数，和比它大的那个数的距离是多少。所以跟Validate Binary Search Tree这道题的思想特别想，我们在递归的时候，就同时把这个相应node的left bound和right bound给传递下去。这样我们在traversal这个tree的时候就能够得到最短距离了。
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return -1
self.res = 1<<31
self.helper(root)
return self.res
def helper(self, root, left=-(1<<31 + 1), right=1<<31):
if not root:
return
self.res = min([self.res, abs(left-root.val), abs(right-root.val)])
if root.left:
self.helper(root.left, left, root.val)
if root.right:
self.helper(root.right, root.val, right)
我觉得这道题的难度应该至少到medium啊。其实不是很好写,两种方法：第一种方法：生成所有的时间，然后判断bit加起来是不是等于给的bit数。比较暴力，不过很好写。第二种方法：把给的bit数分配到各个位上来生成时间，有点像permutation的思想。需要一个dfs的helper function。如果要避免duplication其实不是很好写。需要把两个结合起来公用一个index。看我的代码就知道了。
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
res = []
self.dfs(num, 0, 0, res, 0)
return res
def dfs(self, n, h, m, res, index):
if not n:
if m<60 and h<12:
res.append(str(h)+':'+"0"*(m < 10)+str(m))
return
for i in range(index, 10):
if i<4:
self.dfs(n-1, h|(1<<i), m, res, i+1)
else:
offset = i-4
self.dfs(n-1, h, m|(1<<offset), res, i+1)