首页 > 其他分享 >2023-10-18:用go语言,给定一个数组arr,长度为n,表示有0~n-1号设备, arr[i]表示i号设备的型号,型号的种类从0~k-1,一共k种型号, 给定一个k*k的矩阵map,来表示型号

2023-10-18:用go语言,给定一个数组arr,长度为n,表示有0~n-1号设备, arr[i]表示i号设备的型号,型号的种类从0~k-1,一共k种型号, 给定一个k*k的矩阵map,来表示型号

时间:2023-10-18 17:12:32浏览次数:129  
标签:arr cost int 给定 型号 heap position

2023-10-18:用go语言,给定一个数组arr,长度为n,表示有0~n-1号设备,

arr[i]表示i号设备的型号,型号的种类从0~k-1,一共k种型号,

给定一个k*k的矩阵map,来表示型号之间的兼容情况,

map[a][b] == 1,表示a型号兼容b型号,

map[a][b] == 0,表示a型号不兼容b型号,

兼容关系是有向图,也就是a型号兼容b型号,不代表b型号同时兼容a型号,

如果i设备的型号兼容j设备的型号,那么可以从i设备修建一条去往j设备的线路,

修建线路的代价是i设备到j设备的距离:|i-j|,

你的目标是从0号设备到达n-1号设备,并不一定每个设备都联通,只需要到达即可。

返回最小的修建代价,如果就是无法到达返回-1。

1 <= n <= 1000,

1 <= k <= 50。

来自招商银行。

来自左程云

答案2023-10-18:

大体步骤:

1.创建一个二维切片 own,长度为 k,用于记录每个型号的设备编号。

2.创建一个二维切片 nexts,长度为 k,用于记录每个型号兼容的下一个型号。

3.遍历数组 arr,将每个设备的编号添加到对应型号的 own 中。

4.遍历兼容矩阵 m,将每个型号兼容的下一个型号添加到对应型号的 nexts 中。

5.创建一个二叉堆 heap,并定义排序函数,按照修建代价升序排列。

6.将起始设备 (0, 0) 添加到堆中,表示从 0 号设备开始,修建代价为 0。

7.创建一个长度为 n 的布尔型切片 visited,用于标记设备是否被访问过。

8.当堆不为空时,进行以下操作:

  • 弹出堆顶元素 t,表示当前位置和当前的修建代价。

  • 获取当前位置 cur 的设备编号和修建代价。

  • 如果当前位置为目标位置 n-1,则返回当前的修建代价。

  • 将当前位置标记为已访问。

9.获取当前设备的型号 model

10.遍历下一个兼容的型号 nextModel,以及拥有下一个型号 nextModel 的设备位置 nextPosition

 - 如果设备位置未被访问过,则将 `(nextPosition, cost + abs(nextPosition, position))` 添加到堆中。

11.如果无法到达目标位置,返回 -1。

12.在 main 函数中调用 minCost 函数,并输出结果。

总的时间复杂度为 $O(nk^2logn)$,其中 n 是设备数量,k 是型号数量。遍历拥有型号的设备位置的过程复杂度为 O(n),堆操作的复杂度为 O(logn),遍历所有可能的型号和设备位置的复杂度为 $O(k^2$),所以总的时间复杂度为 $O(nk^2logn)$。

总的额外空间复杂度为 O(n),其中 n 是设备数量。需要额外的空间来存储 ownnextsvisited 和堆 heap,它们的空间复杂度都为 O(n)。

go完整代码如下:

package main

import (
	"fmt"

	"github.com/emirpasic/gods/trees/binaryheap"
)

