首页 > 其他分享 >2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠

2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠

时间：2024-01-13 14:35:00浏览次数：50  
标签：vector 油漆匠 int 刷油漆 cost process1 time dp


2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time，

分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠，

一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，

开销为 cost[i] 单位的钱。

一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0，

但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少？

输入：cost = [1,2,3,2], time = [1,2,3,2]。

输出：3。

来自力扣。2742. 给墙壁刷油漆。

答案2024-01-03：

来自左程云。

灵捷3.5

大体过程如下：

paintWalls1 函数

1.paintWalls1 函数是基于递归方法的解决方案。

2.在 process1 函数中，通过递归方式将每种情况下的最小开销计算出来。

3.递归调用时考虑两种情况，选择当前墙刷或者不刷，计算出最小开销。

4.该方法在递归调用的过程中可能会有很多重复计算，效率可能不高。

paintWalls2 函数

1.paintWalls2 函数采用了记忆化搜索的方式。

2.定义了一个二维数组 dp 用于记录已经计算过的结果，避免重复计算。

3.通过递归+记忆化搜索的方式优化了重复计算，提高了效率。

paintWalls3 函数

1.paintWalls3 函数采用了动态规划的方式。

2.使用一个一维数组 dp 保存不同墙数下的最小开销。

3.结合循环和动态递推的方式，迭代计算每墙的最小开销，直到第 n 墙。

时间和空间复杂度

  • 时间复杂度：
  • paintWalls1 使用了递归，可能有大量重复计算，其时间复杂度为 O(2^n)。
  • paintWalls2 和 paintWalls3 使用了记忆化搜索和动态规划，时间复杂度都为 O(n^2)，其中 n 为墙的数量。
  • 空间复杂度：
  • paintWalls1 和 paintWalls2 的额外空间复杂度为 O(n^2)，因为它们都使用了二维数组存储中间结果。
  • paintWalls3 的额外空间复杂度为 O(n)，因为它只用了一个一维数组保存中间结果。

go完整代码如下：

package main

import (
    "fmt"
    "math"
)

// paintWalls1 represents the first function from the given Java code.
func paintWalls1(cost []int, time []int) int {
    return process1(cost, time, 0, len(cost))
}

// process1 is the recursive function as mentioned in the Java code.
func process1(cost []int, time []int, i int, s int) int {
    if s <= 0 {
        return 0
    }
    // s > 0
    if i == len(cost) {
        return math.MaxInt32
    } else {
        p1 := process1(cost, time, i+1, s)
        p2 := math.MaxInt32
        next2 := process1(cost, time, i+1, s-1-time[i])
        if next2 != math.MaxInt32 {
            p2 = cost[i] + next2
        }
        return int(math.Min(float64(p1), float64(p2)))
    }
}

// paintWalls2 is the second function from the given Java code.
func paintWalls2(cost []int, time []int) int {
    n := len(cost)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }
    return process2(cost, time, 0, n, dp)
}

// process2 represents the recursive function in the second approach of the Java code.
func process2(cost []int, time []int, i int, s int, dp [][]int) int {
    if s <= 0 {
        return 0
    }
    if dp[i][s] != -1 {
        return dp[i][s]
    }
    var ans int
    if i == len(cost) {
        ans = math.MaxInt32
    } else {
        p1 := process2(cost, time, i+1, s, dp)
        p2 := math.MaxInt32
        next2 := process2(cost, time, i+1, s-1-time[i], dp)
        if next2 != math.MaxInt32 {
            p2 = cost[i] + next2
        }
        ans = int(math.Min(float64(p1), float64(p2)))
    }
    dp[i][s] = ans
    return ans
}

// paintWalls3 is the third function from the given Java code.
func paintWalls3(cost []int, time []int) int {
    n := len(cost)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    for i := n - 1; i >= 0; i-- {
        for s := n; s >= 1; s-- {
            if s-1-time[i] <= 0 {
                dp[s] = int(math.Min(float64(dp[s]), float64(cost[i])))
            } else if dp[s-1-time[i]] != math.MaxInt32 {
                dp[s] = int(math.Min(float64(dp[s]), float64(cost[i]+dp[s-1-time[i]])))
            }
        }
    }
    return dp[n]
}

func main() {
    cost := []int{1, 2, 3, 2}
    time := []int{1, 2, 3, 2}
    fmt.Println("Result 1:", paintWalls1(cost, time))
    fmt.Println("Result 2:", paintWalls2(cost, time))
    fmt.Println("Result 3:", paintWalls3(cost, time))
}

