LeetCode刷题---打家劫舍问题

顾得泉:个人主页

个人专栏:《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂,年薪百万!


一、打家劫舍

题目链接:打家劫舍

题目描述

       你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

       给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

解法

1.状态表示:

       对于简单的线性dp,我们可以用「经验+题目要求」来定义状态表示:

            i.以某个位置为结尾,巴拉巴拉;

            ii.以某个位置为起点,巴拉巴拉。

       这里我们选择比较常用的方式,以某个位置为结尾,结合题目要求,定义一个状态表示:

            dp[i]表示:选择到i位置时,此时的最高金额。

       但是我们这个题在1位置的时候,会面临「选择」或者「不选择」两种抉择,所依赖的状态需要细分:

       f[i]表示:选择到i位置时,nums[i]必选,此时的最高金额;

       g[i]表示:选择到i位置时,nums[i]不选,此时的最高金额。

2.状态转移方程:

       因为状态表示定义了两个,因此我们的状态转移方程也要分析两个:

对于f[i]:

       如果nums[i]必选,那么我们仅需知道[i - 1]位置在不选的情况下的最高金额,然后加上nums[i]即可,因此f[i] = g[i - 1]+ nums[i]

对于g[i]:

       如果nums[j]不选,那么[i - 1]位置上选或者不选都可以。因此,我们需要知道[i- 1]位宣上选或者不选两种情况下的最长时长,因此 g[i] = max (f[i - 1],g[i- 1])

3.初始化:

       这道题的初始化比较简单,因此无需加辅助节点,仅需初始化 f[0] = nums[0],g[0] = 0即可

4.填表顺序:

       根据「状态转移方程」得「从左往右,两个表一起填」

5.返回值

       根据「状态表示」,应该返回max(f[n - 1],g[n - 1])

代码实现

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        if(n == 0) return nums[0];
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[n-1], g[n-1]);
    }
};

二、打家劫舍Ⅱ

题目链接:打家劫舍 II

题目描述

       你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

       给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

解法

       这一个问题是「打家劫舍」问题的变形。

       上一个问题是一个「单排」的模式,这一个问题是一个「环形」的模式,也就是首尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题:

       a.偷第一个房屋时的最大金额×,此时不能偷最后一个房子,因此就是偷[0,n - 2]区间的房子;

       b.不偷第一个房屋时的最大金额y,此时可以偷最后一个房子,因此就是偷[1,n - 1]区间的房子;

       两种情况下的「最大值」,就是最终的结果

       因此,问题就转化成求「两次单排结果的最大值」

代码实现

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
    int rob1(vector<int>& nums, int left, int right)
    {
        if(left > right)  return 0;
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        f[left] = nums[left];
        for(int i = left + 1; i <= right; i++)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[right], g[right]);
    }
};

三、删除并获得点数

题目链接:删除并获得点数

题目描述

       给你一个整数数组 nums ,你可以对它进行一些操作。

       每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

       开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1:

输入:nums = [3,4,2]
输出:6
解释:
删除 4 获得 4 个点数,因此 3 也被删除。
之后,删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2:

输入:nums = [2,2,3,3,3,4]
输出:9
解释:
删除 3 获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

解法

       其实这道题依旧是「打家劫舍」问题的变型。我们注意到题目描述,选择×数字的时候,×-1与x+1是不能被选择的。像不像「打家劫舍」问题中,选择i位置的金额之后,就不能选择i - 1位置以及i+1位置的金额呢~

       因此,我们可以创建一个大小为10001(根据题目的数据范围)的hash 数组,将nums 数组中每一个元素×,累加到,hash 数组下标为x的位置处,然后在hash数组上来一次「打家劫舍」即可

代码实现

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        const int n = 10001;
        int arr[n] = {0};
        for(auto x : nums) arr[x] += x;

        vector<int> f(n);
        auto g = f;

        for(int i = 1; i < n; i++)
        {
            f[i] = g[i-1] + arr[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[n-1], g[n-1]);
    }
};

结语:今日的刷题分享到这里就结束了,希望本篇文章的分享会对大家的学习带来些许帮助,如果大家有什么问题,欢迎大家在评论区留言~~~ 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/206840.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java实现堆

堆是一种基于完全二叉树的数据结构&#xff0c;它分为大根堆和小根堆。在大根堆中&#xff0c;每个节点的值都大于或等于其子节点的值&#xff1b;而在小根堆中&#xff0c;每个节点的值都小于或等于其子节点的值。 在Java中&#xff0c;我们可以使用数组来表示堆。由于完全二…

RS232串口_笔记

这里写目录标题 1、RS232串口理论起始位数据位校验位LSB & MSB示波器查看数据信号对应连接方式 1、RS232串口理论 UART(通用异步收发传输) 是一种通信协议&#xff0c;而 RS232 (串行通信接口)是种物理接口标准。UART 是一种用于在计算机和外部设备之间传输数据的协议&…

鸿蒙系统开发手册 - HarmonyOS内核驱动层源码分析

众所周知系统定义HarmonyOS是一款“面向未来”、面向全场景&#xff08;移动办公、运动健康、社交通信、媒体娱乐等&#xff09;的分布式操作系统。在传统的单设备系统能力的基础上&#xff0c;HarmonyOS提出了基于同一套系统能力、适配多种终端形态的分布式理念&#xff0c;能…

链表高频面试题

