当前位置: 首页 > news >正文

198.打家劫舍,213.打家劫舍II,337.打家劫舍III

代码随想录训练营第48天|198.打家劫舍,213.打家劫舍II,337.打家劫舍III

  • 198.打家劫舍
    • 文章
    • 思路
    • 代码
  • 213.打家劫舍III
    • 文章
    • 思路
    • 代码
  • 337.打家劫舍III
    • 文章
    • 思路
    • 代码
  • 总结

198.打家劫舍

文章

代码随想录|0198.打家劫舍

思路

d p [ i ] = M a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] ) dp[i]=Max(dp[i-1],dp[i-2]+nums[i]) dp[i]=Max(dp[i1],dp[i2]+nums[i])

代码

class Solution {public int rob(int[] nums) {int i, n;n = nums.length;int[] dp = new int[n];dp[0] = nums[0];if (n < 2) {return dp[0];}dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];for (i = 2; i < n; ++i) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[n - 1];}
}

213.打家劫舍III

文章

213.打家劫舍II

思路

在[0, n-1]范围内dp一次,在[1, n]范围内dp一次,取二者最大值

代码

class Solution {public int rob(int[] nums) {int i, n;n = nums.length;if (n == 1) {return nums[0];}if (n == 2) {return nums[1] > nums[0] ? nums[1] : nums[0];}int[] dp0 = new int[n - 1];dp0[0] = nums[0];dp0[1] = nums[1] > nums[0] ? nums[1] : nums[0];int[] dp1 = new int[n - 1];dp1[0] = nums[1];dp1[1] = nums[2] > nums[1] ? nums[2] : nums[1];for (i = 2; i < n - 1; ++i) {dp0[i] = Math.max(dp0[i - 1], dp0[i - 2] + nums[i]);dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i +1]);}return Math.max(dp0[n - 2], dp1[n - 2]);}
}

337.打家劫舍III

文章

代码随想录|0337.打家劫舍III

思路

劫不劫某个节点取决于其两个子节点有没有被劫,所以是后续遍历,递归每一层返回是否劫那个节点的两种情况

代码

class Solution {public int rob(TreeNode root) {TreeNode dummy = new TreeNode(0);dummy.right = root;return dfs(dummy)[0];}public int[] dfs(TreeNode node) {if (node == null) {return new int[] {0, 0};}int[] leftVal = dfs(node.left);int[] rightVal = dfs(node.right);int[] res = new int[2];res[0] = Math.max(leftVal[0], leftVal[1]) + Math.max(rightVal[0], rightVal[1]);res[1] = leftVal[0] + rightVal[0] + node.val;return res;}
}

总结

这三道题都是二刷了,思路明确
但是上上周笔试人家出的题目是打家劫舍IV。。。。我并没有做出来,等下去研究研究再说

相关文章:

198.打家劫舍,213.打家劫舍II,337.打家劫舍III

代码随想录训练营第48天|198.打家劫舍&#xff0c;213.打家劫舍II&#xff0c;337.打家劫舍III 198.打家劫舍文章思路代码 213.打家劫舍III文章思路代码 337.打家劫舍III文章思路代码 总结 198.打家劫舍 文章 代码随想录|0198.打家劫舍 思路 d p [ i ] M a x ( d p [ i − …...

msvcp140.dll是什么东西,如何解决msvcp140.dll丢失的问题的方法分享

在现代生活中&#xff0c;电脑已经成为我们工作、学习和娱乐的重要工具。然而&#xff0c;电脑问题的出现往往会给我们的生活带来不便。其中&#xff0c;"msvcp140.dll丢失"是一个常见的电脑问题。本文将详细介绍这个问题的原因和解决方法&#xff0c;帮助大家更好地…...

音视频 SDL vs2017配置

一、首先我把SDL放在了C盘根目录下 二、新建空项目 三、添加main.cpp //main.cpp #include<iostream> #include <SDL.h>int main(int argc, char* argv[]) // main函数头必须这样写&#xff0c;因为SDL把main定义成了宏 {SDL_Delay(3000); // 让窗口在屏幕上保持…...

前端面试要点

0914 JScript深拷贝和浅拷贝&#xff08;js解构赋值算哪个&#xff1f;&#xff09; 深拷贝和浅拷贝 回流和重绘 回流和重绘 webpack打包流程 Webpack打包 虚拟DOM 虚拟DOM git合并分支 git合并分支 CSS盒子模型 CSS盒子模型 0911 WebPack分包 webpack分包 ts泛型 ts泛型 优化…...

shell字符串处理之字符串比较

引言 我们在使用shell编写脚本时&#xff0c;经常需要对字符串进行处理&#xff0c;如字符串大小比较、模式匹配、替换、截断等。本文将梳理字符串比较中常见的用法。 字符串比较 1. 直接比较字符串 a$1 b$2 c"" # 等于 if [ $a "abc" ];thenecho $a …...

怎么获取别人店铺的商品呢?

jd.item_search_shop(获得店铺的所有商品) 为了进行电商平台 的API开发&#xff0c;首先我们需要做下面几件事情。 1&#xff09;开发者注册一个账号 2&#xff09;然后为每个JD应用注册一个应用程序键&#xff08;App Key) 。 3&#xff09;下载JDAPI的SDK并掌握基本的API…...

【数据结构】二叉树的链式结构

【数据结构】二叉树的链式存储结构 二叉树的存储结构 typedef int BTDataType; // 二叉树的结构 typedef struct BinaryTreeNode {BTDataType data; // 树的值struct BinaryTreeNode *left; // 左孩子struct BinaryTreeNode *right;// 右孩子 } BinaryTreeNode;二…...

