面试算法91:粉刷房子
题目
一排n幢房子要粉刷成红色、绿色和蓝色,不同房子被粉刷成不同颜色的成本不同。用一个n×3的数组表示n幢房子分别用3种颜色粉刷的成本。要求任意相邻的两幢房子的颜色都不一样,请计算粉刷这n幢房子的最少成本。例如,粉刷3幢房子的成本分别为[[17,2,16],[15,14,5],[13,3,1]],如果分别将这3幢房子粉刷成绿色、蓝色和绿色,那么粉刷的成本是10,是最少的成本。
分析:确定状态转移方程
用i表示房子,f(颜色)(i)表示最小花费,costs[][]表示当前房子当前颜色的话费
f(颜色)(i) = Math.min( f(其他颜色)(i-1) , f(其他颜色)(i-1) ) + costs[当前房子][当前颜色]
解
public class Test {public static void main(String[] args) {int[][] costs = {{17, 2, 16},{15, 14, 5},{13, 3, 1}};int result = minCost(costs);System.out.println(result);}public static int minCost(int[][] costs) {if (costs.length == 0) {return 0;}// 3:需要记录3种颜色的花费// 2:只需要记录上一栋房子和当前房子的花费int[][] dp = new int[3][2];for (int j = 0; j < 3; j++) {// 记录第一栋房子3中颜色的花费dp[j][0] = costs[0][j];}for (int i = 1; i < costs.length; i++) {// 遍历房子for (int j = 0; j < 3; j++) {// 遍历颜色// [(j+2)%3]:其他颜色的意思// [(i-1)%2]:上一栋房子的意思int prev1 = dp[(j + 2) % 3][(i - 1) % 2];int prev2 = dp[(j + 1) % 3][(i - 1) % 2];dp[j][i % 2] = Math.min(prev1, prev2) + costs[i][j];}}int last = (costs.length - 1) % 2;// 最后的房子// dp[0][last]、dp[1][last]、dp[2][last]:表示3种颜色,取最小值return Math.min(dp[0][last], Math.min(dp[1][last], dp[2][last]));}}
相关文章:
面试算法91:粉刷房子
题目 一排n幢房子要粉刷成红色、绿色和蓝色,不同房子被粉刷成不同颜色的成本不同。用一个n3的数组表示n幢房子分别用3种颜色粉刷的成本。要求任意相邻的两幢房子的颜色都不一样,请计算粉刷这n幢房子的最少成本。例如,粉刷3幢房子的成本分别为…...
js逆向第11例:猿人学第4题雪碧图、样式干扰
任务4:采集这5页的全部数字,计算加和并提交结果 打开控制台查看请求地址https://match.yuanrenxue.cn/api/match/4,返回的是一段html网页代码 复制出来格式化后,查看具体内容如下: <td><img src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABUAAA…...
OpenEular23.09(欧拉)操作系统为企业搭建独立的K8S集群环境,详细流程+截图
一.环境; win10,vmware16 pro,openeular23.09,linux内核 6.4.0-10.1.0.20.oe2309.x86_64, docker-engine 2:18.09.0-328,kubernetes 1.25.3,containerd 1.6.22,calico v3.25 集群…...
学生成绩管理系统半成品
C语言的老师在给我们讲指针的时候,讲的并不深入,她用了一个学生成绩管理系统来引入指针这个东西并给我们讲解,但我觉得她的管理系统功能有一些不足,并且不是很美观,所以说心血来潮,自己也动手写了一个学生成…...
国家信息安全水平等级考试NISP二级题目卷⑤(包含答案)
国家信息安全水平等级考试NISP二级题目卷(五) 国家信息安全水平等级考试NISP二级题目卷(五)需要报考咨询可以私信博主! 前言: 国家信息安全水平考试(NISP)二级,被称为校园版”CISP”,由中国信息…...
4.快速实现增删改查,模糊查询功能
打开springboot项目,在com.example下建包common,在common下新建Result.java 4.1封装统一的返回数据结构 1.在Result.java中编写如下代码: private static final String *SUCCESS*"0"; private static final String *ERROR*"-1"; p…...
【Redux】自己动手实现redux和react-redux
1. React提供context的作用 在class组件的世界里,如果后代组件共享某些状态,比如主题色、语言键,则需要将这些状态提升到根组件,以props的方式从根组件向后代组件一层一层传递,这样则需要在每层写props.someData&#…...
代码随想录算法训练营day6|242.有效的字母异位词、349.两个数组的交集、202.快乐数
哈希表理论基础 建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。 什么时候想到用哈希法,当我们遇到了要快速判断一个元素是否出现集合里的时…...
2024.1.4每日一题
LeetCode每日一题 2397.被列覆盖的最多行数 2397. 被列覆盖的最多行数 - 力扣(LeetCode) 题目描述 给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ;另给你一个整数 numSelect,表示你必须从 matrix 中选择的 不同 …...
C++协程和线程的区别?详细介绍一下C++协程
C协程和线程的区别 线程是操作系统级别的资源,由操作系统负责调度和切换,每个线程都有自己的堆栈和执行上下文。线程之间的切换需要保存和恢复线程的执行上下文,这个过程有一定的开销。协程是用户态的轻量级线程,协程的调度完全由…...
数字信号处理期末复习——计算大题(一)
个人名片: 🦁作者简介:一名喜欢分享和记录学习的在校大学生 🐯个人主页:妄北y 🐧个人QQ:2061314755 🐻个人邮箱:2061314755qq.com 🦉个人WeChat:V…...
matlab数值计算函数--ode45
当难以求得微分方程的解析解时,可以求其数值解,Matlab中求微分方程数值解的函数有七个:ode45,ode23,ode113,ode15s,ode23s,ode23t,ode23tb。本文讲解ode45,其…...
Vue3地图选点组件
Vue3地图选点组件 <template><div style"width: 100%; height: 500px"><div class"search-container"><el-autocompletev-model"suggestionKeyWord"class"search-container__input"clearable:fetch-suggestion…...
JS之注册事件兼容性解决方案
本章介绍注册事件兼容性的解决方案 废话不多说,直接上代码: function addEventListener(element, eventName, fn) {//判断当前浏览器是否支持 addEventListener 方法if (element.addEventListener) {element.addEventListener(eventName, fn); // 第三个…...
C#中使用as关键字将对象转换为指定类型
目录 一、定义 二、示例 三、生成 使用as关键字可以将对象转换为指定类型,与is关键字不同,is关键字用于检查对象是否与给定类型兼容,如果兼容则返回true,如果不兼容则返回false。而as关键字会直接进行类型转换,如果…...
【Spring实战】21 Spring Data REST 常用功能详细介绍
文章目录 1. 资源导出(Resource Exporting)2. 查询方法(Query Methods)3. 分页和排序(Pagination and Sorting)4. 关联关系(Associations)5. 事件(Events)6. …...
05-微服务-RabbitMQ-概述
RabbitMQ 1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式: 同步通讯:就像打电话,需要实时响应。 异步通讯:就像发邮件,不需要马上回复。 两种方式各有优劣,打电话可以立即得到响应&am…...
jmeter参数化的三种方式
1.用户定义变量 使用变量: ${变量名} 这个变量是全局变量,也就是在下面子节点中都可以使用; 使用场景:两个账号分别有不同的权限,A经办,B审核。等。。。 2.CSV数据文件设置 3.函数...
java基础之Java8新特性-Lambda
目录 什么是Lambda表达式 Lambda表达式规范 基本语法 参数列表 函数体 注意事项 如何定义函数接口 1.保证接口中只能有一个抽象方法 2.使用FunctionalInterface注解标记该接口为函数接口 使用Lambda调用无参函数 使用Lambda调用有参函数 使用Lambda的精简写法 使用…...
入门使用mybatis-plus
第一步:pom文件带入依赖 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.1</version> </dependency> 第二步:创建实体对象 TableName(&…...
ubuntu安装和配置ssh教程
一、前言 ssh服务类似于windows的远程桌面服务,可以实现对linux系统的远程管理,ssh默认端口为22端口。后面博主进行操作以ubuntu2020操作系统为例进行操作。 二、安装ssh服务 Ubuntu 2020 默认不安装 SSH 服务。它只安装了 SSH 客户端,可以用于连接到其他计算机上的 SSH 服…...
每天刷两道题——第六天
1.1字母异位词分组 给你一个字符串数组,将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词指的是由重新排列源单词的所有字母得到的一个新单词。 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,…...
时间序列平稳性相关检验方法
理解平稳性 一般来说,平稳时间序列是指随着时间的推移具有相当稳定的统计特性的时间序列,特别是在均值和方差方面。平稳性可能是一个比较模糊的概念,将序列排除为不平稳可能比说序列是平稳的更容易。通常不平稳序列有几个特征: …...
<leetcode修炼>双指针训练-移动零
题目: 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 方法1: 快慢指针 快指针负责遍历数组中所有元素,慢指针负责记录不为0的…...
Python初探:从零开始的编程奇妙之旅
一、Python是什么 Python是一门多用途的高级编程语言,以其简洁、易读的语法而脱颖而出。在深度学习领域,Python扮演着至关重要的角色。其丰富的科学计算库(如NumPy、Pandas、Matplotlib)和强大的深度学习框架(如Tenso…...
算法与数据结构之链表<一>(Java)
目录 1、链表的定义 2、链表的特点 3、为何要使用链表 4、数组与链表的区别 5、链表的增删查 5.1、在头部插入链表 5.2、在中间插入链表 5.3、删除头节点 5.4、删除中间节点 5.5、查询某个值 6、链表的应用 6.1 如何设计一个LRU缓存算法? 6.2 约瑟夫问题 1、链表的定…...
目标检测COCO数据集与评价体系mAP
1.mAP 2.IoU IoU也就是交并比,也称为 Jaccard 指数,用于计算真实边界框与预测边界框之间的重叠程度。它是真值框与预测边界框的交集和并集之间的比值。Ground Truth边界框是测试集中手工标记的边界框,用于指定对象图像的位置以及预测的边界框…...
2024最全面且有知识深度的web3开发工具、web3学习项目资源平台
在Web3技术迅速发展的时代,寻找一个综合且深入的Web3开发工具和学习项目资源平台变得至关重要。今天,我将向大家介绍一个非常有价值的网站,它就是https://web3x.world 。 Web3X是一个全面而深入的Web3开发者社区,为开发者们提供了…...
Golang - defer关键字 深入剖析
defer关键字 defer和go一样都是Go语言提供的关键字。defer用于资源的释放,会在函数返回之前进行调用。一般采用如下模式: f,err : os.Open(filename) if err ! nil {panic(err) } defer f.Close()如果有多个defer表达式,调用顺序类似于栈&a…...
如何在Spring Boot中使用@Scheduled写定时任务判断数据量是否过大,过大则进行分表操作,多张表使用临时视图查询
当数据量过大,在定时任务中执行分表操作 1、复制表结构及数据 在xml中编写复制表结构及数据(newTableName为新表名、originalTableName为原始表名) 只复制表结构: CREATE TABLE ${newTableName} AS SELECT * FROM ${originalTa…...
网站备案证明/网络推广外包怎么接单
PHP程序使用mail()函数发送邮件的时候,标题中文的话会出现乱码。 解决方法: 先用函数base64_encode() — 使用 MIME base64 对数据进行编码 标题字符串前加编码类型例如: ?UTF-8?B? 标题字符串后加:? 邮件header说明Content-t…...
国内外做的比较好的家装网站/关键词完整版
2019独角兽企业重金招聘Python工程师标准>>> 一.RabbitMq的术语解释 exchange:交换机,一个交换机可以有多个路由(而每一个路由分别指向一个队列)。 queue:队列,一个队列可以对应多个交换机。 route-key:路由…...
鞍山网站开发公司/优化师是做什么的
北京市控烟行动轰轰烈烈,然而很多老烟民在既往戒烟时遇到过这样一些问题:突然不抽烟,身体反而出现各种不适!甚至社会上一直流传着这样一种说法“突然戒烟会打乱身体平衡,反而对身体不好”!老烟民突然戒烟&a…...
阿里巴巴武汉网站建设/适合奖励自己的网站免费
一直对时间函数有点兴趣,今天打开time.h看了一下.发现内容也不是太多.于是看了看.这是c库里的.C的,改日再看.一边看一边写了总结,呵呵,效果不错. 在 time.h 文件中。首先我们可以看到 typedef long time_t; 这就可以明确地知道 time_t是一个long型 而为什么要这样做呢ÿ…...
深圳博彩软件网站建设/优化设计电子课本下载
//ATK-ESP8266模块测试主函数,检查WIFI模块是否在线 void atk_8266_test(void) {while(atk_8266_send_cmd("AT","OK",200))//检查WIFI模块是否在线{atk_8266_quit_trans();//退出透传atk_8266_send_cmd("ATCIPMODE0","OK",200); //关…...
有什么正网站做兼职的/厦门seo关键词优化
1 ROS必须的环境变量 执行命令: source /opt/ros/ROSDISTRO/setup.bash (Replace ROSDISTRO with the desired ROS distribution, e.g. indigo.)可以完成设置。 当然通常是添加该命令到~/.bashrc,系统启动自动设置这些必须的环境变量。 注意:…...