LintCode-打劫房屋I、 II（环状数据的处理）、III
I
描述
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
样例
给定 [3, 8, 4], 返回 8.
挑战
O(n) 时间复杂度 且 O(1) 存储。
代码
class Solution:
"""
@param A: An array of non-negative integers
@return: The maximum amount of money you can rob tonight
"""
def houseRobber(self, A):
# write your code here
dp = [0 for i in range(len(A))]
if len(A) == 0:
return 0
dp[0] = A[0]
if len(A) == 1:
return dp[0]
dp[1] = A[1]
if len(A) == 2:
return max(dp[0], dp[1])
for i in range(2, len(A)):
dp[i] = max(dp[i-2]+A[i], dp[i-1])
return dp[-1]
常规的求最大小动态规划。
题目来源
https://www.lintcode.com/problem/house-robber/description
II
描述
在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
这题是House Robber的扩展，只不过是由直线变成了圈
样例
给出nums = [3,6,4], 返回 6， 你不能打劫3和4所在的房间，因为它们围成一个圈，是相邻的．
代码
class Solution:
"""
@param nums: An array of non-negative integers.
@return: The maximum amount of money you can rob tonight
"""
def houseRobber2(self, nums):
# write your code here
n = len(nums)
if n <= 0:
return 0
elif n <= 3:
return max(nums)
new_nums = nums[:n-1]
result = self.houseRobber(new_nums)
new_nums = nums[1:]
result = max(result, self.houseRobber(new_nums))
return result
def houseRobber(self, A):
# write your code here
dp = [0 for i in range(len(A))]
dp[0] = A[0]
dp[1] = max(A[0], A[1])
for i in range(2, len(A)):
dp[i] = max(dp[i-2]+A[i], dp[i-1])
return dp[-1]
解决环状结构数据其实也很容易，只需要“掐头”、“去尾”分成两个数据集合分别按照直线的方法处理即可，因为这样的情况下头和尾是不能相遇的，所以，就模拟了头尾相连不可以同时选的情况。
题目来源
https://www.lintcode.com/problem/house-robber-ii/description
III
描述
在上次打劫完一条街道之后和一圈房屋之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子组成的区域比较奇怪，聪明的窃贼考察地形之后，发现这次的地形是一颗二叉树。与前两次偷窃相似的是每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。
算一算，如果今晚去打劫，你最多可以得到多少钱，当然在不触动报警装置的情况下。
这题是House Robber和House Robber II的扩展，只不过这次地形由直线和圈变成了二叉树
样例
3
/ \
2 3
\ \
3 1
窃贼最多能偷窃的金钱数是 3 + 3 + 1 = 7.
3
/ \
4 5
/ \ \
1 3 1
窃贼最多能偷窃的金钱数是 4 + 5 = 9.
代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: The maximum amount of money you can rob tonight
"""
def houseRobber3(self, root):
# write your code here
self.Globals = dict([])
return self.Dfs(root)
def Dfs(self, root):
if root == None:
return 0
if self.Globals. __contains__(root):
return self.Globals[root]
val = 0
if root.left != None:
val += self.Dfs(root.left.left) + self.Dfs(root.left.right)
if root.right != None:
val += self.Dfs(root.right.left) + self.Dfs(root.right.right)
value = max(root.val+val, self.Dfs(root.left)+self.Dfs(root.right))
self.Globals[root] = value
return value
遍历数据的方式还是DFS，值得注意的是， 父节点取了，就只能取子节点的子节点，然后用他们的和，与子节点对比记录最大值，为何用到DP，是为了防止搜索重复的节点，因为很显然
val += self.Dfs(root.left.left) + self.Dfs(root.left.right)
value = max(root.val+val, self.Dfs(root.left)+self.Dfs(root.right))
肯定会有节点重复。
另外值得一提的是，dict的keys、vals都可以是值、字符串、对象。这个在以前写的OBJ轮子里，是用过的。
另外python2中的dict.has_key(key)方法在python3中更新为了dict.contains(key)方法。
#Python 3.X 里不包含 has_key() 函数，被 __contains__(key) 替代:
dict3 = {'name':'z','Age':7,'class':'First'};
print("Value : ",dict3.__contains__('name'))
print("Value : ",dict3.__contains__('sex'))
执行结果：
Value : True
Value : False
题目来源
https://www.lintcode.com/problem/house-robber-iii/description
