C++实现LeetCode(198.打家劫舍)

[LeetCode] 198. House Robber 打家劫舍

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.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。那么对于这类求极值的问题首先考虑动态规划 Dynamic Programming 来解，维护一个一位数组 dp，其中 dp[i] 表示 [0, i] 区间可以抢夺的最大值，对当前i来说，有抢和不抢两种互斥的选择，不抢即为 dp[i-1]（等价于去掉 nums[i] 只抢 [0, i-1] 区间最大值），抢即为 dp[i-2] + nums[i]（等价于去掉 nums[i-1]）。再举一个简单的例子来说明一下吧，比如说 nums为{3, 2, 1, 5}，那么来看 dp 数组应该是什么样的，首先 dp[0]=3 没啥疑问，再看 dp[1] 是多少呢，由于3比2大，所以抢第一个房子的3，当前房子的2不抢，则dp[1]=3，那么再来看 dp[2]，由于不能抢相邻的，所以可以用再前面的一个的 dp 值加上当前的房间值，和当前房间的前面一个 dp 值比较，取较大值当做当前 dp 值，这样就可以得到状态转移方程 dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 且需要初始化 dp[0] 和 dp[1]，其中 dp[0] 即为 num[0]，dp[1] 此时应该为 max(num[0], num[1])，代码如下：

解法一：

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 1) return nums.empty() ? 0 : nums[0];
        vector<int> dp = {nums[0], max(nums[0], nums[1])};
        for (int i = 2; i < nums.size(); ++i) {
            dp.push_back(max(nums[i] + dp[i - 2], dp[i - 1]));
        }
        return dp.back();
    }
};

还有一种解法，核心思想还是用 DP，分别维护两个变量 robEven 和 robOdd，顾名思义，robEven 就是要抢偶数位置的房子，robOdd 就是要抢奇数位置的房子。所以在遍历房子数组时，如果是偶数位置，那么 robEven 就要加上当前数字，然后和 robOdd 比较，取较大的来更新 robEven。这里就看出来了，robEven 组成的值并不是只由偶数位置的数字，只是当前要抢偶数位置而已。同理，当奇数位置时，robOdd 加上当前数字和 robEven 比较，取较大值来更新 robOdd，这种按奇偶分别来更新的方法，可以保证组成最大和的数字不相邻，最后别忘了在 robEven 和 robOdd 种取较大值返回，代码如下：

解法二：

class Solution {
public:
    int rob(vector<int>& nums) {
        int robEven = 0, robOdd = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                robEven = max(robEven + nums[i], robOdd);
            } else {
                robOdd = max(robEven, robOdd + nums[i]);
            }
        }
        return max(robEven, robOdd);
    }
};

上述方法还可以进一步简洁，我们使用两个变量 rob 和 notRob，其中 rob 表示抢当前的房子，notRob 表示不抢当前的房子，那么在遍历的过程中，先用两个变量 preRob 和 preNotRob 来分别记录更新之前的值，由于 rob 是要抢当前的房子，那么前一个房子一定不能抢，所以使用 preNotRob 加上当前的数字赋给 rob，然后 notRob 表示不能抢当前的房子，那么之前的房子就可以抢也可以不抢，所以将 preRob 和 preNotRob 中的较大值赋给 notRob，参见代码如下：

解法三：

class Solution {
public:
    int rob(vector<int>& nums) {
        int rob = 0, notRob = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int preRob = rob, preNotRob = notRob;
            rob = preNotRob + nums[i];
            notRob = max(preRob, preNotRob);
        }
        return max(rob, notRob);
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/198

参考资料：

https://leetcode.com/problems/house-robber/description/

https://leetcode.com/problems/house-robber/discuss/55681/java-on-solution-space-o1

https://leetcode.com/problems/house-robber/discuss/55693/c-1ms-o1space-very-simple-solution

https://leetcode.com/problems/house-robber/discuss/55695/java-dp-solution-on-runtime-and-o1-space-with-inline-comment

到此这篇关于C++实现LeetCode(198.打家劫舍)的文章就介绍到这了,更多相关C++实现打家劫舍内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(186.翻转字符串中的单词之二)

