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[i−1],dp[i−2]+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.打家劫舍,213.打家劫舍II,337.打家劫舍III 198.打家劫舍文章思路代码 213.打家劫舍III文章思路代码 337.打家劫舍III文章思路代码 总结 198.打家劫舍 文章 代码随想录|0198.打家劫舍 思路 d p [ i ] M a x ( d p [ i − …...
msvcp140.dll是什么东西,如何解决msvcp140.dll丢失的问题的方法分享
在现代生活中,电脑已经成为我们工作、学习和娱乐的重要工具。然而,电脑问题的出现往往会给我们的生活带来不便。其中,"msvcp140.dll丢失"是一个常见的电脑问题。本文将详细介绍这个问题的原因和解决方法,帮助大家更好地…...
音视频 SDL vs2017配置
一、首先我把SDL放在了C盘根目录下 二、新建空项目 三、添加main.cpp //main.cpp #include<iostream> #include <SDL.h>int main(int argc, char* argv[]) // main函数头必须这样写,因为SDL把main定义成了宏 {SDL_Delay(3000); // 让窗口在屏幕上保持…...
前端面试要点
0914 JScript深拷贝和浅拷贝(js解构赋值算哪个?) 深拷贝和浅拷贝 回流和重绘 回流和重绘 webpack打包流程 Webpack打包 虚拟DOM 虚拟DOM git合并分支 git合并分支 CSS盒子模型 CSS盒子模型 0911 WebPack分包 webpack分包 ts泛型 ts泛型 优化…...
shell字符串处理之字符串比较
引言 我们在使用shell编写脚本时,经常需要对字符串进行处理,如字符串大小比较、模式匹配、替换、截断等。本文将梳理字符串比较中常见的用法。 字符串比较 1. 直接比较字符串 a$1 b$2 c"" # 等于 if [ $a "abc" ];thenecho $a …...
怎么获取别人店铺的商品呢?
jd.item_search_shop(获得店铺的所有商品) 为了进行电商平台 的API开发,首先我们需要做下面几件事情。 1)开发者注册一个账号 2)然后为每个JD应用注册一个应用程序键(App Key) 。 3)下载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函数是什么?二、strlen函数的模拟实现2.1 计数器方式实现strlen函数2.2 不创建临时变量计数器方式实现strlen函数2.3 指针-指针方式实现strlen函数 三、strlen函数的返回类型 一、strlen函数是什么&a…...
Spring Boot + Vue的网上商城之物流系统实现
Spring Boot Vue的网上商城之物流系统实现 思路 当构建一个物流系统时,我们可以按照以下步骤进行: 设计数据模型:首先确定系统中需要存储的数据,例如物流公司信息、物流订单信息等。根据需求设计相应的数据模型,包括…...
释放数据价值这道难题,Smartbi V11有解
《未来简史》预言:数据将成为人们未来的信仰。 未来已来,将至已至。如今,数据所扮演的角色与作用超乎想象。从政府将数据要素列入生产要素之中,到数据驱动型业务场景涌现,企业与组织对于数据及其价值的认可度明显提升…...
Day_14 > 指针进阶(3)> bubble函数
目录 1.回顾回调函数 2.写一个bubble_sort函数 2.1认识一下qsort函数 编辑2.2写bubble_sort函数 今天我们继续深入学习指针 1.回顾回调函数 我们回顾一下之前学过的回调函数 回调函数就是一个通过函数指针调用的函数 如果你把函数的指针(地址)…...
sql中怎么查books表下面的内容
要查询 books 表中的所有内容,你可以使用以下 SQL 语句: USE bookmanagement; -- 选择数据库 SELECT * FROM books; -- 查询books表中的所有内容如果你使用的是命令行界面 (mysql 客户端) 来操作数据库,可以直接在命令提示符中输入上述命令…...
Vulnhub系列靶机---HarryPotter-Aragog-1.0.2哈利波特系列靶机-1
文章目录 方式一信息收集主机发现端口扫描目录扫描wpscan工具 漏洞利用msf工具数据库权限用户权限root提权 方式二信息收集gobuster扫描wpscan扫描 漏洞利用POC 靶机文档:HarryPotter: Aragog (1.0.2) 下载地址:Download (Mirror) 方式一 信息收集 主机…...
.NET 8发布首个RC,比.NET 7的超级快更快
.NET 8 发布了首个 RC。据称 RC 阶段会发布两个版本,正式版将于 2023 年 11 月 14 日至 16 日在 .NET Conf 2023 上推出。.NET 8 是长期支持 (LTS) 版本,将会获得 3 年技术支持。 公告写道,此版本为 Android 和 WASM 引入了全新的 AOT 模式、…...
在 Substance Painter中自定义Shader
为什么要学习在Substance Painter中自定义Shader? 答:需要实现引擎与Substance Painter中的渲染效果一致,材质的配置也一致,所见即所得。 基础概述 首先在着色器设置这里,我们可以查看当前渲染使用的着色器 如果没有…...
【自学开发之旅】Flask-restful-Jinjia页面编写template-回顾(五)
restful是web编程里重要的概念 – 一种接口规范也是一种接口设计风格 设计接口: 要考虑:数据返回、接收数据的方式、url、方法 统一风格 rest–表现层状态转移 web–每一类数据–资源 资源通过http的动作来实现状态转移 GET、PUT、POST、DELETE path…...
input 的 placeholder 样式
::placeholder 伪元素 这个伪元素可以改变 input、textarea 占位文本的样式。 input::placeholder {color: green; }完整的兼容性写法: input {&::-webkit-input-placeholder, /* WebKit browsers*/ &:-moz-input-placeholder, /* Mozilla Firefox 4 to …...
4.4-Spring源码循环依赖终极讲解
回顾上期内容 new 容器 new AnnotateBeanDefinitionReader 的时候创建很多创世纪的类,其中有一个ConfigurationPostProcessor是用来解析配置类的,将其注册起来存到Bean定义的Map中【这个类是基于Bean工厂后置处理器的】 这一步是将配置类注册到Bean定…...
腾讯云4核8G服务器选CVM还是轻量比较好?价格对比
腾讯云4核8G云服务器可以选择轻量应用服务器或CVM云服务器标准型S5实例,轻量4核8G12M服务器446元一年,CVM S5云服务器935元一年,相对于云服务器CVM,轻量应用服务器性价比更高,轻量服务器CPU和CVM有区别吗?性…...
数学实验-素数(Mathematica实现)
一、实验名称:素数 二、实验环境:Mathematica 10.3软件 三、实验目的:本实验将探讨素数的规律,研究素数的判别、最大的素数、构成生成素数的公式和素数的分布,并学会求解某些范围内的素数。 四、实验内容、步骤以及…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
