这是小川的第383次更新,第412篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第245题(顺位题号是1029)。公司计划采访的人数为2N
。将第i
个人飞往城市A的费用是[i][0]
,将第i
个人飞到城市B的费用是费用[i][1]
。
返回将每个人带到一个城市的最低费用,这样每个城市就会有N
个人到达。
例如:
输入:[[10,20],[30,200],[400,50],[30,20]] 输出:110 说明: 第一个人去城市A,费用为10。 第二个人去城市A,费用为30。 第三个人去B市,费用为50。 第四个人去B市,费用为20。 总体最低费用为10 + 30 + 50 + 20 = 110,每个城市有一半的人在采访。
注意:
1 <= costs.length <= 100
保证cost.length是偶数。
1 <=
cost[i][0]
,cost[i][1]
<= 1000
02 第一种解法
我们可以通过计算去A市、B市之间花费的差值cost[i][0]-cost[i][1]
,来判断哪一部分人去A市,哪一部分人去B市,差值最小的人去A市,因为差值越小,去A市是越省钱的。只要把去A市的人确定了,剩下的都去B市就行。
结合题目的示例来看,原数组是[[10,20],[30,200],[400,50],[30,20]]
,计算去A市、B市之间花费的差值,数组变成了[-10,-170,350,10]
,将差值数组排序后,得到[-170,-10,10,350]
,前面的两个差值去A市,后面的两个差值去B市。其中差值最小的一组是[30,200]
,它们的差值是-170,去A市比去B市少花170,所以去A市更加省钱。
思路:借助Arrays
的sort
方法,重写compare
方法,遍历按照差值排序后的数组,前一半元素取A市,后一半元素去B市,返回累加的最小花费。
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return (a[0] - a[1]) - (b[0] - b[1]);
}
});
int sum = 0;
for (int i = 0; i < costs.length; ++i) {
if (i < costs.length / 2) {
sum += costs[i][0];
} else {
sum += costs[i][1];
}
}
return sum;
}
03 第二种解法
利用动态规划来解,此方法来自讨论区,传送门:https://leetcode.com/problems/two-city-scheduling/discuss/278731/Java-DP-Easy-to-Understand
public int twoCitySchedCost2(int[][] costs) {
int N = costs.length/2;
int[][] dp = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
dp[i][0] = dp[i-1][0] + costs[i-1][0];
}
for (int j = 1; j <= N; j++) {
dp[0][j] = dp[0][j-1] + costs[j-1][1];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
dp[i][j] = Math.min(dp[i-1][j] + costs[i+j-1][0],
dp[i][j-1] + costs[i+j-1][1]);
}
}
return dp[N][N];
}
04 小结
算法专题目前已连续日更超过七个月,算法题文章251+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!