LeetCode.1029

Stella981
• 阅读 567

这是小川的第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市更加省钱。

思路:借助Arrayssort方法,重写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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
LeetCode算法题
这是悦乐书的第258次更新,第271篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第125题(顺位题号是551)。您将获得一个表示学生出勤记录的字符串。该记录仅包含以下三个字符:'A':缺席。'L':迟到。'P':在场。如果学生的出勤记录不超过一个“A”(缺席)或超过两个
Stella981 Stella981
3年前
LeetCode第27题
Givenanarray_nums_andavalue_val_,removeallinstancesofthatvalueinplaceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisb
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Stella981 Stella981
3年前
LeetCode.1128
这是小川的第394次更新,第428篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第259题(顺位题号是1128)。给定多米诺骨牌列表,当且仅当(ac且bd)或(ad且bc),dominoesia,
Stella981 Stella981
3年前
Redis 6.0 正式版终于发布了!除了多线程还有什么新功能?
!(https://oscimg.oschina.net/oscnet/b8c8b22b9f44bd806c26b486e1893a263a4.jpg)这是我的第56篇原创文章!(https://oscimg.oschina.net/oscnet/8bf00bc92f6a1cd46596ee44bac64a801ae.pn
Wesley13 Wesley13
3年前
Mysql 查询所有课程的成绩第2名到第3名的学生信息及该课程成绩
 查询所有课程的成绩第2名到第3名的学生信息及该课程成绩1\.查询课程ID为‘01’的课程的成绩第2名到第3名的学生信息及该课程成绩SELECT  d.,c.排名,c.s_score,c.c_idFROM  (SELECTa.s_id,a.s_score,a.c_id,@i:@i1AS排名FROMs
Stella981 Stella981
3年前
LeetCode.1170
这是小川的第412次更新,第444篇原创<br/看题和准备今天介绍的是LeetCode算法题中Easy级别的第263题(顺位题号是1170)。在一个非空字符串s上定义一个函数f(s),该函数计算s中最小字符的出现频率。例如,如果s"dcce",则f(s)2,因为最