模拟实现C语言--strlen函数

模拟实现C语言–strlen函数 模拟实现C语言--strlen函数一、strlen函数是什么&#xff1f;二、strlen函数的模拟实现2.1 计数器方式实现strlen函数2.2 不创建临时变量计数器方式实现strlen函数2.3 指针-指针方式实现strlen函数 三、strlen函数的返回类型 一、strlen函数是什么&a…...

Spring Boot + Vue的网上商城之物流系统实现

Spring Boot Vue的网上商城之物流系统实现 思路 当构建一个物流系统时&#xff0c;我们可以按照以下步骤进行&#xff1a; 设计数据模型&#xff1a;首先确定系统中需要存储的数据&#xff0c;例如物流公司信息、物流订单信息等。根据需求设计相应的数据模型&#xff0c;包括…...

释放数据价值这道难题,Smartbi V11有解

《未来简史》预言&#xff1a;数据将成为人们未来的信仰。 未来已来&#xff0c;将至已至。如今&#xff0c;数据所扮演的角色与作用超乎想象。从政府将数据要素列入生产要素之中&#xff0c;到数据驱动型业务场景涌现&#xff0c;企业与组织对于数据及其价值的认可度明显提升…...

Day_14 > 指针进阶(3)> bubble函数

目录 1.回顾回调函数 2.写一个bubble_sort函数 2.1认识一下qsort函数 ​编辑2.2写bubble_sort函数 今天我们继续深入学习指针 1.回顾回调函数 我们回顾一下之前学过的回调函数 回调函数就是一个通过函数指针调用的函数 如果你把函数的指针&#xff08;地址&#xff09;…...

sql中怎么查books表下面的内容

要查询 books 表中的所有内容&#xff0c;你可以使用以下 SQL 语句&#xff1a; USE bookmanagement; -- 选择数据库 SELECT * FROM books; -- 查询books表中的所有内容如果你使用的是命令行界面 (mysql 客户端) 来操作数据库&#xff0c;可以直接在命令提示符中输入上述命令…...

Vulnhub系列靶机---HarryPotter-Aragog-1.0.2哈利波特系列靶机-1

文章目录 方式一信息收集主机发现端口扫描目录扫描wpscan工具 漏洞利用msf工具数据库权限用户权限root提权 方式二信息收集gobuster扫描wpscan扫描 漏洞利用POC 靶机文档&#xff1a;HarryPotter: Aragog (1.0.2) 下载地址&#xff1a;Download (Mirror) 方式一 信息收集 主机…...

.NET 8发布首个RC,比.NET 7的超级快更快

.NET 8 发布了首个 RC。据称 RC 阶段会发布两个版本&#xff0c;正式版将于 2023 年 11 月 14 日至 16 日在 .NET Conf 2023 上推出。.NET 8 是长期支持 (LTS) 版本&#xff0c;将会获得 3 年技术支持。 公告写道&#xff0c;此版本为 Android 和 WASM 引入了全新的 AOT 模式、…...

在 Substance Painter中自定义Shader

为什么要学习在Substance Painter中自定义Shader&#xff1f; 答&#xff1a;需要实现引擎与Substance Painter中的渲染效果一致&#xff0c;材质的配置也一致&#xff0c;所见即所得。 基础概述 首先在着色器设置这里&#xff0c;我们可以查看当前渲染使用的着色器 如果没有…...

【自学开发之旅】Flask-restful-Jinjia页面编写template-回顾(五)

restful是web编程里重要的概念 – 一种接口规范也是一种接口设计风格 设计接口&#xff1a; 要考虑&#xff1a;数据返回、接收数据的方式、url、方法 统一风格 rest–表现层状态转移 web–每一类数据–资源 资源通过http的动作来实现状态转移 GET、PUT、POST、DELETE path…...

input 的 placeholder 样式

::placeholder 伪元素 这个伪元素可以改变 input、textarea 占位文本的样式。 input::placeholder {color: green; }完整的兼容性写法&#xff1a; input {&::-webkit-input-placeholder, /* WebKit browsers*/ &:-moz-input-placeholder, /* Mozilla Firefox 4 to …...

4.4-Spring源码循环依赖终极讲解

回顾上期内容 new 容器 new AnnotateBeanDefinitionReader 的时候创建很多创世纪的类&#xff0c;其中有一个ConfigurationPostProcessor是用来解析配置类的&#xff0c;将其注册起来存到Bean定义的Map中【这个类是基于Bean工厂后置处理器的】 这一步是将配置类注册到Bean定…...

腾讯云4核8G服务器选CVM还是轻量比较好?价格对比

腾讯云4核8G云服务器可以选择轻量应用服务器或CVM云服务器标准型S5实例&#xff0c;轻量4核8G12M服务器446元一年&#xff0c;CVM S5云服务器935元一年&#xff0c;相对于云服务器CVM&#xff0c;轻量应用服务器性价比更高&#xff0c;轻量服务器CPU和CVM有区别吗&#xff1f;性…...

数学实验-素数(Mathematica实现)

一、实验名称&#xff1a;素数 二、实验环境&#xff1a;Mathematica 10.3软件 三、实验目的&#xff1a;本实验将探讨素数的规律&#xff0c;研究素数的判别、最大的素数、构成生成素数的公式和素数的分布&#xff0c;并学会求解某些范围内的素数。 四、实验内容、步骤以及…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...