美文网首页
337.House Robber III

337.House Robber III

作者: 格调七弦 | 来源:发表于2016-03-30 20:21 被阅读243次

House Robber III
第一次思考结果是直接将数的奇数层与偶数层分别求和,比大小得出结果:

class Solution {
public:
    void tranversal(bool layer,int& oValue,int& eValue,TreeNode* root)
    {
        if(root == NULL)
        {
            return;
        }
        if(layer)//奇数层
        {
            oValue +=root->val;
        }
        else
        {
            eValue +=root->val;
        }
        tranversal(!layer,oValue,eValue,root->left);
        tranversal(!layer,oValue,eValue,root->right);
    }
    int rob(TreeNode* root) {
        int oValue = 0;
        int eValue = 0;
        tranversal(true,oValue,eValue,root);
        return oValue > eValue? oValue:eValue;
    }
};

[4,1,null,2,null,3],面对这样一个测试,理所当然就错了。
换一个思路,如果将每层的和保存成一个数组,就转化为在不能有相邻位置同时被选取的情况下,求数组的最大和,并且该数组元素中没有负值。
OK,第二版:

class Solution {
public:
    void tranversal(int layer, vector<int>& buffer,TreeNode* root)
    {
        if(root == NULL)
        {
            return;
        }
        if(buffer.size() == layer)
        {
            buffer.push_back(0);
        }
        buffer[layer]+=root->val;
        tranversal(layer+1,buffer,root->left);
        tranversal(layer+1,buffer,root->right);
    }
    int rob(TreeNode* root) {
        vector<int> buffer;
        int layer = 0;
        tranversal(layer,buffer,root);
        buffer.push_back(0);
        buffer.push_back(0);
        buffer.push_back(0);
        int sum = 0;
        for(int i = 0; i < buffer.size() - 3;i+=2)
        {
            if(buffer[i] >= buffer[i+1] ||buffer[i] + buffer[i+2] >= buffer[i+1] + buffer[i+3])
            {
                sum+=buffer[i];
            }
            else
            {
                sum+=buffer[i+1];
                ++i;
            }
        }
        return sum;  
    }
};

[2,1,3,null,4],又错了。。
= =
一开始题意就想偏了,看来是某种遍历,之后在处理,想想。。
OH,看到提示标签了,原来是DFS,真的是蠢。
第三版:

class Solution {
public:
    map<TreeNode*,int> steal;
    map<TreeNode*,int> refuse;
    int rob(TreeNode* root) 
    {
        DFStranversal(root);
        return max(steal[root],refuse[root]);
    }
    void DFStranversal(TreeNode* root)
    {
        if(root == NULL) return;
        DFStranversal(root->left);
        DFStranversal(root->right);
        steal[root] = root->val + refuse[root->left] + refuse[root->right];
        refuse[root] = max(max(steal[root->left]+
                 steal[root->right],steal[root->left]+
                 refuse[root->right]),
                  max(refuse[root->left]+steal[root->right],
                  refuse[root->left]+refuse[root->right]));
    }
};

从根节点开始进行深度优先遍历,每个节点有小偷去偷和拒绝偷两种情况,应该采纳的情况是两者中的较大值。

相关文章

  • 337.House Robber III

    House Robber III第一次思考结果是直接将数的奇数层与偶数层分别求和,比大小得出结果: [4,1,nu...

  • 2019-04-07

    LeetCode 337. House Robber III Description The thief has ...

  • 动态十八:打家劫舍 III

    题目地址: https://leetcode-cn.com/problems/house-robber-iii/...

  • 打家劫舍系列 1,2,3

    打家劫舍3https://leetcode-cn.com/problems/house-robber-iii/su...

  • House Robber III

    题目来源还是房屋抢劫的问题,不过这次改成了二叉树抢劫。然后我不会!!!看了下答案,最简单的方法就是比较所有情况,深...

  • House Robber III

    问题描述 House Robber III一颗二叉树有n个节点,每个节点都有一个权值,现在要求你从中选出任意个节点...

  • DP真题

    骨骼清奇:LC 62LC 337 House Robber III LC 486 Predict the Win...

  • house-robber-iii

    这道题略有难度,题目链接。题目要求就是求一个二叉树所有节点数值的和的最大值,条件是有边连接的两个节点不能被同时选中...

  • 337. House Robber III

    题目 The thief has found himself a new place for his thieve...

  • Leetcode 337 - House Robber III

    题目: You are a professional robber planning to rob houses ...

网友评论

      本文标题:337.House Robber III

      本文链接:https://www.haomeiwen.com/subject/ackelttx.html