March 2016 – Page 3 – 我的经验分享

House Robber III

1.题目告诉我们相邻的两个父子节点不能同时被偷取，求出最大能偷取的金额。

2.这个题目是典型的树形DP，我们定义了两个DP，一个是被偷取的DP1，一个是不偷取的DP2。然后进行深度优先搜索，计算每一个节点的DP1和DP2，最后输出根节点中DP1和DP2的较大者。

House Robber III

Difficulty: Medium

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

AC代码：
[c language=”++”]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
map<TreeNode*,int> dp1;
map<TreeNode*,int> dp2;
int rob(TreeNode* root) {
dfs(root);
return max(dp1[root],dp2[root]);
}
void dfs(TreeNode* root)
{
if(root == NULL) return;

dfs(root->left);
dfs(root->right);

//偷这个节点
dp1[root]=root->val+dp2[root->left]+dp2[root->right];
//不偷这个节点
dp2[root]=max(max(dp1[root->left]+dp1[root->right],dp2[root->left]+dp2[root->right]),
max(dp2[root->left]+dp1[root->right],dp1[root->left]+dp2[root->right]));
}
};
[/c]

拓扑结构相同子树（KMP应用）

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

解题思路：

1.我们可以对于A树的每一个节点，进行判断，看是否和B相等，但是这样的时间复杂度为O(M*N)，设A的节点数为M，B的节点数为N。

2.另外一种思路就是，我们先把两个树序列化，然后判断strA是否含有strB的子串，判断子串的时候，我们采用KMP算法，这样时间复杂度就可以降为O(M+N)。其中，我们需要采用前序遍历（或后序遍历），确保子树的序列化是连续的。中序遍历会由于插入中间值，导致序列化后不一致。

3.序列化的时候，我们需要对空的叶子节点进行插入特殊符号（数值）操作，这是用于判断只有一个叶子节点的节点的结构，如：

//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如–A—–A
//—/———-\
//–B———-B
//如树1，A的左节点为B，右节点为空
//树2，A的做节点为空，右节点为B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
AC代码：
[c language=”++”]
//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如 A A
// / \
// B B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断

/*
对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树
*/
//前序遍历+KMP
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
if (B == NULL) return true;
else if (A == NULL) return false;
vector<int> pattern;
vector<int> str;
dfs(A, str);
dfs(B, pattern);
if (str.size()<pattern.size()) return false;
//构建next数组
vector<int> next(pattern.size() + 1, 0);
for (int i = 1; i<pattern.size(); ++i)
{
int j = next[i];
while (j>0 && pattern[i] != pattern[j])
j = next[j];
if (pattern[i] == pattern[j])
next[i + 1] = j + 1;//求next[i+1]的值，所以比较的是p[i]和p[j]
}
//使用KMP
int j = 0;
for (int i = 0; i<str.size(); ++i)
{
while (j>0 && str[i] != pattern[j])
j = next[j];
if (str[i] == pattern[j])
j++;//比较下一个值
if (j == pattern.size())
{
//匹配到字串了，返回真
return true;
}
}
//没找到，false
return false;
}
//进行前序遍历
void dfs(TreeNode* root, vector<int>&preOrder)
{
if (root == NULL){
//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如 A A
// / \
// B B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
preOrder.push_back(INT_MAX);
return;
}
preOrder.push_back(root->val);
dfs(root->left, preOrder);
dfs(root->right, preOrder);
}
};
[/c]

shell sort 希尔排序

希尔排序的核心思想是，利用一个增量序列H[k]（大小为n），其中H[0]=1，对数组进行n次H[k]排序。每次H[k]排序，arr[H[k]]及其后面的元素分别有序地放置在arr[i-n*increment]中。

下面为实现的算法：

[c language=”++”]
void shellSort(vector<int>&arr)
{
//使用希尔增量序列,Hibbard增量序列为2^n-1
for (int increment = arr.size() / 2; increment >= 1; increment /= 2)
{
for (int i = increment; i < arr.size(); ++i)
{//把increment及后面的数,排序到 j-2I,j-I,j中。。。
int x = arr[i];
int j = i;
for (j = i; j >= increment; j -= increment)
{
if (x < arr[j – increment])//小于,则x应该前移
arr[j] = arr[j – increment];//把前面的数复制给j
else
break;//已经找到合适的位置
}
//把x放到合适的位置
arr[j] = x;
}
}
}
[/c]

Month: March 2016

House Robber III

House Robber III

拓扑结构相同子树（KMP应用）

shell sort 希尔排序

nextval数组求法