2023-10-18：用go语言，给定一个数组arr，长度为n，表示有0~n-1

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 是设备数量。需要额外的空间来存储、、和堆，它们的空间复杂度都为 O(n)。

own

nexts

visited

heap

go完整代码如下：

packagemain
import(
"fmt"
"github.com/emirpasic/gods/trees/binaryheap"
)
funcminCost(arr[]int,m[][]int,nint,kint)int{
//0:{4,7,13,26}
//1:{5,45,3,17}
own:=make([][]int,k)
nexts:=make([][]int,k)
fori:=0;iown[i]=[]int{}
nexts[i]=[]int{}
}
fori:=0;iown[arr[i]]=append(own[arr[i]],i)
}
fori:=0;iforj:=0;jifm[i][j]==1{
nexts[i]=append(nexts[i],j)
}
}
}
heap:=binaryheap.NewWith(func(a,binterface{})int{
returna.([]int)[1]-b.([]int)[1]
})
heap.Push([]int{0,0})
visited:=make([]bool,n)
forheap.Size()>0{
t,_:=heap.Pop()
cur:=t.([]int)
position:=cur[0]
cost:=cur[1]
if!visited[position]{
visited[position]=true
ifposition==n-1{
returncost
}
model:=arr[position]
for_,nextModel:=rangenexts[model]{
for_,nextPosition:=rangeown[nextModel]{
if!visited[nextPosition]{
heap.Push([]int{nextPosition,cost+abs(nextPosition,position)})
}
}
}
}
}
return-1
}
funcabs(a,bint)int{
ifa-b<0{
returnb-a
}
returna-b
}
funcmain(){
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完整代码如下：

usestd::cmp::Reverse;
usestd::collections::BinaryHeap;
fnmin_cost(arr:&[i32],map:&[Vec],n:usize,k:usize)->i32{
letmutown:Vec>=vec![Vec::new();k];
letmutnexts:Vec>=vec![Vec::new();k];
for(i,&value)inarr.iter().enumerate(){
own[valueasusize].push(iasi32);
}
for(i,row)inmap.iter().enumerate(){
for(j,&value)inrow.iter().enumerate(){
ifvalue==1{
nexts[iasusize].push(jasi32);
}
}
}
letmutheap:BinaryHeap<(i32,i32)>=BinaryHeap::new();
heap.push((0,0));
letmutvisited:Vec=vec![false;n];
whileletSome((position,cost))=heap.pop(){
letposition=positionasusize;
letcost=cost;
if!visited[position]{
visited[position]=true;
ifposition==n-1{
returncost;
}
letmodel=arr[position]asusize;
for&next_modelin&nexts[model]{
for&next_positionin&own[next_modelasusize]{
if!visited[next_positionasusize]{
heap.push((
next_position,
cost+(next_position-positionasi32).abs(),
));
}
}
}
}
}
-1
}
fnmain(){
letarr=[0,1,2,3];
letm=[
vec![0,1,0,1,0],
vec![1,0,1,1,0],
vec![2,1,1,1,1],
vec![3,0,0,0,0],
];
letn=4;
letk=4;
letresult=min_cost(&arr,&m,n,k);
println!("MinimumCost:{}",result);
}

c++完整代码如下：

#include
#include
#include
#include
usingnamespacestd;
intminCost(vector&arr,vector>&map,intn,intk){
vector>own(k);
vector>nexts(k);
for(inti=0;iown[arr[i]].push_back(i);
}
for(inti=0;ifor(intj=0;jif(map[i][j]==1){
nexts[i].push_back(j);
}
}
}
priority_queue,vector>,greater>>heap;
heap.push({0,0});
vectorvisited(n,false);
while(!heap.empty()){
vectorcur=heap.top();
heap.pop();
intposition=cur[0];
intcost=cur[1];
if(!visited[position]){
visited[position]=true;
if(position==n-1){
returncost;
}
intmodel=arr[position];
for(intnextModel:nexts[model]){
for(intnextPosition:own[nextModel]){
if(!visited[nextPosition]){
heap.push({nextPosition,cost+abs(nextPosition-position)});
}
}
}
}
}
return-1;
}
intmain(){
vectorarr={0,1,2,3};
vector>m={{0,1,0,1,0},{1,0,1,1,0},{2,1,1,1,1},{3,0,0,0,0}};
intn=4;
intk=4;
intresult=minCost(arr,m,n,k);
cout<
return0;
}