小李飛刀：做題第十二彈！

yagami 發(fā)布于2019-07-31 10:19 / 2844人閱讀

摘要：寫在前面今天沒有叨逼叨但是又一次錯過了競賽愛睡覺的小李下周要上班，下下周一定要參加了握拳認(rèn)真做題的分割線第一題兩地調(diào)度公司計劃面試人。第人飛往市的費用為，飛往市的費用為。示例輸入輸出解釋第一個人去市，費用為。

寫在前面

今天沒有叨逼叨...但是又一次錯過了競賽...
愛睡覺的小李...下周要上班，下下周一定要參加了（握拳

認(rèn)真做題的分割線

第一題

1029. 兩地調(diào)度
公司計劃面試2N人。第i人飛往 A 市的費用為 costsi，飛往 B 市的費用為 costsi。
返回將每個人都飛到某座城市的最低費用，要求每個城市都有N人抵達(dá)。

示例：

輸入：[[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
costs.length 為偶數(shù)
1 <= costsi, costsi <= 1000

我的題解：

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        costs = sorted(costs,key = lambda x:abs(x[0] - x[1]))
        costs = costs[::-1]
        a,b = 0,0
        n = len(costs) //2
        res = 0
        for i in costs:
            if a < n and b < n:
                if i[0] < i[1]:
                    a += 1
                    res += i[0]
                else:
                    b += 1
                    res += i[1]
            elif a
我的思路：
參考了小江同學(xué)的思路（她的blog還在小黑屋...后續(xù)補上鏈接）和這位同學(xué)的思路。

先判斷每個人去往兩地的成本差，成本差越大的同學(xué)要越早被安排的明明白白
然后分配人員，先分配滿n個人的組不再加人，其他的都去另一個組

GPU云服務(wù)器云服務(wù)器第十二篇飛刀小李做題

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43619.html

相關(guān)文章

小李飛刀：做題第十彈！

摘要：第二題漢明距離難度簡單兩個整數(shù)之間的漢明距離指的是這兩個數(shù)字對應(yīng)二進(jìn)制位不同的位置的數(shù)目。給出兩個整數(shù)和，計算它們之間的漢明距離。第三題買賣股票的最佳時機(jī)難度簡單給定一個數(shù)組，它的第個元素是一支給定股票第天的價格。寫在前面這幾天斷斷續(xù)續(xù)做了題目，也在慢慢體會一些數(shù)據(jù)思維。終于不用邊做視頻邊寫題目啦~開心~把這幾天的題解發(fā)一下~ 認(rèn)真做題的分割線第一題 977. 有序數(shù)組的平方難度...

bingo 2019-07-31 10:13 評論0 收藏0
小李飛刀：做題第十一彈！

摘要：第五題對稱二叉樹難度簡單給定一個二叉樹，檢查它是否是鏡像對稱的。第十六題最大連續(xù)的個數(shù)難度簡單給定一個二進(jìn)制數(shù)組，計算其中最大連續(xù)的個數(shù)。第十八題平方數(shù)之和難度簡單給定一個非負(fù)整數(shù)，你要判斷是否存在兩個整數(shù)和，使得。寫在前面最近忙著調(diào)教新裝備，沒有及時的寫題解，但是沒有在偷懶沒刷題喔~來認(rèn)真整理下最近做的題目~ 之前考慮按tag來刷題，后來收到了推薦的leetcode題解，就根據(jù)上...

ytwman 2019-07-31 10:18 評論0 收藏0
小李飛刀：刷題第十三彈！

摘要：寫在前面今天的小李的目標(biāo)是排序算法，果然還是要下手寫才會更有體會，也更記得住。排序算法冒泡排序主要是比對相鄰兩個數(shù)之間的大小關(guān)系，不斷將較大值交換至最后。寫在前面今天的小李的目標(biāo)是排序算法，果然還是要下手寫才會更有體會，也更記得住。認(rèn)真做題的分割線第一題 215. 數(shù)組中的第K個最大元素難度：中等在未排序的數(shù)組中找到第k個最大的元素。請注意，你需要找的是數(shù)組排序后的第k個最大的...

lixiang 2019-07-31 10:20 評論0 收藏0
小李飛刀：做題第六彈！

摘要：給定的字符串只含有小寫英文字母，并且長度不超過。其他這題了，要重做看了其他的人的題解，使用的是無限逼近中位值的辦法，理論基礎(chǔ)應(yīng)該是泰勒公式。萬萬沒想到居然用到了泰勒公式手工執(zhí)行了下算法，反而理解的更快，但是泰勒公式還得再復(fù)習(xí)下。寫在前面的話今天持續(xù)做題ing，python有意思~今天的題有點虐心...興許是我太笨了...會努力學(xué)習(xí)的！動態(tài)規(guī)劃我來啦~ 開始做題第一題 459. 重...

BigNerdCoding 2019-07-31 10:08 評論0 收藏0
小李飛刀：做題第八彈！

摘要：認(rèn)真做題的分割線第一題乘積最大子序列難度中等給定一個整數(shù)數(shù)組，找出一個序列中乘積最大的連續(xù)子序列該序列至少包含一個數(shù)。寫在前面的話慢慢轉(zhuǎn)變思路，不再死磕不會做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺對一些題目的思路有比較大的幫助，但是還是要在實踐中理解。認(rèn)真做題的分割線第一題 152. 乘積最大子序列難度：中等給定一個整數(shù)數(shù)組nums，找出一個...

ztyzz 2019-07-31 10:11 評論0 收藏0