2023-05-06：X軸上有一些機器人和工廠。給你一個整數(shù)數(shù)組robot，其中robot[i]是第i個機器人的位置

再給你一個二維整數(shù)數(shù)組factory，其中 factory[j] = [positionj, limitj]

表示第 j 個工廠的位置在 positionj ，且第 j 個工廠最多可以修理 limitj 個機器人

每個機器人所在的位置 互不相同。每個工廠所在的位置也互不相同

注意一個機器人可能一開始跟一個工廠在相同的位置

所有機器人一開始都是壞的，他們會沿著設(shè)定的方向一直移動

設(shè)定的方向要么是 X 軸的正方向，要么是 X 軸的負方向

當一個機器人經(jīng)過一個沒達到上限的工廠時，這個工廠會維修這個機器人，且機器人停止移動

任何時刻，你都可以設(shè)置 部分 機器人的移動方向

你的目標是最小化所有機器人總的移動距離

請你返回所有機器人移動的最小總距離

注意：

所有機器人移動速度相同

如果兩個機器人移動方向相同，它們永遠不會碰撞

如果兩個機器人迎面相遇，它們也不會碰撞，它們彼此之間會擦肩而過

如果一個機器人經(jīng)過了一個已經(jīng)達到上限的工廠，機器人會當作工廠不存在，繼續(xù)移動

機器人從位置 x 到位置 y 的移動距離為 |y - x|

1 <= robot.length, factory.length <= 100

factory[j].length == 2

-10 ^ 9 <= robot[i], positionj <= 10 ^ 9

0 <= limitj <= robot.length

測試數(shù)據(jù)保證所有機器人都可以被維修。

輸入：robot = [0,4,6], factory = [[2,2],[6,2]]。

輸出：4。

答案2023-05-06：

算法1：

1.首先對機器人位置數(shù)組?robot?進行排序，按照從小到大的順序排列。

2.對工廠位置數(shù)組?factory?按照第一個元素排序，也就是按照工廠所在的位置從小到大排列。

3.創(chuàng)建一個二維數(shù)組?dp，大小為?(n, m)，其中 $n$ 是機器人個數(shù)，$m$ 是工廠個數(shù)。初始時，所有元素置為 -1。

4.調(diào)用遞歸函數(shù)?process1(robot, factory, n-1, m-1, dp)?計算最小總距離。

--1.如果機器人已經(jīng)全部處理完畢（即?i < 0），返回 0。

--2.如果已經(jīng)沒有可用的工廠（即?j < 0），返回最大整數(shù)值（表示當前狀態(tài)不合法，無解）。

--3.如果?dp[i][j]?已經(jīng)計算過了，直接返回這個值。

--4 定義變量?ans?表示當前狀態(tài)下的最小距離，初始化為左邊一個工廠的最小距離。然后遍歷當前工廠能夠維修的機器人，計算這些機器人到當前工廠的距離，并且調(diào)用遞歸函數(shù)?process1?計算剩余機器人和工廠的最小距離。

--5.在所有可能的狀態(tài)中選擇一個距離最小的狀態(tài)，并返回這個距離。

5.返回遞歸函數(shù)?process1?的計算結(jié)果。

時間復雜度：O((n ^ m)m)，其中 n 是機器人個數(shù)，m 是工廠個數(shù)。

空間復雜度：O(nm)。

算法2：

1.首先對機器人位置數(shù)組?robot?進行排序，按照從小到大的順序排列。

2.對工廠位置數(shù)組?factory?按照第一個元素排序，也就是按照工廠所在的位置從小到大排列。

3.創(chuàng)建一個二維數(shù)組?dp，大小為?(n, m)，其中 $n$ 是機器人個數(shù)，$m$ 是工廠個數(shù)。初始時，所有元素置為最大整數(shù)值。

4.遍歷機器人和工廠，使用動態(tài)規(guī)劃計算最小總距離。

--1.定義變量?ans?表示當前狀態(tài)下的最小距離，初始化為左邊一個工廠的最小距離。

--2.定義變量?distance?表示當前機器人到當前工廠的距離，初始化為 0。

--3.遍歷當前工廠能夠維修的機器人，計算這些機器人到當前工廠的距離，并且查找剩余機器人和工廠的最小距離。

--4.更新變量?ans?和?distance。

--5.在所有可能的狀態(tài)中選擇一個距離最小的狀態(tài)，并將這個距離賦值給當前狀態(tài)。

5.返回?dp[n-1][m-1]，即機器人全部處理完畢時到達最后一個工廠所需要的最小總距離。