2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠_算法

rust完整代码如下：

fn paint_walls1(cost: Vec<i32>, time: Vec<i32>) -> i32 {
    process1(&cost, &time, 0, cost.len() as i32)
}

fn process1(cost: &Vec<i32>, time: &Vec<i32>, i: i32, s: i32) -> i32 {
    if s <= 0 {
        return 0;
    }
    if (i as usize) == cost.len() {
        return i32::MAX;
    } else {
        let p1 = process1(cost, time, i + 1, s);
        let mut p2 = i32::MAX;
        let next2 = process1(cost, time, i + 1, s - 1 - time[i as usize]);
        if next2 != i32::MAX {
            p2 = cost[i as usize] + next2;
        }
        return p1.min(p2);
    }
}

fn paint_walls2(cost: Vec<i32>, time: Vec<i32>) -> i32 {
    let n = cost.len();
    let mut dp = vec![vec![-1; n + 1]; n + 1];
    process2(&cost, &time, 0, n as i32, &mut dp)
}

fn process2(cost: &Vec<i32>, time: &Vec<i32>, i: i32, s: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if s <= 0 {
        return 0;
    }
    if dp[i as usize][s as usize] != -1 {
        return dp[i as usize][s as usize];
    }
    let ans;
    if (i as usize) == cost.len() {
        ans = i32::MAX;
    } else {
        let p1 = process2(cost, time, i + 1, s, dp);
        let mut p2 = i32::MAX;
        let next2 = process2(cost, time, i + 1, s - 1 - time[i as usize], dp);
        if next2 != i32::MAX {
            p2 = cost[i as usize] + next2;
        }
        ans = p1.min(p2);
    }
    dp[i as usize][s as usize] = ans;
    ans
}

fn paint_walls3(cost: Vec<i32>, time: Vec<i32>) -> i32 {
    let n = cost.len();
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in (0..n).rev() {
        for s in (1..=n as i32).rev() {
            if s - 1 - time[i] <= 0 {
                dp[s as usize] = dp[s as usize].min(cost[i]);
            } else if dp[(s - 1 - time[i]) as usize] != i32::MAX {
                dp[s as usize] = dp[s as usize].min(cost[i] + dp[(s - 1 - time[i]) as usize]);
            }
        }
    }
    dp[n]
}

fn main() {
    let cost = vec![1, 2, 3, 2];
    let time = vec![1, 2, 3, 2];
    
    let result1 = paint_walls1(cost.clone(), time.clone());
    let result2 = paint_walls2(cost.clone(), time.clone());
    let result3 = paint_walls3(cost.clone(), time.clone());

    println!("Result for paint_walls1: {}", result1);
    println!("Result for paint_walls2: {}", result2);
    println!("Result for paint_walls3: {}", result3);
}

2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠_开发语言_02

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 暴力递归
int process1(vector<int>& cost, vector<int>& time, int i, int s) {
    if (s <= 0) {
        return 0;
    }
    if (i == cost.size()) {
        return INT_MAX;
    }
    else {
        int p1 = process1(cost, time, i + 1, s);
        int p2 = INT_MAX;
        int next2 = process1(cost, time, i + 1, s - 1 - time[i]);
        if (next2 != INT_MAX) {
            p2 = cost[i] + next2;
        }
        return min(p1, p2);
    }
}

int paintWalls1(vector<int>& cost, vector<int>& time) {
    return process1(cost, time, 0, cost.size());
}

// 暴力递归改记忆化搜索
int process2(vector<int>& cost, vector<int>& time, int i, int s, vector<vector<int>>& dp) {
    if (s <= 0) {
        return 0;
    }
    if (dp[i][s] != -1) {
        return dp[i][s];
    }
    int ans;
    if (i == cost.size()) {
        ans = INT_MAX;
    }
    else {
        int p1 = process2(cost, time, i + 1, s, dp);
        int p2 = INT_MAX;
        int next2 = process2(cost, time, i + 1, s - 1 - time[i], dp);
        if (next2 != INT_MAX) {
            p2 = cost[i] + next2;
        }
        ans = min(p1, p2);
    }
    dp[i][s] = ans;
    return ans;
}

