精选文章 打家劫舍系列: 198.打家劫舍 213.打家劫舍2 337.打家劫舍3

打家劫舍系列: 198.打家劫舍 213.打家劫舍2 337.打家劫舍3

作者:hbhhhxs 时间: 2020-08-05 11:33:53
hbhhhxs 2020-08-05 11:33:53

198.打家劫舍1

线性的dp,终于可以用到我自己的思路了,f[i]表示偷第i家所能得到的最大金币,那么它必然不能偷第i-1家,即从f[i-2]转移过来,但是我也可以不偷i-2,所以可以从f[i-3]转移过来,但是我不能不偷i-3了,因为中间隔了3个的话,必然能在中间再偷一个,(假设数据都是正数),所以自然而然想到转移方程 f[i]=max(f[i-2],f[i-3])+nums[i-3];最后答案一定在最后两个f中,因为再往前一个,必然能偷最后一个。

class Solution {
public:
    int rob(vector& nums) {
        if (nums.size()==0) return 0;
        int n=nums.size();
        vector f(n+10,0);
        //int ans=0;
        for (int i=0+3;i

213.打家劫舍2

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃,因此可以把此环状排列房间问题约化为两个单排排列房间子问题:

在不偷窃第一个房子的情况下(即 nums[1:]),最大金额是 p_1
在不偷窃最后一个房子的情况下(即 nums[:n-1]),最大金额是 p_2
综合偷窃最大金额: 为以上两种情况的较大值,即 max(p1,p2) 。
下面的任务则是解决 单排排列房间(即 198. 打家劫舍) 问题。

class Solution {
public:
    int rob(vector& nums) {
        if (nums.size()==0) return 0;
        int n=nums.size();
        if (n==1) return nums[0];
        if (n==2) return max(nums[0],nums[1]);
        if (n==3) return max(max(nums[0],nums[1]),nums[2]);
        vector f(n+10,0);
        int ans=0;
        //偷第一家,不偷最后一家即[0..n-2]
        for (int i=0+3;i

有一个解题思路跟我是一样的,感觉写的比我好看点。。

https://leetcode-cn.com/problems/house-robber-ii/solution/213-c-shuang-100-da-jia-jie-she-by-smart_shelly/

 

337.打家劫舍3

树型的dp?一开始我以为小偷是不能回头的,那我直接把这棵树放到数组上f[i]=max(f[i/2/2],f[i/2/2/2])+v[i];就ok了,写完发现这小偷还真贪啊,还走回头路的,那就必须遍历这整棵树了,用了dfs,但是卡在第123个测试点了,于是想用记忆化优化来着,但是状态(TreeNode* tn,int flag)不好表示啊,偷偷看了一眼题解,一般都是直接hashmap了一个状态TreeNode* tn,那么他们都不用记录状态flag的嘛,发现他们是另外一种思路,即

打不打劫根节点,影响了打劫一棵树的收益:
    打劫根节点,则不能打劫左右子节点,但是能打劫左右子节点的四个子树。
    不打劫根节点,则能打劫左子节点和右子节点,收益是打劫左右子树的收益之和。

这样的话确实记录一个状态TreeNode* tn就行了,但我的思路是通过标记当前节点是否偷来递归左右子树,不涉及孙子辈的。

/**
 * 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:
    int dg(TreeNode* root,int flag)
    {
        if (root==NULL) return 0; 
        if (flag==1)
        {
            int ans=dg(root->left,0)+dg(root->right,0);
            return ans;
        }
        else
        {
            int ans1=dg(root->left,0)+dg(root->right,0);
            int ans2=dg(root->left,1)+dg(root->right,1)+root->val;
            return max(ans1,ans2);
        }

    }
    int rob(TreeNode* root) {
        if (root==NULL) return 0;
        return max(dg(root,1),dg(root,0));
    }
};

但是这样的编码,卡在了第123个测试点,

打家劫舍系列:    198.打家劫舍    213.打家劫舍2    337.打家劫舍31

于是继续看题解找优化,看到了一个可行的优化,即我自己也发现,是存在很多重复的递归的,比如说int ans1=dg(root->left,0)+dg(root->right,0);这句话,几乎每个节点都会需要重新计算不偷当前节点的情况。于是改进方向是一次遍历的时候,把偷与不偷都计算出来,然后保存下来,返回给当前节点随意调用。

class Solution {
public:
    vector dg(TreeNode* tn)
    {
        vector ans(2,0);
        if (tn==NULL) return ans; 

        vector left=dg(tn->left);
        vector right=dg(tn->right);
        
        ans[0]=max(left[0],left[1])+max(right[0],right[1]);
        ans[1]=left[0]+right[0]+tn->val;
        
        return ans;
    }

    int rob(TreeNode* root) {
        vector ans=dg(root);
        return max(ans[0],ans[1]);
    }
};

这边我们要注意返回类型vector的风险

一是如果vector的内容不是基本数据类型的话,需要自己写拷贝构造函数,否则只会进行浅拷贝。

二是因为会进行一个拷贝过程,如果vector的数据非常多的话,会导致效率降低。//所以最好的方式还是通过传入vector的引用作为参数来调用。

三是这种方式成功是因为函数返回时会产生一个临时对象,return后用的是这个临时对象,原来的局部变量已经释放掉了。但要注意g++编译的优化机制可能会导致不产生这个临时对象,然后出错。我是在linux上发现了这个问题,看到https://www.veaxen.com/%E5%A4%8D%E6%9D%82%E7%9A%84c%EF%BC%8C%E5%BD%93%E5%87%BD%E6%95%B0%E8%BF%94%E5%9B%9E%E5%AF%B9%E8%B1%A1%E5%88%B0%E5%BA%95%E5%8F%91%E7%94%9F%E4%BA%86%E4%BB%80%E4%B9%88%EF%BC%9F.html这篇文章才知道编译环境也会使return结果不同。

转自这篇博客的评论讨论:https://blog.csdn.net/neverever01/article/details/80744148

所以,vector不好用,我们还有一招是老办法用数组指针传递,详见

https://blog.csdn.net/weixin_41232202/article/details/90368296

class Solution {
public:
    int * dg(TreeNode* tn)
    {
        int * ans=new int[2]{0,0};
        if (tn==NULL) return ans; 

        int * left=dg(tn->left);
        int * right=dg(tn->right);
        
        ans[0]=max(left[0],left[1])+max(right[0],right[1]);
        ans[1]=left[0]+right[0]+tn->val;
        
        return ans;
    }

    int rob(TreeNode* root) {
        int * ans=dg(root);
        return max(ans[0],ans[1]);
    }
};

降低了内存消耗,但是执行时间还是只有50%,先这样吧,找个机会再改进一下,看看树型dp怎么写的。

好吧,看了一眼官方题解,这就是树型dp

树形DP有别于常规DP,它不在迭代中“填表格”,是在递归中“填表格”。
这道题的二维矩阵其实是:
dp[root][0]:打劫以 root 为根节点的子树,并且不打劫 root 节点的最大收益
dp[root][1]:打劫以 root 为根节点的子树,并且打劫 root 节点的最大收益
在分析时,注意 root 节点和子节点相互冲突的关系。

具体看:https://leetcode-cn.com/problems/house-robber-iii/solution/si-chong-xie-fa-di-gui-ji-yi-hua-di-gui-shu-xing-d/

还有一种可以像python返回元组一样,c++结构体有{}这种写法:

struct SubtreeStatus {
    int selected;
    int notSelected;
};

class Solution {
public:
    SubtreeStatus dfs(TreeNode* o) {
        if (!o) {
            return {0, 0};
        }
        auto l = dfs(o->left);
        auto r = dfs(o->right);
        int selected = o->val + l.notSelected + r.notSelected;
        int notSelected = max(l.selected, l.notSelected) + max(r.selected, r.notSelected);
        return {selected, notSelected};
    }

    int rob(TreeNode* o) {
        auto rootStatus = dfs(o);
        return max(rootStatus.selected, rootStatus.notSelected);
    }
};

执行时间达到了90%。。。这大概就是,技巧吧。

至此,打家劫舍问题告一段落。

to be continued......

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:Set和multiset容器中常用函数的使用

下一篇:MyOS 之 软盘读取

您可能感兴趣

  • 引用 孙悟空的师傅菩提祖师的真实真份和镇元大仙辈份排名+四大灵猴

    引用 月明居士 的 孙悟空的师傅菩提祖师的真实真份和镇元大仙辈份排名 http://club.pchome.net/thread_1_15_1316497.html 原作者:再续无尽爱 bobby520ya 大家都看过《西游记》其中传授孙悟空本领的师父菩提祖师,此人名为菩提,(佛界名称)身着道服(还开了个道场)似佛非佛,似道却又通佛,在电视中并没有诸多说名其中身份和本领的描述,《西游记》里的...

  • HP大中华区总裁孙振耀退休十五天后九大感言(转)

    一、关于工作与生活   我有个有趣的观察,外企公司多的是25-35岁的白领,40岁以上的员工很少,二三十岁的外企员工是意气风发的,但外企公司40岁附近的经理人是很尴尬的。我见过的40岁附近的外企经理人大多在一直跳槽,最后大多跳到民企,比方说,唐骏。外企员工的成功很大程度上是公司的成功,并非个人的成功,西门子的确比国美大,但并不代表西门子中国经理比国美的老板强,甚至可以说差得很远。而进外企的人...

  • HP孙振耀退休感言

    一、关于工作与生活      我有个有趣的观察,外企公司多的是25-35岁的白领,40岁以上的员工很少,二三十岁的外企员工是意气风发的,但外企公司40岁附近的经理人是很尴尬的。我见过的40岁附近的外企经理人大多在一直跳槽,最后大多跳到民企,比方说,唐骏。外企员工的成功很大程度上是公司的成功,并非个人的成功,西门子的确比国美大,但并不代表西门子中国经理比国美的老板强,甚至可以说差得很远。而进外...

  • 外企好还是国企好

    我有个有趣的观察,外企公司多的是25-35岁的白领,40岁以上的员工很少,二三十岁的外企员工是意气风发的,但外企公司40岁附近的经理人是很尴尬的。我见过的40岁附近的外企经理人大多在一直跳槽,最后大多跳到民企,比方说,唐骏。外企员工的成功很大程度上是公司的成功,并非个人的成功,西门子的确比国美大,但并不代表西门子中国经理比国美的老板强,甚至可以说差得很远。而进外企的人往往并不能很早理解这一点...

  • 汉字频率统计

      汉字的频率统计不像英文那样公开!在网上很难找到(至少我没看见)。于是自己想办法:用JS写一个小过程“搜索gb2312汉字在网上的频率”。http://www.csdn.net/Develop/article/19/19992.shtm   运行两个多小时,借助baidu和google得到两份汉字频率表(gb2312的前3755字)。但发现这两个表的汉字频率相差很大(见下表)!也不知道哪一...

  • 看了这篇文章,我知道自己这几年白过了

    林锐,1999年岁末

    写此文使我很为难,一是担心读者误以为我轻浮得现在就开始写自传,二是担心
    朋友们误以为我得了绝症而早早留下遗作。


    不论是落俗套还是不落俗套地评价,我在大学十年里都是出类拔萃的好学生。并
    且一直以来我对朋友们和一些低年级的学生们都有很大的正面影响。这十年是一个从幼
    稚到成熟的过程,交织着聪明与蠢笨、勤奋与懒散、...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。