算法2時間復雜度：O(n(m ^ 2))，其中 n 是機器人個數(shù)，m 是工廠個數(shù)。

空間復雜度：O(nm)。

算法3：

1.首先對機器人位置數(shù)組?robot?進行排序，按照從小到大的順序排列。

2.對工廠位置數(shù)組?factory?按照第一個元素排序，也就是按照工廠所在的位置從小到大排列。

3.創(chuàng)建一個二維數(shù)組?dp，大小為?(n, m)，其中 $n$ 是機器人個數(shù)，$m$ 是工廠個數(shù)。初始時，所有元素置為最大整數(shù)值。

4.創(chuàng)建一個雙端隊列?deque，用于維護每個工廠能夠維修的機器人的最小距離。

5.遍歷工廠，對于每個工廠，使用動態(tài)規(guī)劃計算最小總距離。

--1.定義變量?add?表示當前機器人到當前工廠之前的距離和，初始化為 0。

--2.定義變量?limit?表示當前工廠能夠維修的機器人數(shù)量限制。

--3.初始化雙端隊列?deque，將?(i, 0)?加入隊列。其中 $i$ 表示機器人的下標，0 表示到達當前工廠之前的距離和為 0。

--4.遍歷機器人，計算當前狀態(tài)下的最小距離。

----1.如果左邊有一個工廠，選擇它作為當前狀態(tài)的備選值。

----2.從隊列中取出所有與當前機器人距離小于等于?limit?的機器人，并計算這些機器人到當前工廠的距離和。如果隊列為空，則跳過該步驟。

----3.在所有可能的狀態(tài)中選擇一個距離最小的狀態(tài)，并將這個距離賦值給當前狀態(tài)。

----4.將當前機器人加入隊列，更新隊列中的元素。

--5.返回?dp[n-1][m-1]，即機器人全部處理完畢時到達最后一個工廠所需要的最小總距離。

6.返回?dp[n-1][m-1]，即機器人全部處理完畢時到達最后一個工廠所需要的最小總距離。

時間復雜度：O(nm log n)，其中 n 是機器人個數(shù)，m 是工廠個數(shù)。

空間復雜度：O(nm)。

go三種算法完整代碼如下：

package?main

import?(
????"fmt"
????"math"
????"sort"
)

func?minimumTotalDistance1(robot?[]int,?factory?[][]int)?int64?{
????n?:=?len(robot)
????m?:=?len(factory)
????sort.Ints(robot)
????sortFactoryByFirst(factory)
????dp?:=?make([][]int64,?n)
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int64,?m)
????????for?j?:=?range?dp[i]?{
????????????dp[i][j]?=?-1
????????}
????}
????return?process1(robot,?factory,?n-1,?m-1,?dp)
}

func?process1(robot?[]int,?factory?[][]int,?i,?j?int,?dp?[][]int64)?int64?{
????if?i?<?0?{
????????return?0
????}
????if?j?<?0?{
????????return?math.MaxInt64
????}
????if?dp[i][j]?!=?-1?{
????????return?dp[i][j]
????}
????ans?:=?process1(robot,?factory,?i,?j-1,?dp)
????distance?:=?int64(0)
????for?l,?num?:=?i,?1;?l?>=?0?&&?num?<=?factory[j][1];?l,?num?=?l-1,?num+1?{
????????curAns?:=?process1(robot,?factory,?l-1,?j-1,?dp)
????????d?:=?int64(abs(robot[l]?-?factory[j][0]))
????????distance?+=?d
????????if?curAns?!=?math.MaxInt64?{
????????????ans?=?min(ans,?curAns+distance)
????????}
????}
????dp[i][j]?=?ans
????return?ans
}

func?sortFactoryByFirst(a?[][]int)?{
????sort.Slice(a,?func(i,?j?int)?bool?{
????????return?a[i][0]?<?a[j][0]
????})
}

func?abs(x?int)?int?{
????if?x?<?0?{
????????return?-x
????}
????return?x
}

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