    [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二 Given an input string , reverse the string word by word.  Example: Input:  ["t","h","e"," ","s","k","y"," ","i&qu

  • C++实现LeetCode(188.买卖股票的最佳时间之四)

    [LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You m

  • C++实现LeetCode(199.二叉树的右侧视图)

    [LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1     

  • C++实现LeetCode(557.翻转字符串中的单词之三)

    [LeetCode] 557.Reverse Words in a String III 翻转字符串中的单词之三 Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: "Let's take LeetCode conte

  • C++实现LeetCode(309.买股票的最佳时间含冷冻期)

    [LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as

  • C++实现LeetCode(191.位1的个数)

    [LeetCode] 191.Number of 1 Bits 位1的个数 Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). For example, the 32-bit integer '11' has binary representation 00000000000000000000000

  • C++实现LeetCode(190.颠倒二进制位)

    [LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re

  • C++实现LeetCode(198.打家劫舍)

    [LeetCode] 198. House Robber 打家劫舍 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

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • vscode中配置LeetCode插件的教程(愉快刷题)

    大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌

  • vscode+leetcode环境配置方法

    前言 之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置 如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运

  • vscode配置leetcode插件并解决无法登录问题(图文详解)

    官方文档 https://github.com/LeetCode-OpenSource/vscode-leetcode/blob/master/docs/README_zh-CN.md 1.环境 window10 vscode 1.23.0+ Node.js 10+ 如果Node.js 没添加到环境变量需要手动添加,添加成功在cmd中输入node --version会显示:  2.配置 vscode安装leetcode插件: 安装完右侧会出现: 此时发现账号密码方式无法登录(本次教程都针对国际版

  • 如何在Intellij中安装LeetCode刷题插件方便Java刷题

    一.安装 在 IDEA(2019)的 setting 的 Plugins 的 Marketplace 中搜索 leetcode,即可以找到该插件,安装完成了,重启即可. 二.配置 1.重启完成后,第一次使用的时候,需要一些基本的配制,在 setting 中的 Tools 中可以找到该插件工具,为 leetcode plugin,在里面,可以选择访问的为国际的 LeetCode 还是国内的,以及何种语言,同时,输入自己账户名(LoginName)和密码(Password),则可以和自己帐号关联起来

  • 有关IntelliJ IDEA中LeetCode插件配置问题

    最初目的是在实验室电脑和笔记本电脑上同时配置好这个刷题插件,并且Git互联,并锻炼自己debug以及输入输出. 前面的可以参考教程:安装 首先是在IntelliJ上面下载安装好LeetCode插件, 然后配置好登录名和密码, 一切都很顺利,按照网上的教程走的很顺利. 然后我的配置模板是: 标题: P$!{question.frontendQuestionId}_$!velocityTool.camelCaseName(${question.titleSlug}) 代码模板: ${question

  • IntelliJ IDEA 刷题利器 LeetCode 插件详解

    IDEA整合LeetCode插件,可以在 IDEA 本地编辑代码并且运行提交,还能关联自己的账号,非常实用. 下载安装 配置 点击File->Settings->Tools->leetcode plugin,如图: 参数说明: Custom code template: 开启使用自定义模板,否则使用默认生成格式 CodeFileName: 生成文件的名称,默认为题目标题 CodeTemplate: 生成题目代码的内容,默认为题目描述和题目代码 TemplateConstant: 模板常用

  • IDEA2020.1使用LeetCode插件运行并调试本地样例的方法详解

    环境: idea2020.1 插件: LeetCode-editor 6.7 一.IDEA安装LeetCode插件 安装完成重启idea 打开插件 URL可以选择国服和世界服.LoginName和Password填自己的用户名和密码即可. 需要配置的选项为: TempFilePath: 自己保存代码的包的位置 CodeFileName: $!velocityTool.camelCaseName(${question.titleSlug}) CodeTemplate: ${question.con

随机推荐