1. 两个链表第一个公共子节点 LeetCode160 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; listA [4,1,8,4,5], listB [5…

11-22 SSM3

书城分页查询 使用mybatis分页插件&#xff1a; 请完成登陆注册 -> 跳转到首页 解决前端上架时间点击切换 以及侧边栏点击由背景颜色的改变 完成超链接的绑定点击时间 -> jquery $(document).ready(function() { // 初始化上架时间状态为 true&#xff08;上架&…

记录一次爱快路由ACL策略引起的大坑

环境&#xff1a; A公司和B公司采用爱快的ipsec互联 B公司同时有加密软件限制网络 问题&#xff1a;对方ERP无法连接我们的数据库服务器 先简单测试了下1433端口是不是通的 下面的测试结果&#xff0c;直接ping是通的&#xff0c;但是加上1433端口后就不通 排查过程&#xff1…

centos7下执行yum命令报错

前言 在Linux系统中&#xff0c;安装nginx时候&#xff0c;需要先安装环境。 Nginx是使用C语言开发&#xff0c;安装nginx需要先从官网上将源码下载&#xff0c;然后编译&#xff0c;编译需要gcc环境,但是在安装gcc环境的时候&#xff0c;执行命令报错。 yum install –y gcc-…

【开源】基于JAVA的大学计算机课程管理平台

项目编号&#xff1a; S 028 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S028&#xff0c;文末获取源码。} 项目编号&#xff1a;S028&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 实验课程档案模块2.2 实验资源模块2…

有什么值得推荐的node. js练手项目吗?

前言 可以参考一下下面的nodejs相关的项目&#xff0c;希望对你的学习有所帮助&#xff0c;废话少说&#xff0c;让我们直接进入正题 1、 NodeBB Star: 13.3k 一个基于Node.js的现代化社区论坛软件&#xff0c;具有快速、可扩展、易于使用和灵活的特点。它支持多种数据库&…

使用JAVA语言写一个排队叫号的小程序

以下是一个简单的排队叫号的小程序&#xff0c;使用JAVA语言实现。 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class NumberingSystem {public static void main(String[] args) {Queue<String> queue new LinkedList<…

WPF绘制进度条(弧形,圆形,异形)

前言 WPF里面圆形进度条实现还比较麻烦,主要涉及到的就是动态绘制进度条的进度需要用到简单的数学算法。其实原理比较简单,我们需要的是话两条重叠的弧线,里面的弧线要比里面的弧线要宽,这样简单的雏形就出来了。 基础写法 我们可以用Path来绘制弧线,代码如下: <Gr…

推荐几款python在线学习和电子书网站

学习python的过程中&#xff0c;虽然下载了很多的电子书&#xff0c;但是在学习过程中基本上都是通过一些在线网站或者在线电子书进行的。 下面给大家推荐几个在线学习教程网站和电子书网站。 《菜鸟教程》 一句话介绍&#xff1a;很多初学者的选择 网址&#xff1a;https:…

C++11——右值引用和移动语义

左值和右值 在C11之前&#xff0c;我们很少去关注左值和右值这一概念&#xff0c;但是在C11中&#xff0c;加入了一个非常重要的语法&#xff1a;右值引用。 左值和右值&#xff0c;一般来说可以当作字面意思&#xff0c;左值是经常出现在表达式左边的值&#xff0c;右值是经…

【开源视频联动物联网平台】写一个物联网项目捐献给Dromara组织

一、平台简介 MzMedia开源视频联动物联网平台&#xff0c;简单易用&#xff0c;更适合中小企业和个人学习使用。适用于智能家居、农业监测、水利监测、工业控制&#xff0c;车联网&#xff0c;监控直播&#xff0c;慢直播等场景。 支持抖音&#xff0c;视频号等主流短视频平台…

Linux--系统结构与操作系统

文章目录 冯诺依曼体系结构为什么要有内存&#xff1f;场景一 操作系统何为管理&#xff1f; 冯诺依曼体系结构 冯诺依曼体系结构是计算机体系结构的基本原理之一。它将程序和数据都以二进制形式存储&#xff0c;以相同的方式处理和存取。 上图是冯诺依曼体系结构的五大组成部…

处理机调度与作业调度

处理机调度 一个批处理型作业&#xff0c;从进入系统并驻留在外存的后备队列上开始&#xff0c;直至作业运行完毕&#xff0c;可能要经历如下的三级调度 高级调度 也称为作业调度、长程调度、接纳调度。调度对象是作业 主要功能&#xff1a; 挑选若干作业进入内存 为作业创建…

git push 报错 error: src refspec master does not match any 解决

git报错 ➜ *** git:(main) git push -u origin "master" error: src refspec master does not match any error: failed to push some refs to https://gitee.com/***/***.git最新版的仓库初始化后 git 主分支变成了 main 方法 1.把 git 默认分支名改回 master …

Sentinel的一些知识二

11231041 下一个是 熔断规则是异常数 和异常比例一样 只是换成了异常个数 1秒内的异常数有3个&#xff0c;就熔断2秒 下一步 进行压力测试 11231343 热点规则 没懂这个热点规则存在的意义 某个用户访问过于频繁&#xff0c;对其进行限制&#xff0c;给其他用户访问的机…

mysql中删除数据后,新增数据时id会跳跃,主键自增id不连续

引言&#xff1a; 在使用MySQL数据库时&#xff0c;有时候我们需要删除某些记录&#xff0c;但是删除记录后可能会导致表中的id不再连续排序。 如何实现删除记录后让id重新排序的功能。 如图&#xff1a; 删除数据后&#xff0c;中间的id不会自动连续。 下面有两种方法进行重…

万界星空科技仓库管理wms系统

企业在管理库存时&#xff0c;尤其是生产制造企业&#xff0c;使用传统方式比如纸笔、Excel 管理库存&#xff0c;由于工具和信息化存在局限&#xff0c;导致在管理库存时出现如下问题&#xff1a; 1、通过纸笔记录出入库申请&#xff0c;人为手动计算易出错&#xff0c;数据易…