func?minimumTotalDistance2(robot?[]int,?factory?[][]int)?int64?{
????n?:=?len(robot)
????m?:=?len(factory)
????sort.Ints(robot)
????sortFactoryByFirst(factory)
????dp?:=?make([][]int64,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????dp[i]?=?make([]int64,?m)
????????for?j?:=?0;?j?<?m;?j++?{
????????????ans?:=?int64(math.MaxInt64)
????????????if?j?>?0?{
????????????????ans?=?dp[i][j-1]
????????????}
????????????distance?:=?int64(0)
????????????for?l,?num?:=?i,?1;?l?>=?0?&&?num?<=?factory[j][1];?l,?num?=?l-1,?num+1?{
????????????????curAns?:=?int64(0)
????????????????if?l-1?<?0?{
????????????????????curAns?=?0
????????????????}?else?if?j-1?<?0?{
????????????????????curAns?=?math.MaxInt64
????????????????}?else?{
????????????????????curAns?=?dp[l-1][j-1]
????????????????}
????????????????distance?+=?int64(abs(robot[l]?-?factory[j][0]))
????????????????if?curAns?!=?math.MaxInt64?{
????????????????????ans?=?min(ans,?curAns+distance)
????????????????}
????????????}
????????????dp[i][j]?=?ans
????????}
????}
????return?dp[n-1][m-1]
}

func?minimumTotalDistance3(robot?[]int,?factory?[][]int)?int64?{
????n?:=?len(robot)
????m?:=?len(factory)
????sort.Ints(robot)
????sortFactoryByFirst(factory)
????dp?:=?make([][]int64,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????dp[i]?=?make([]int64,?m)
????????for?j?:=?0;?j?<?m;?j++?{
????????????dp[i][j]?=?math.MaxInt64
????????}
????}
????deque?:=?make([][]int64,?n+1)
????for?i?:=?0;?i?<?n+1;?i++?{
????????deque[i]?=?make([]int64,?2)
????}
????var?l,?r?int
????for?j?:=?0;?j?<?m;?j++?{
????????add?:=?int64(0)
????????limit?:=?int64(factory[j][1])
????????l?=?0
????????r?=?1
????????deque[l][0]?=?-1
????????deque[l][1]?=?0
????????for?i?:=?0;?i?<?n;?i++?{
????????????p1?:=?int64(math.MaxInt64)
????????????if?j?>?0?{
????????????????p1?=?dp[i][j-1]
????????????}
????????????add?+=?int64(abs(robot[i]?-?factory[j][0]))
????????????if?deque[l][0]?==?int64(i)-limit-1?{
????????????????l++
????????????}
????????????p2?:=?int64(math.MaxInt64)
????????????if?l?<?r?{
????????????????best?:=?deque[l][1]
????????????????if?best?!=?math.MaxInt64?{
????????????????????p2?=?add?+?best
????????????????}
????????????}
????????????dp[i][j]?=?min(p1,?p2)
????????????fill?:=?p1
????????????if?p1?==?math.MaxInt64?{
????????????????fill?=?p1
????????????}?else?{
????????????????fill?=?p1?-?add
????????????}
????????????for?l?<?r?&&?deque[r-1][1]?>=?fill?{
????????????????r--
????????????}
????????????deque[r][0]?=?int64(i)
????????????deque[r][1]?=?fill
????????????r++
????????}
????}
????return?dp[n-1][m-1]
}

func?main()?{
????if?true?{
????????robot?:=?[]int{0,?4,?6}
????????factory?:=?[][]int{{2,?2},?{6,?2}}
????????fmt.Println(minimumTotalDistance1(robot,?factory))
????}
????if?true?{
????????robot?:=?[]int{0,?4,?6}
????????factory?:=?[][]int{{2,?2},?{6,?2}}
????????fmt.Println(minimumTotalDistance2(robot,?factory))
????}

????if?true?{
????????robot?:=?[]int{0,?4,?6}
????????factory?:=?[][]int{{2,?2},?{6,?2}}
????????fmt.Println(minimumTotalDistance3(robot,?factory))
????}
}

rust第2種和第3種算法代碼如下：

fn?minimum_total_distance2(robot:?Vec<i32>,?factory:?Vec<Vec<i32>>)?->?i64?{
????let?n?=?robot.len();
????let?m?=?factory.len();

????//?排序操作
????let?mut?sorted_robot?=?robot.clone();
????sorted_robot.sort_unstable();

????let?mut?sorted_factory?=?factory.clone();
????sorted_factory.sort_unstable_by_key(|a|?a[0]);

????let?mut?dp?=?vec![vec![std::i64::MAX;?m];?n];

????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????//?ans?=?dp[i][j?-?1]?->?0...i?->?0...j-1
????????????let?mut?ans?=?std::i64::MAX;
????????????if?j?>=?1?{
????????????????ans?=?dp[i][j?-?1];
????????????}
????????????let?mut?distance?=?0;
????????????for?(l,?num)?in?(0..=i).rev().zip(1..=factory[j][1])?{
????????????????let?cur_ans?=?if?l?==?0?{
????????????????????0
????????????????}?else?if?j?==?0?{
????????????????????std::i64::MAX
????????????????}?else?{
????????????????????dp[l?-?1][j?-?1]
????????????????};
????????????????let?d?=?(robot[l]?-?factory[j][0]).abs()?as?i64;
????????????????distance?+=?d;
????????????????if?cur_ans?!=?std::i64::MAX?{
????????????????????ans?=?ans.min(cur_ans?+?distance);
????????????????}
????????????}
????????????dp[i][j]?=?ans;
????????}
????}