int paintWalls2(vector<int>& cost, vector<int>& time) {
    int n = cost.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
    return process2(cost, time, 0, n, dp);
}

// 严格位置依赖的动态规划 + 空间压缩
int paintWalls3(vector<int>& cost, vector<int>& time) {
    int n = cost.size();
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int s = n; s >= 1; s--) {
            if (s - 1 - time[i] <= 0) {
                dp[s] = min(dp[s], cost[i]);
            }
            else if (dp[s - 1 - time[i]] != INT_MAX) {
                dp[s] = min(dp[s], cost[i] + dp[s - 1 - time[i]]);
            }
        }
    }
    return dp[n];
}

int main() {
    vector<int> cost = { 1, 2, 3, 2 };
    vector<int> time = { 1, 2, 3, 2 };

    cout << "Result for paintWalls1: " << paintWalls1(cost, time) << endl;
    cout << "Result for paintWalls2: " << paintWalls2(cost, time) << endl;
    cout << "Result for paintWalls3: " << paintWalls3(cost, time) << endl;

    return 0;
}

2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠_代理模式_03

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int process1(int* cost, int* time, int i, int s, int costSize);

int paintWalls1(int* cost, int costSize, int* time, int timeSize) {
    return process1(cost, time, 0, costSize, costSize);
}

int process1(int* cost, int* time, int i, int s, int costSize) {
    if (s <= 0) {
        return 0;
    }
    if (i == costSize) {
        return INT_MAX;
    }
    else {
        int p1 = process1(cost, time, i + 1, s, costSize);
        int p2 = INT_MAX;
        int next2 = process1(cost, time, i + 1, s - 1 - time[i], costSize);
        if (next2 != INT_MAX) {
            p2 = cost[i] + next2;
        }
        return (p1 < p2) ? p1 : p2;
    }
}

int process2(int* cost, int* time, int i, int s, int costSize, int** dp);

