找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 10870|回复: 3
收起左侧

[面经热题讨论] FB面经和LC新题 House Robber 感觉比较简单的解法。

[复制链接]

10

主题

0

精华

62

积分

资深会员

Rank: 2

积分
62
发表于 4-19-2015 01:42 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 4-21-2015 12:56 PM 编辑

这个在FB面经出现很多次了。 在leetcode 也是新题。

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

其实就是在某个数组里面找一个序列, 序列里面的每一个元素都不能相邻,然后求其最大和

这个问题可以用dp的思想来考虑, 对于第n个房间我们所能有的选择是偷和不偷, 那么如果是做决定是偷 则上一步必须是不偷 那么 这一步的就是 dp[N] = num[i -1 ] + dpNonTake[N -1] , 假设dp[N] 表示的是有N个元素时候的最大值状态。 如果是不偷, 那么上一步就无所谓是不是已经偷过,所以就copy为 dp[N] = dp[N -1 ]即可, 所以总而言之为 dp[N] = Math.max(dpNontake[N-1 ] + num【i】, dp[N-1] ); 因为每一轮迭代只需要触碰到dp 的相邻两个选项 所以可以空间压缩为 两个元素即可。一个 为take 一个为 nontake 和 到当前的最大值。 那么迭代为:

take = nonTake + num【i】;  偷
nonTake = maxProfit;    不偷
maxProfit = Math.max(take,nonTake); 求最大利润

时间复杂度为O(n) 空间为O(1) 能运行的代码为:

public int rob(int[] num) {
        int take = 0;
        int maxProfit = 0;
        int nonTake = 0;
        for(int i = 0 ; i < num.length; ++i){
            take = nonTake + num【i】;
            nonTake = maxProfit;
            maxProfit = Math.max(take,nonTake);
        }
        return maxProfit;
    }


补充一个其他帖子:http://www.meetqun.com/thread-8176-1-1.html
里面有Java/C++/Python的代码。

24

主题

4

精华

209

积分

高级会员

Rank: 3Rank: 3

积分
209

最佳新人

发表于 4-19-2015 07:46 PM | 显示全部楼层
分析得很好!
回复 支持 反对

使用道具 举报

24

主题

4

精华

209

积分

高级会员

Rank: 3Rank: 3

积分
209

最佳新人

发表于 4-19-2015 08:00 PM | 显示全部楼层
    public int rob(int[] num) {
        int max = 0;
        if(num == null) {
            return max;
        }
        int maxPrePre = 0;
        int maxPre = 0;
        for(int i=0; i<num.length; i++) {
            int takenI = maxPrePre + num【i】;
            max = Math.max(maxPre, takenI);
            maxPrePre = maxPre;
            maxPre = max;
        }
        return max;
    }
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表