正文

[LeetCode] Paint House I & II

IP云
IP云V管理员/5 阅读
10/04
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if (costs.empty()) return ;
for (int i = ; i < costs.size(); ++i) {
for (int j = ; j < ; ++j) {
costs[i][j] += min(costs[i-][(j+)%], costs[i-][(j+)%]);
}
}
return min(costs.back()[], min(costs.back()[], costs.back()[]));
}
};

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2]is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty() || costs[].empty()) return ;
int n = costs.size(), k = costs[].size();
vector<int> min1(k), min2(k);
for (int i = ; i < costs.size(); ++i) {
min1[] = INT_MAX;
for (int j = ; j < k; ++j) {
min1[j] = min(min1[j-], costs[i-][j-]);
}
min2[k-] = INT_MAX;
for (int j = k - ; j >= ; --j) {
min2[j] = min(min2[j+], costs[i-][j+]);
}
for (int j = ; j < k; ++j) {
costs[i][j] += min(min1[j], min2[j]);
}
}
int res = INT_MAX;
for (auto c : costs.back()) {
res = min(res, c);
}
return res;
}
};

快速找到数组中去掉某个元素的最小值方法：定义两个数组，min1[i]与min2[i]分别记录从左向右到第i位与从右向左到第i位的区间最小值，那么去掉第i位的最小值就是min(min1[i], min2[i])。

[LeetCode] Paint House I & II的更多相关文章

  1. LeetCode Single Number I &sol; II &sol; III

    [1]LeetCode 136 Single Number 题意:奇数个数,其中除了一个数只出现一次外,其他数都是成对出现,比如1,2,2,3,3...,求出该单个数. 解法:容易想到异或的性质,两个 ...

  2. &lbrack;array&rsqb; leetcode - 40&period; Combination Sum II - Medium

    leetcode - 40. Combination Sum II - Medium descrition Given a collection of candidate numbers (C) an ...

  3. LeetCode 137&period; Single Number II&lpar;只出现一次的数字 II&rpar;

    LeetCode 137. Single Number II(只出现一次的数字 II)

  4. LeetCode：路径总和II【113】

    LeetCode:路径总和II[113] 题目描述 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径. 说明: 叶子节点是指没有子节点的节点. 示例:给定如下二叉树, ...

  5. LeetCode：组合总数II【40】

    LeetCode:组合总数II[40] 题目描述 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合. candi ...

  6. &lbrack;LeetCode&rsqb; Paint House II 粉刷房子之二

    There are a row of n houses, each house can be painted with one of the k colors. The cost of paintin ...

  7. LeetCode Paint House II

    原题链接在这里:https://leetcode.com/problems/paint-house-ii/ 题目: There are a row of n houses, each house ca ...

  8. &lbrack;LeetCode&rsqb; Paint Fence 粉刷篱笆

    There is a fence with n posts, each post can be painted with one of the k colors. You have to paint ...

  9. &lbrack;LeetCode&rsqb; Paint House 粉刷房子

    There are a row of n houses, each house can be painted with one of the three colors: red, blue or gr ...

随机推荐

  1. strtok&amp&semi;strsep

    strtok,strtok_r,strsep--extract tokens from strings Tje strsep() function was introduced as a replac ...

  2. gen&lowbar;grant&lowbar;exec&period;sql

    set echo off feedback off verify off pagesize 0 linesize 120 define v_grantee                 = &amp ...

  3. CREELINKS平台&lowbar;处理器CeGpio资源使用说明&lpar;CeGpio的配置与使用&rpar;

    0x00 CREELINKS平台简介     CREELINKS(创e联)是由大信科技有限公司研发,集合软硬件.操作系统.数据云储存.开发工具于一体,用于物联网产品的设计.研发与生产的平台.    平 ...

  4. 运行python &OpenCurlyDoubleQuote;没有那个文件或目录3” 或 &OpenCurlyDoubleQuote;&sol;usr&sol;local&sol;bin&sol;python3&Hat;M&colon; bad interpreter&colon; 没有那个文件或目录” 错误

    原因 如果使用的是#!/usr/local/bin/python3这种方式,就会出现 “/usr/local/bin/python3^M: bad interpreter: 没有那个文件或目录” 错误 ...

  5. idea的起步配置

    工欲善其事,必先利其器 1.安装 https://www.jetbrains.com/idea/download/#section=windows 可以选择不同平台的安装包,版本一般Ultimate, ...

  6. ASP&period;NET HTTP 协议

    http是无状态的,不会记得“上个请求***”,所以哪怕是同一个页面中的js.css.jpg也都要重复的提交Accept-Language.Accept-Encoding.Cookie等. 一般情况下 ...

  7. Android逆向 Android平台虚拟机

    一 Dalvik:是Google开发运行在Android平台的Java虚拟机, Android程序编译后会生成dex文件.Dalvik虚拟机下运行Java时,要将字节码通过即时编译器(just in ...

  8. MySQL数据库应用 从入门到精通 学习笔记

    以下内容是学习<MySQL数据库应用 从入门到精通>过程中总结的一些内容提要,供以后自己复现使用. 一:数据库查看所有数据库: SHOW DATABASES创建数据库: CREATE DA ...

  9. 《Head First 设计模式》之状态模式——糖果机

    状态模式(State) ——允许对象在内部状态时改变它的行为,对象看起来好像修改了它的类. 策略模式与状态模式的区别 状态主体(拥有者)持有状态对象,运行时可以通过动态指定状态对象来改变类的行为 策略 ...

  10. python基础实践（二）

    -*-越简单越快乐-*-# -*- coding:utf-8 -*-# Author:sweeping-monkQuestion_1 = "python中的整数运算"Method_ ...