int paintWalls2(int* cost, int costSize, int* time, int timeSize) {
    int** dp = (int**)malloc((costSize + 1) * sizeof(int*));
    for (int i = 0; i <= costSize; i++) {
        dp[i] = (int*)malloc((costSize + 1) * sizeof(int));
        for (int j = 0; j <= costSize; j++) {
            dp[i][j] = -1;
        }
    }
    int result = process2(cost, time, 0, costSize, costSize, dp);
    for (int i = 0; i <= costSize; i++) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

int process2(int* cost, int* time, int i, int s, int costSize, int** dp) {
    if (s <= 0) {
        return 0;
    }
    if (dp[i][s] != -1) {
        return dp[i][s];
    }
    int ans;
    if (i == costSize) {
        ans = INT_MAX;
    }
    else {
        int p1 = process2(cost, time, i + 1, s, costSize, dp);
        int p2 = INT_MAX;
        int next2 = process2(cost, time, i + 1, s - 1 - time[i], costSize, dp);
        if (next2 != INT_MAX) {
            p2 = cost[i] + next2;
        }
        ans = (p1 < p2) ? p1 : p2;
    }
    dp[i][s] = ans;
    return ans;
}

int paintWalls3(int* cost, int costSize, int* time, int timeSize);

int paintWalls3(int* cost, int costSize, int* time, int timeSize) {
    int* dp = (int*)malloc((costSize + 1) * sizeof(int));
    for (int i = 0; i <= costSize; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    for (int i = costSize - 1; i >= 0; i--) {
        for (int s = costSize; s >= 1; s--) {
            if (s - 1 - time[i] <= 0) {
                dp[s] = (dp[s] < cost[i]) ? dp[s] : cost[i];
            }
            else if (dp[s - 1 - time[i]] != INT_MAX) {
                dp[s] = (dp[s] < cost[i] + dp[s - 1 - time[i]]) ? dp[s] : cost[i] + dp[s - 1 - time[i]];
            }
        }
    }
    int result = dp[costSize];
    free(dp);
    return result;
}

int main() {
    int cost[] = { 1, 2, 3, 2 };
    int time[] = { 1, 2, 3, 2 };

    int result1 = paintWalls1(cost, 4, time, 4);
    printf("Result of paintWalls1: %d\n", result1);

    int result2 = paintWalls2(cost, 4, time, 4);
    printf("Result of paintWalls2: %d\n", result2);

    int result3 = paintWalls3(cost, 4, time, 4);
    printf("Result of paintWalls3: %d\n", result3);
    return 0;
}

2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠_代理模式_04


标签：vector,油漆匠,int,刷油漆,cost,process1,time,dp
From： https://blog.51cto.com/moonfdd/9232393

相关文章

  • 2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示
    2024-01-03：用go语言，给你两个长度为n下标从0开始的整数数组cost和time，分别表示给n堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠，一位需要付费的油漆匠，刷第i堵墙需要花费time[i]单位的时间，开销为cost[i]单位的钱。一位免费的油漆匠，刷任意一堵墙的时间为1......
  • Reinforcement Learning in Energy Management: Optimizing Grid Operations and Redu
    1.背景介绍Reinforcementlearning(RL)isasubfieldofmachinelearningthatfocusesonhowagentsoughttotakeactionsinanenvironmentinordertomaximizesomenotionofcumulativereward.Inrecentyears,reinforcementlearninghasbeenappliedtoawid......
  • Cost Calculator Builder PRO v3.1.46 已注册 – WordPress 插件
    成本计算器生成器PROv3.1.46：WordPress插件全解析一、插件概述"成本计算器生成器PROv3.1.46"是一款强大的WordPress插件，专为需要创建报价、价格和项目估算表的用户设计。这款插件集成了众多高级功能，可帮助用户高效地管理他们的成本和价格，从而提供准确的报价估算。二、条......
  • 题解 LGP7294【[USACO21JAN] Minimum Cost Paths P】/ accoders::NOI 5696【棋子】
    problemFarmerJohn的牧草地可以看作是一个\(N×M\)（\(2≤N≤10^9,2≤M≤2⋅10^5\)）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于\(x∈[1,N],y∈[1,M]\)，从上往下第\(x\)行、从左往右第\(y\)列的方格记为\((x,y)\)。此外，对于每一个\(y∈[1,M]\)，第\(y\)列拥有一个......
  • HarmonyOS第一课，配置DevEcoStudio，运行"哈喽word"
    1下载DevEcoStudio工具下载地址根据自己电脑的os和芯片版本，下载对应的安装包，顺便也把其他2个开发者工具也下载下来了2运行DevEcoStudio，并配置相关环境变量如果自检有不满足的环境配置，可以在线安装至指定文件夹，强迫症请准备好指定路径存放npm及ohpm安装路径安装HarmonyOS-Sd......
  • [粘贴]Introducing Exadata X9M: Dramatically Faster, More Cost Effective, and Eas
    https://blogs.oracle.com/exadata/post/exadata-x9m  TheExadataProductManagementandDevelopmentteamsareexcitedtoannouncethenextgenerationofExadataDatabaseMachineplatform,the OracleExadataDatabaseMachineX9M. Built onoverade......
  • [翻译]——How the MySQL Optimizer Calculates the Cost of a Query (Doc ID 1327497
    本文是对这篇文章HowtheMySQLOptimizerCalculatestheCostofaQuery(DocID1327497.1)[1]的翻译，翻译如有不当的地方，敬请谅解，请尊重原创和翻译劳动成果，转载的时候请注明出处。谢谢！适用于：MySQL4.0及后续更高的版本本文档中的内容适用于任何平台。目标了解MySQL优化器如......
  • 什么是云计算领域的 TCO - Total Cost of Ownership
    TCO，全称为"TotalCostofOwnership"，在中文中常译为"总拥有成本"。在云计算领域，TCO是一个极为重要的概念，它包括了从采购、部署、运维到退役整个生命周期内的所有成本。这包括硬件、软件的购买、安装、维护、升级、人工、能源、设施等成本，以及可能的额外成本，比如时间成本、......
  • Cost Aggregation with Transformers for Sparse Correspondence-读书笔记
    CostAggregationwithTransformersforSparseCorrespondence:2022背景:该论文结合了SuperGlue和CATs，将里面所有手工制作的部分都代替了。将CATs引入该模型，用Transformer取代手工制作的成本聚合方法，用于具有自关注层全局接受域的可学习成本聚合。（PS：成本聚合：成本聚合是指在立......
  • 基于costas环的载波同步系统matlab性能仿真
    1.算法运行效果图预览  2.算法运行软件版本matlab2022a  3.算法理论概述       基于Costas环的载波同步系统是一种用于恢复接收信号的载波频率和相位同步的系统。Costas环是一种特殊的环路锁相环路，广泛用于调制解调器、无线通信和雷达等领域。以下是基于C......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99