????dp[n?-?1][m?-?1]
}

fn?minimum_total_distance3(robot:?Vec<i32>,?factory:?Vec<Vec<i32>>)?->?i64?{
????let?n?=?robot.len();
????let?m?=?factory.len();

????//?排序操作
????let?mut?sorted_robot?=?robot.clone();
????sorted_robot.sort_unstable();

????let?mut?sorted_factory?=?factory.clone();
????sorted_factory.sort_unstable_by_key(|a|?a[0]);

????let?mut?dp?=?vec![vec![std::i64::MAX;?m];?n];

????for?j?in?0..m?{
????????let?mut?add?=?0;
????????let?limit?=?factory[j][1]?as?usize;
????????let?mut?l?=?0;
????????let?mut?r?=?1;
????????let?mut?deque?=?vec![vec![0;?2];?n?+?1];
????????deque[l][0]?=?std::i64::MAX;
????????deque[l][1]?=?0;
????????for?i?in?0..n?{
????????????let?p1?=?if?j?>=?1?{?dp[i][j?-?1]?}?else?{?std::i64::MAX?};
????????????add?+=?(sorted_robot[i]?-?sorted_factory[j][0]).abs()?as?i64;
????????????while?l?<?r?&&?deque[l][0]?==?i?as?i64?-?limit?as?i64?-?1?{
????????????????l?+=?1;
????????????}
????????????let?p2?=?if?l?<?r?&&?deque[l][1]?!=?std::i64::MAX?{
????????????????add?+?deque[l][1]
????????????}?else?{
????????????????std::i64::MAX
????????????};
????????????dp[i][j]?=?p1.min(p2);
????????????let?fill?=?if?p1?==?std::i64::MAX?{?p1?}?else?{?p1?-?add?};
????????????while?l?<?r?&&?deque[r?-?1][1]?>=?fill?{
????????????????r?-=?1;
????????????}
????????????deque[r][0]?=?i?as?i64;
????????????deque[r][1]?=?fill;
????????????r?+=?1;
????????}
????}

????dp[n?-?1][m?-?1]
}

fn?main()?{
????let?robot?=?vec![0,?4,?6];
????let?factory?=?vec![vec![2,?2],?vec![6,?2]];
????println!(
????????"{}",
????????minimum_total_distance2(robot.clone(),?factory.clone())
????);
????println!(
????????"{}",
????????minimum_total_distance3(robot.clone(),?factory.clone())
????);
}


c++三種算法完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<algorithm>
#include?<climits>

using?namespace?std;

struct?Pair?{
????int?x,?y;
};

void?sortFactoryByFirst(vector<vector<int>>&?factory)?{
????sort(factory.begin(),?factory.end(),?[](const?auto&?a,?const?auto&?b)?{
????????return?a[0]?<?b[0];
????????});
}

int64_t?minimumTotalDistance1(vector<int>&?robot,?vector<vector<int>>&?factory,?int?n,?int?m,?vector<vector<int64_t>>&?dp)?{
????if?(n?<?0)?{
????????return?0;
????}
????if?(m?<?0)?{
????????return?INT64_MAX;
????}
????if?(dp[n][m]?!=?-1)?{
????????return?dp[n][m];
????}
????int64_t?ans?=?minimumTotalDistance1(robot,?factory,?n,?m?-?1,?dp);
????int64_t?distance?=?0;
????for?(int?l?=?n,?num?=?1;?l?>=?0?&&?num?<=?factory[m][1];?l--,?num++)?{
????????int64_t?curAns?=?minimumTotalDistance1(robot,?factory,?l?-?1,?m?-?1,?dp);
????????int64_t?d?=?abs(robot[l]?-?factory[m][0]);
????????distance?+=?d;
????????if?(curAns?!=?INT64_MAX)?{
????????????ans?=?min(ans,?curAns?+?distance);
????????}
????}
????dp[n][m]?=?ans;
????return?ans;
}