func minCost(arr []int, m [][]int, n int, k int) int {
	// 0 : {4,7,13,26}
	// 1 : {5,45,3,17}
	own := make([][]int, k)
	nexts := make([][]int, k)
	for i := 0; i < k; i++ {
		own[i] = []int{}
		nexts[i] = []int{}
	}

	for i := 0; i < n; i++ {
		own[arr[i]] = append(own[arr[i]], i)
	}

	for i := 0; i < k; i++ {
		for j := 0; j < k; j++ {
			if m[i][j] == 1 {
				nexts[i] = append(nexts[i], j)
			}
		}
	}

	heap := binaryheap.NewWith(func(a, b interface{}) int {
		return a.([]int)[1] - b.([]int)[1]
	})
	heap.Push([]int{0, 0})

	visited := make([]bool, n)

	for heap.Size() > 0 {
		t, _ := heap.Pop()
		cur := t.([]int)
		position := cur[0]
		cost := cur[1]

		if !visited[position] {
			visited[position] = true

			if position == n-1 {
				return cost
			}

			model := arr[position]

			for _, nextModel := range nexts[model] {
				for _, nextPosition := range own[nextModel] {
					if !visited[nextPosition] {
						heap.Push([]int{nextPosition, cost + abs(nextPosition, position)})
					}
				}
			}
		}
	}

	return -1
}

func abs(a, b int) int {
	if a-b < 0 {
		return b - a
	}
	return a - b
}

