Go
话题列表 社区 Wiki 优质外文 招聘求职 Go 实战教程 社区文档
登录
注册

2024-04-03：用go语言，在一个小城市里，有 m 个房子排成一排， 你需要给每个房子涂上 n 种颜色之一

moonfdd 的个人博客 / 0 / 0 / 创建于 11个月前

2024-04-03：用 go 语言，在一个小城市里，有 m 个房子排成一排，

你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n )，

有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色，

我们将连续相同颜色尽可能多的房子称为一个街区。

比方说 houses = [1,2,2,3,3,2,1,1]，

它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}]。

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target，其中：

houses [i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色，

cost [i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。

如果没有可用的涂色方案，请返回 -1。

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3。

输出：9。

答案 2024-04-03：

来自左程云。

灵捷 3.5

大体步骤如下：#

minCost1 函数：

1. 首先，创建一个三维数组 dp，用于记录状态转移的结果。dp [i][k][c] 表示将前 i 个房子涂色，形成 k 个街区，并且第 i 个房子颜色为 c+1 时的最小总花费。

2. 然后，调用 process1 函数，进行递归计算。

3. 在 process1 函数中，首先处理边界情况：如果 k 小于 0，返回无穷大；如果 i 等于房子数量，如果 k 等于 0，返回 0，否则返回无穷大。

4. 如果 dp [i][k][c] 已经计算过，直接返回结果。

5. 接着，判断第 i 个房子的颜色是否已经确定（houses [i] != 0）：

  • 如果颜色已经确定，判断该颜色是否与 c 相同，分别递归处理下一个房子（i+1）和剩余街区数量（k-1 或 k）。

  • 如果颜色未确定，遍历每种可能的颜色（1 到 n），分别递归处理下一个房子和剩余街区数量，并记录选择花费最小的方案。

6. 将结果存入 dp [i][k][c]，并返回结果。

minCost2 函数：

1. 创建一个二维数组 dp，用于记录状态转移的结果。dp [k][c] 表示形成 k 个街区，且最后一个房子颜色为 c+1 时的最小总花费。

2. 首先初始化 dp 数组：对于 k=0（没有街区）和所有的颜色 c，花费为 0；对于 k>0 和所有的颜色 c，花费初始化为无穷大。

3. 然后，从后向前遍历房子，处理每个房子的情况：

  • 如果房子颜色已经确定（houses [i] != 0），更新 dp 数组中对应位置的值。

  • 如果房子颜色未确定，通过 dp 数组中记录的上一次的结果，计算每个街区数量和颜色的最小花费，更新 dp 数组中对应位置的值。

4. 最后，返回 dp [target][0] 的结果，如果为无穷大则返回 - 1。

minCost3 函数：

1. 创建一个二维数组 dp，用于记录状态转移的结果。dp [k][c] 表示形成 k 个街区，且最后一个房子颜色为 c+1 时的最小总花费。

2. 首先初始化 dp 数组和辅助数组 minl 和 minr：

  • 对于 k=0（没有街区）和所有的颜色 c，花费为 0；

  • 对于 k>0 和所有的颜色 c，花费初始化为无穷大；

  • minl [i] 表示前 i 个颜色中最小的花费，minr [i] 表示从第 i 个颜色到第 n 个颜色中最小的花费。

3. 然后，从后向前遍历房子，处理每个房子的情况：

  • 如果房子颜色已经确定（houses [i] != 0），更新 dp 数组中对应位置的值。

  • 如果房子颜色未确定，通过 dp 数组中记录的上一次的结果和辅助数组 minl 和 minr，计算每个街区数量和颜色的最小花费，更新 dp 数组中对应位置的值。

4. 最后，返回 dp [target][0] 的结果，如果为无穷大则返回 - 1。

这 3 种算法的时间复杂度和空间复杂度如下：

  • minCost1：时间复杂度为 O (m * n^target)，空间复杂度为 O (m * target * n)。

  • minCost2：时间复杂度为 O (m * target * n^2)，空间复杂度为 O (target * n)。

  • minCost3：时间复杂度为 O (m * target * n^2)，空间复杂度为 O (n)。

Go 完整代码如下：#

package main

import (
    "fmt"
    "math"
)

func minCost1(houses []int, cost [][]int, m int, n int, target int) int {
    dp := make([][][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([][]int, target+1)
        for k := 0; k <= target; k++ {
            dp[i][k] = make([]int, n+1)
            for c := 0; c <= n; c++ {
                dp[i][k][c] = -1
            }
        }
    }
    ans := process1(houses, cost, n, 0, target, 0, dp)
    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

func process1(houses []int, cost [][]int, n, i, k, c int, dp [][][]int) int {
    if k < 0 {
        return math.MaxInt32
    }
    if i == len(houses) {
        if k == 0 {
            return 0
        }
        return math.MaxInt32
    }
    if dp[i][k][c] != -1 {
        return dp[i][k][c]
    }
    ans := math.MaxInt32
    if houses[i] != 0 {
        if houses[i] != c {
            ans = process1(houses, cost, n, i+1, k-1, houses[i], dp)
        } else {
            ans = process1(houses, cost, n, i+1, k, houses[i], dp)
        }
    } else {
        for fill := 1; fill <= n; fill++ {
            var next int
            if fill == c {
                next = process1(houses, cost, n, i+1, k, fill, dp)
            } else {
                next = process1(houses, cost, n, i+1, k-1, fill, dp)
            }
            if next != math.MaxInt32 {
                ans = min(ans, cost[i][fill-1]+next)
            }
        }
    }
    dp[i][k][c] = ans
    return ans
}

func minCost2(houses []int, cost [][]int, m int, n int, target int) int {
    dp := make([][]int, target+1)
    for k := range dp {
        dp[k] = make([]int, n+1)
    }
    for c := 0; c <= n; c++ {
        dp[0][c] = 0
    }
    for k := 1; k <= target; k++ {
        for c := 0; c <= n; c++ {
            dp[k][c] = math.MaxInt32
        }
    }
    memo := make([]int, n+1)
    for i := m - 1; i >= 0; i-- {
        if houses[i] != 0 {
            houseColor := houses[i]
            for k := target; k >= 0; k-- {
                memory := dp[k][houseColor]
                for c := 0; c <= n; c++ {
                    if houseColor != c {
                        if k == 0 {
                            dp[k][c] = math.MaxInt32
                        } else {
                            dp[k][c] = dp[k-1][houseColor]
                        }
                    } else {
                        dp[k][c] = memory
                    }
                }
            }
        } else {
            for k := target; k >= 0; k-- {
                for c := 0; c <= n; c++ {
                    memo[c] = dp[k][c]
                }
                for c := 0; c <= n; c++ {
                    ans := math.MaxInt32
                    for fill := 1; fill <= n; fill++ {
                        var next int
                        if fill == c {
                            next = memo[fill]
                        } else {
                            if k == 0 {
                                next = math.MaxInt32
                            } else {
                                next = dp[k-1][fill]
                            }
                        }
                        if next != math.MaxInt32 {
                            ans = min(ans, cost[i][fill-1]+next)
                        }
                    }
                    dp[k][c] = ans
                }
            }
        }
    }
    if dp[target][0] == math.MaxInt32 {
        return -1
    }
    return dp[target][0]
}

func minCost3(houses []int, cost [][]int, m int, n int, target int) int {
    dp := make([][]int, target+1)
    for k := range dp {
        dp[k] = make([]int, n+1)
    }
    for c := 0; c <= n; c++ {
        dp[0][c] = 0
    }
    for k := 1; k <= target; k++ {
        for c := 0; c <= n; c++ {
            dp[k][c] = math.MaxInt32
        }
    }
    memo := make([]int, n+1)
    minl := make([]int, n+2)
    minr := make([]int, n+2)
    minr[n+1] = math.MaxInt32
    minl[n+1] = minr[n+1]
    minr[0] = minl[n+1]
    minl[0] = minr[0]
    for i := m - 1; i >= 0; i-- {
        if houses[i] != 0 {
            for k, memory := target, 0; k >= 0; k-- {
                memory = dp[k][houses[i]]
                for c := 0; c <= n; c++ {
                    if houses[i] != c {
                        if k == 0 {
                            dp[k][c] = math.MaxInt32
                        } else {
                            dp[k][c] = dp[k-1][houses[i]]
                        }
                    } else {
                        dp[k][c] = memory
                    }
                }
            }
        } else {
            for k := target; k >= 0; k-- {
                for c := 0; c <= n; c++ {
                    memo[c] = dp[k][c]
                }
                for fill := 1; fill <= n; fill++ {
                    if k == 0 || dp[k-1][fill] == math.MaxInt32 {
                        minl[fill] = minl[fill-1]
                    } else {
                        minl[fill] = min(minl[fill-1], cost[i][fill-1]+dp[k-1][fill])
                    }
                }
                for fill := n; fill >= 1; fill-- {
                    if k == 0 || dp[k-1][fill] == math.MaxInt32 {
                        minr[fill] = minr[fill+1]
                    } else {
                        minr[fill] = min(minr[fill+1], cost[i][fill-1]+dp[k-1][fill])
                    }
                }
                for c, ans := 0, 0; c <= n; c++ {
                    if c == 0 || memo[c] == math.MaxInt32 {
                        ans = math.MaxInt32
                    } else {
                        ans = cost[i][c-1] + memo[c]
                    }
                    if c > 0 {
                        ans = min(ans, minl[c-1])
                    }
                    if c < n {
                        ans = min(ans, minr[c+1])
                    }
                    dp[k][c] = ans
                }
            }
        }
    }
    if dp[target][0] != math.MaxInt32 {
        return dp[target][0]
    }
    return -1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    houses := []int{0, 0, 0, 0, 0}
    cost := [][]int{{1, 10}, {10, 1}, {10, 1}, {1, 10}, {5, 1}}
    m := 5
    n := 2
    target := 3

    fmt.Println(minCost1(houses, cost, m, n, target))
    fmt.Println(minCost2(houses, cost, m, n, target))
    fmt.Println(minCost3(houses, cost, m, n, target))
}

在这里插入图片描述

Python 完整代码如下：#

# -*-coding:utf-8-*-

import sys

def minCost1(houses, cost, m, n, target):
    dp = [[[-1] * (n + 1) for _ in range(target + 1)] for _ in range(m)]
    ans = process1(houses, cost, n, 0, target, 0, dp)
    if ans == sys.maxsize:
        return -1
    return ans

def process1(houses, cost, n, i, k, c, dp):
    if k < 0:
        return sys.maxsize
    if i == len(houses):
        if k == 0:
            return 0
        return sys.maxsize
    if dp[i][k][c] != -1:
        return dp[i][k][c]
    ans = sys.maxsize
    if houses[i] != 0:
        if houses[i] != c:
            ans = process1(houses, cost, n, i + 1, k - 1, houses[i], dp)
        else:
            ans = process1(houses, cost, n, i + 1, k, houses[i], dp)
    else:
        for fill in range(1, n + 1):
            if fill == c:
                next = process1(houses, cost, n, i + 1, k, fill, dp)
            else:
                next = process1(houses, cost, n, i + 1, k - 1, fill, dp)
            if next != sys.maxsize:
                ans = min(ans, cost[i][fill - 1] + next)
    dp[i][k][c] = ans
    return ans

def minCost2(houses, cost, m, n, target):
    dp = [[0] * (n + 1) for _ in range(target + 1)]
    for c in range(n + 1):
        dp[0][c] = 0
    for k in range(1, target + 1):
        for c in range(n + 1):
            dp[k][c] = sys.maxsize
    memo = [0] * (n + 1)
    for i in range(m - 1, -1, -1):
        if houses[i] != 0:
            houseColor = houses[i]
            for k in range(target, -1, -1):
                memory = dp[k][houseColor]
                for c in range(n + 1):
                    if houseColor != c:
                        if k == 0:
                            dp[k][c] = sys.maxsize
                        else:
                            dp[k][c] = dp[k - 1][houseColor]
                    else:
                        dp[k][c] = memory
        else:
            for k in range(target, -1, -1):
                for c in range(n + 1):
                    memo[c] = dp[k][c]
                for c in range(n + 1):
                    ans = sys.maxsize
                    for fill in range(1, n + 1):
                        if fill == c:
                            next = memo[fill]
                        else:
                            if k == 0:
                                next = sys.maxsize
                            else:
                                next = dp[k - 1][fill]
                        if next != sys.maxsize:
                            ans = min(ans, cost[i][fill - 1] + next)
                    dp[k][c] = ans
    if dp[target][0] == sys.maxsize:
        return -1
    return dp[target][0]

def minCost3(houses, cost, m, n, target):
    dp = [[0] * (n + 1) for _ in range(target + 1)]
    for c in range(n + 1):
        dp[0][c] = 0
    for k in range(1, target + 1):
        for c in range(n + 1):
            dp[k][c] = sys.maxsize
    memo = [0] * (n + 1)
    minl = [sys.maxsize] * (n + 2)
    minr = [sys.maxsize] * (n + 2)
    minl[n + 1] = minr[n + 1] = sys.maxsize
    minl[0] = minr[0] = sys.maxsize
    for i in range(m - 1, -1, -1):
        if houses[i] != 0:
            for k in range(target, -1, -1):
                memory = dp[k][houses[i]]
                for c in range(n + 1):
                    if houses[i] != c:
                        if k == 0:
                            dp[k][c] = sys.maxsize
                        else:
                            dp[k][c] = dp[k - 1][houses[i]]
                    else:
                        dp[k][c] = memory
        else:
            for k in range(target, -1, -1):
                for c in range(n + 1):
                    memo[c] = dp[k][c]
                for fill in range(1, n + 1):
                    if k == 0 or dp[k - 1][fill] == sys.maxsize:
                        minl[fill] = minl[fill - 1]
                    else:
                        minl[fill] = min(minl[fill - 1], cost[i][fill - 1] + dp[k - 1][fill])
                for fill in range(n, 0, -1):
                    if k == 0 or dp[k - 1][fill] == sys.maxsize:
                        minr[fill] = minr[fill + 1]
                    else:
                        minr[fill] = min(minr[fill + 1], cost[i][fill - 1] + dp[k - 1][fill])
                for c in range(n + 1):
                    if c == 0 or memo[c] == sys.maxsize:
                        ans = sys.maxsize
                    else:
                        ans = cost[i][c - 1] + memo[c]
                    if c > 0:
                        ans = min(ans, minl[c - 1])
                    if c < n:
                        ans = min(ans, minr[c + 1])
                    dp[k][c] = ans
    if dp[target][0] != sys.maxsize:
        return dp[target][0]
    return -1

def min(a, b):
    return a if a < b else b

houses = [0, 0, 0, 0, 0]
cost = [[1, 10], [10, 1], [10, 1], [1, 10], [5, 1]]
m = 5
n = 2
target = 3

print(minCost1(houses, cost, m, n, target))
print(minCost2(houses, cost, m, n, target))
print(minCost3(houses, cost, m, n, target))

在这里插入图片描述

本作品采用《CC 协议》，转载必须注明作者和本文链接
微信公众号：福大大架构师每日一题。最新面试题，涉及 golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。
moonfdd
1.0k 声望
微信公众号：福大大架构师每日一题。最新面试题，涉及golang，rust，mysq...
讨论数量: 0
排序：
时间 投票
(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！
支持 MD 帮助
moonfdd
未填写
文章
488
粉丝
23
喜欢
39
收藏
22
排名：441
访问：2.1 万
私信
所有博文
文章归档
2 篇 2025 年 3 月 4 篇 2025 年 1 月 3 篇 2024 年 6 月 7 篇 2024 年 5 月 7 篇 2024 年 4 月 9 篇 2024 年 3 月 3 篇 2024 年 2 月 10 篇 2024 年 1 月 9 篇 2023 年 12 月 9 篇 2023 年 11 月 8 篇 2023 年 10 月 11 篇 2023 年 9 月 14 篇 2023 年 8 月 26 篇 2023 年 7 月 35 篇 2023 年 6 月 51 篇 2023 年 5 月 43 篇 2023 年 4 月 13 篇 2023 年 3 月 15 篇 2023 年 2 月 15 篇 2023 年 1 月 31 篇 2022 年 12 月 30 篇 2022 年 11 月 31 篇 2022 年 10 月 31 篇 2022 年 9 月 30 篇 2022 年 8 月 32 篇 2022 年 7 月 9 篇 2022 年 6 月
最新文章 最受欢迎
3周前 绝了！k3s (k8s) 安装 ollama 运行 deepseek 全流程揭秘，yaml全公开 1个月前 Go1.24版本终于来了！各位开发者，准备好迎接这些激动人心的新功能了吗？ 2个月前 2025-01-22：使二进制数组全部等于 1 的最少操作次数Ⅱ。用go语言，给定一个二进制数组 nums 2个月前 2025-01-18：施咒的最大总伤害。用go语言，一个魔法师掌握了多种不同的咒语，每个咒语对应一个伤害值 2个月前 2025-01-15：执行操作可获得的最大总奖励 Ⅰ
4 2023-06-19：讲一讲Redis分布式锁的实现？ 3 音视频八股文（1）--音视频基础 3 2022-11-29：查找重复的电子邮箱。以下数据中a@b.com是重复的，请写出sql语句 2 2022-06-22：golang选择题，以下golang代码输出什么？A：3；B：1；C：4；D：编译失败 2 node可以用nvm快速切换版本，golang如何快速切换版本？用gvm就行。
社区赞助商
成为赞助商

关于 LearnKu

LearnKu 是终身编程者的修道场
做最专业、严肃的技术论坛
LearnKu 诞生的故事

资源推荐

  • 《社区使用指南》
  • 《文档撰写指南》
  • 《LearnKu 社区规范》
  • 《提问的智慧》

    • 服务提供商

    其他信息

  • 成为版主
  • 所有测验
  • 联系站长（反馈建议）

    • 粤ICP备18099781号-6 | 粤公网安备 44030502004330号 | 违法和不良信息举报

    由 Summer 设计和编码 ❤

    请登录

    内容举报
    匿名举报，为防止滥用，仅管理员可见举报者。

    我要举报该，理由是：

    取消