int64_t?minimumTotalDistance2(vector<int>&?robot,?vector<vector<int>>&?factory,?int?n,?int?m)?{
????sort(robot.begin(),?robot.end());
????sortFactoryByFirst(factory);
????vector<vector<int64_t>>?dp(n,?vector<int64_t>(m));
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????int64_t?ans?=?INT64_MAX;
????????????if?(j?>?0)?{
????????????????ans?=?dp[i][j?-?1];
????????????}
????????????int64_t?distance?=?0;
????????????for?(int?l?=?i,?num?=?1;?l?>=?0?&&?num?<=?factory[j][1];?l--,?num++)?{
????????????????int64_t?curAns?=?0;
????????????????if?(l?-?1?<?0)?{
????????????????????curAns?=?0;
????????????????}
????????????????else?if?(j?-?1?<?0)?{
????????????????????curAns?=?INT64_MAX;
????????????????}
????????????????else?{
????????????????????curAns?=?dp[l?-?1][j?-?1];
????????????????}
????????????????distance?+=?abs(robot[l]?-?factory[j][0]);
????????????????if?(curAns?!=?INT64_MAX)?{
????????????????????ans?=?min(ans,?curAns?+?distance);
????????????????}
????????????}
????????????dp[i][j]?=?ans;
????????}
????}
????return?dp[n?-?1][m?-?1];
}

int64_t?minimumTotalDistance3(vector<int>&?robot,?vector<vector<int>>&?factory,?int?n,?int?m)?{
????sort(robot.begin(),?robot.end());
????sortFactoryByFirst(factory);
????vector<vector<int64_t>>?dp(n,?vector<int64_t>(m,?INT64_MAX));
????vector<Pair>?deque(n?+?1);
????int?l?=?0,?r?=?1;
????deque[0].x?=?-1;
????deque[0].y?=?0;
????for?(int?j?=?0;?j?<?m;?j++)?{
????????int64_t?add?=?0;
????????int64_t?limit?=?(int64_t)factory[j][1];
????????l?=?0;
????????r?=?1;
????????deque[l].x?=?-1;
????????deque[l].y?=?0;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????int64_t?p1?=?INT64_MAX;
????????????if?(j?>?0)?{
????????????????p1?=?dp[i][j?-?1];
????????????}
????????????add?+=?abs(robot[i]?-?factory[j][0]);
????????????while?(l?<?r?&&?deque[l].x?==?(int64_t)i?-?limit?-?1)?{
????????????????l++;
????????????}
????????????int64_t?p2?=?INT64_MAX;
????????????if?(l?<?r)?{
????????????????int64_t?best?=?deque[l].y;
????????????????if?(best?!=?INT64_MAX)?{
????????????????????p2?=?add?+?best;
????????????????}
????????????}
????????????dp[i][j]?=?min(p1,?p2);
????????????int64_t?fill?=?p1;
????????????if?(p1?==?INT64_MAX)?{
????????????????fill?=?p1;
????????????}
????????????else?{
????????????????fill?=?p1?-?add;
????????????}
????????????while?(l?<?r?&&?deque[r?-?1].y?>=?fill)?{
????????????????r--;
????????????}
????????????deque[r].x?=?i;
????????????deque[r].y?=?fill;
????????????r++;
????????}
????}
????return?dp[n?-?1][m?-?1];
}

int?main()?{
????if?(true)?{
????????vector<int>?robot{?0,?4,?6?};
????????vector<vector<int>>?factory{?{2,?2},?{6,?2}?};
????????int?n?=?robot.size();
????????int?m?=?factory.size();
????????vector<vector<int64_t>>?dp(n,?vector<int64_t>(m,?-1));
????????printf("%lld\n",?minimumTotalDistance1(robot,?factory,?n?-?1,?m?-?1,?dp));
????}
????if?(true)?{
????????vector<int>?robot{?0,?4,?6?};
????????vector<vector<int>>?factory{?{2,?2},?{6,?2}?};
????????int?n?=?robot.size();
????????int?m?=?factory.size();
????????printf("%lld\n",?minimumTotalDistance2(robot,?factory,?n,?m));
????}
????if?(true)?{
????????vector<int>?robot{?0,?4,?6?};
????????vector<vector<int>>?factory{?{2,?2},?{6,?2}?};
????????int?n?=?robot.size();
????????int?m?=?factory.size();
????????printf("%lld\n",?minimumTotalDistance3(robot,?factory,?n,?m));
????}
????return?0;
}


c語言的不好寫，故沒有代碼。

福大大架構(gòu)師每日一題

java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。

495篇原創(chuàng)內(nèi)容

公眾號