2016年3月 – 第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代码：

/**
 * 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]));
    }
};

拓扑结构相同子树（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代码：

       //需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
            //如  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);
    }
};

shell sort 希尔排序

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

下面为实现的算法：

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;
		}
	}
}

月份：2016年3月

House Robber III

House Robber III

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

shell sort 希尔排序

nextval数组求法