func main() {
	arr := []int{0, 1, 2, 3}
	m := [][]int{{0, 1, 0, 1, 0}, {1, 0, 1, 1, 0}, {2, 1, 1, 1, 1}, {3, 0, 0, 0, 0}}
	n := 4
	k := 4
	result := minCost(arr, m, n, k)
	fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn min_cost(arr: &[i32], map: &[Vec<i32>], n: usize, k: usize) -> i32 {
    let mut own: Vec<Vec<i32>> = vec![Vec::new(); k];
    let mut nexts: Vec<Vec<i32>> = vec![Vec::new(); k];

    for (i, &value) in arr.iter().enumerate() {
        own[value as usize].push(i as i32);
    }

    for (i, row) in map.iter().enumerate() {
        for (j, &value) in row.iter().enumerate() {
            if value == 1 {
                nexts[i as usize].push(j as i32);
            }
        }
    }

    let mut heap: BinaryHeap<(i32, i32)> = BinaryHeap::new();
    heap.push((0, 0));
    let mut visited: Vec<bool> = vec![false; n];

    while let Some((position, cost)) = heap.pop() {
        let position = position as usize;
        let cost = cost;

        if !visited[position] {
            visited[position] = true;

            if position == n - 1 {
                return cost;
            }

            let model = arr[position] as usize;

            for &next_model in &nexts[model] {
                for &next_position in &own[next_model as usize] {
                    if !visited[next_position as usize] {
                        heap.push((
                            next_position,
                            cost + (next_position - position as i32).abs(),
                        ));
                    }
                }
            }
        }
    }

    -1
}

fn main() {
    let arr = [0, 1, 2, 3];
    let m = [
        vec![0, 1, 0, 1, 0],
        vec![1, 0, 1, 1, 0],
        vec![2, 1, 1, 1, 1],
        vec![3, 0, 0, 0, 0],
    ];
    let n = 4;
    let k = 4;

    let result = min_cost(&arr, &m, n, k);
    println!("Minimum Cost: {}", result);
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

int minCost(vector<int>& arr, vector<vector<int>>& map, int n, int k) {
    vector<vector<int>> own(k);
    vector<vector<int>> nexts(k);
    for (int i = 0; i < n; i++) {
        own[arr[i]].push_back(i);
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (map[i][j] == 1) {
                nexts[i].push_back(j);
            }
        }
    }
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> heap;
    heap.push({ 0, 0 });
    vector<bool> visited(n, false);
    while (!heap.empty()) {
        vector<int> cur = heap.top();
        heap.pop();
        int position = cur[0];
        int cost = cur[1];
        if (!visited[position]) {
            visited[position] = true;
            if (position == n - 1) {
                return cost;
            }
            int model = arr[position];
            for (int nextModel : nexts[model]) {
                for (int nextPosition : own[nextModel]) {
                    if (!visited[nextPosition]) {
                        heap.push({ nextPosition, cost + abs(nextPosition - position) });
                    }
                }
            }
        }
    }
    return -1;
}

int main() {
    vector<int> arr = { 0, 1, 2, 3 };
    vector<vector<int>> m = { {0, 1, 0, 1, 0}, {1, 0, 1, 1, 0}, {2, 1, 1, 1, 1}, {3, 0, 0, 0, 0} };
    int n = 4;
    int k = 4;

    int result = minCost(arr, m, n, k);
    cout << result << endl;

    return 0;
}

在这里插入图片描述

标签:arr,cost,int,给定,型号,heap,position
From: https://www.cnblogs.com/moonfdd/p/17772846.html

相关文章

  • Secure Code Warrior C# Basic OWASP Web Top 10 2017 8: Insecure deserialization,
    Lastbutnotleast.Thesesetchallengesconsistof8:Insecuredeserialization,9:UsingComponentswithKnownVulnerabilities,10:InsufficientLoggingandMonitoring8:Insecuredeserialization, 9:UsingComponentswithKnownVulnerabilities, 10:I......
  • Codeforces Round 892 (Div. 2) B. Olya and Game with Arrays
    一系列\(n\)个数组,第\(i\)个数组的大小\(m_i\geq2\)。第\(i\)个数组为\(a_{m_1},a_{m_2},\cdots,a_{m_i}\)。对于每个数组,你可以移动最多一个元素到另一个数组。一系列\(n\)个数组的\(beauty\)定义为\(\sum_{i=1}^{n}min_{j=1}^{m_i}a_{i,j}\)。询问你......
  • Secure Code Warrior C# Basic OWASP Web Top 10 2017 5: Broken Access Control, 6:
    Learntheropesorhoneyourskillsinsecureprogramminghere.Thesechallengeswillgiveyouanunderstandingof5:BrokenAccessControl,6:SecurityMisconfigurationand7:XSSvulnerabilities5:BrokenAccessControl, 6:SecurityMisconfiguration ......
  • 解决Matlab遇到的svmtrain (line 234) Y must be a vector or a character array.
    解决Matlab遇到的svmtrain(line234)Ymustbeavectororacharacterarray.在使用MATLAB进行SVM分类器训练时,有时会出现以下错误提示:svmtrain(line234)Ymustbeavectororacharacterarray.这个错误是由于目标变量Y的类型不正确导致的。本文将介绍如何解决这个问题......
  • 给定字符串str= "asdfasdweraasdfasdf", 请python统计每个字符出现的次数,并将结果进行
    str="asdfasdweraasdfasdf"char_count={}forcharinstr:ifcharinchar_count:char_count[char]+=1else:char_count[char]=1forchar,countinchar_count.items():print(f"字符'{......
  • 数据结构与算法 | 数组(Array)
    数组(Array)数组(Array)应该是最基础的数据结构之一,它由相同类型的元素组成的集合,并按照一定的顺序存储在内存中。每个元素都有一个唯一的索引,可以用于访问该元素。 //java数组示例 int[]numbers1={2,0,2,3,9,23}; //或者 int[]numbers2=newint[6];基本概念数组基......
  • 561、Array Partition
    Givenanarrayof2nintegers,yourtaskistogrouptheseintegersintonpairsofinteger,say(a1,b1),(a2,b2),...,(an,bn)whichmakessumofmin(ai,bi)forallifrom1tonaslargeaspossible.Input:[1,4,3,2]Output:4Explanation:nis2,a......
  • Secure Code Warrior Introduction to OWASP Top 10 Awareness (with latest updates
    MissingFunctionAccessControlAccesstothesefunctionalitiesshouldberestrictedtoauthenticatedusers.However,thecurrentmechanismonlycheckswhetherauserexists.Anyuser,authenticatedornot,willbeabletoaccessrestrictedinformation.U......
  • 首发20A工艺!Intel Arrow Lake单核性能只提升5%
    Intel将在12月14日发布的MeteorLake酷睿Ultra处理器虽然升级Intel4工艺、分离式模块化架构的,但性能一般,只能用于主流和轻薄笔记本。明年,Intel将推出下一代ArrowLake,终于会有新一代桌面版,首发Intel20A制造工艺,接口更换为LGA1851,芯片组升级Z890、B860。据最新曝料,ArrowLake-......
  • hashmap,arrayList,concurrentHashMap扩容机制
    HashMap1.7和1.8扩容机制在Java1.7中,HashMap的扩容机制是当容量超过负载因子与数组长度的乘积时就会进行扩容。默认负载因子为0.75,即当数组长度为n时,当元素个数size超过n*0.75时就会扩容。扩容时,数组长度会变为原来的2倍,并且将原来的元素重新计算哈希值,再散列到新......