閑聊

不知不覺，從開始發算法博客到如今已經過了半月，在這個過程中其實也遇到過很多困難，也一度想過要放棄，深刻體會到沒有任何一件事情是可以簡簡單單敷衍過去的，特別能體會那些工作之余還能十年如一日堅持技術文章創作的作者們的不容易。不過盡管辛苦也有很多收獲，比如精益求精，更追求更完美，又比如收獲了很多技術以外的知識，認識了更多的朋友，視野也更加開闊。猶記得第一次投稿成功，第一次文章被大的專欄收錄，第一次有人點贊，第一次有粉絲關注，甚至第一次某平臺粉絲破百的時候內心的喜悅...

未來，希望自己能把算法博客當成愛好一直寫下去，也希望能這些文章能給有需要的朋友帶來實際的幫助。在后續博文推送過程中，不排除也有些疏漏或者思維理解上的誤區，歡迎交流或批評指正。

概要

上一篇博客《LeetCode進階944-貪心》，有朋友提出建議944對理解貪心算法并不具有很強的代表性。回顧了下上篇的內容，實際文中博主重點說明的是算法優化的小技巧，題解思路也僅僅只是簡單的統計法，對貪心思想實際幫助確實不大。基于此博主已將上篇博客標題更正為《LeetCode進階944-算法優化》(除訂閱號由于微信公眾平臺的限制，標題暫時無法修改)，而本篇將以leetcode1029為實例，講解貪心算法思想。

原題

1029. Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]

Output: 110

Explanation:

The first person goes to city A for a cost of 10.

The second person goes to city A for a cost of 30.

The third person goes to city B for a cost of 50.

The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:

1 <= costs.length <= 100

It is guaranteed that costs.length is even.

1 <= costs[i][0], costs[i][1] <= 1000

1029. 面試安排(據題意命名)

公司安排2N個人參加面試。第i個人坐飛機飛到城市A的費用為costs[i][0]，飛到城市B的費用為 costs[i][1]。

返回安排好每個人都前往某城市面試的最低費用，A、B城市各有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

costs.length 為偶數

1 <= costs[i][0], costs[i][1] <= 1000

• 本題在LeetCode上屬于貪心算法分類下

題意分析

需要將2N個人分成兩組，分別送往A、B城市面試，每個人去A、B城市的費用已知，要保證總費用最少。凡事涉及最大最小值求和相關的題型，自然不難聯想到貪心算法思想，貪心思想最典型的問題是“背包問題”，關于貪心思想需要注意的是，一定要確保“貪心”的思路正確即能拿到最優解，實踐過程中可以具體進行數值帶入驗證。

思路設計

根據題意，需要的最優解是花費最少的錢分別安排N個人前往A、B面試，每個人前往A、B城市的花費有個價格差。可以這簡單這么理解我們可以統一計算出每個人前往B城市比前往A城市需要多花的錢(也可以是前往A城市比前往B城市要多花的錢)，然后進行排序，價格差最大的排名第一的人必然只能安排到A城市，這樣能省下的成本費用最大。接著依次往后安排，排第二的人也只能安排到A城市，一直到安排了排第N的人到A城市，剩下的N個人由于前往B城市比前往A城市花費沒那么高全部排到B城市。

偽代碼：

1、新建一個大小和人數一致的int數組sort,用于保存每個人前往B城市比前往A城市多花費的費用(注意費用可以是負數，負數等價理解花費更少)；

2、遍歷costs花費數組，將差值記錄在sort數組元素中；

i.計算第i個人前往B和前往A的差值；

ii.差值左移8位；

iii.左移后加上當前在cost數組中的下標位置i；

3、對差值sort數組進行排序；

4、聲明一個int變量min表示最小花費總和，循環遍歷sort數組，遍歷次數只需人數的一半costs.length/2;

i.對于差值排名前N，即sort中最后的N個人，選擇去A城市的花費，根據sort元素存儲的在costs數組中的下標位置從costs數組中獲取去A城市的花費；

ii.對于差值排名后N，即sort中前N個人，選擇去B城市的花費，根據sort元素存儲的在costs數組中的下標位置從costs數組中獲取去B城市的花費；

iii.min累加所有總花費；

編碼實踐

public int twoCitySchedCost(int[][] costs) {

int sort[] = new int[costs.length];

for (int i = 0; i < costs.length; ++i) {

sort[i] = ((costs[i][1] - costs[i][0]) << 8) + i;

}

Arrays.sort(sort);

int min = 0;

for (int i = 0; i < sort.length / 2; ++i) {

int index1 = sort[costs.length - 1 - i] & 0xFF;

int index2 = sort[i] & 0xFF;

min = min + costs[index1][0] + costs[index2][1];

}

return min;

}

彩蛋

觀察上面實現代碼會發現在sort數組中存儲前往B和A城市int差價和在costs數組中下標位置時，使用了左移8位再加i的操作，這便是本文的彩蛋，所有彩蛋均會在后續推文中統一說明。

結語

本文重點在與列舉1029實例展示對貪心思想的理解，思路相對簡單易于理解，并且從提交結果可以看出貪心思想算法的實踐代碼效率已經擊敗了99%的算法,故對另外解法窮舉法便不做詳細說明，讀者可以考慮自己使用窮舉法進行實現。關于leetcode進階系列博客，后續也會疏理出一篇比較系統的進階大綱，敬請期待^_^

掃一掃 關注我的微信訂閱號

總結

以上是生活随笔為你收集整理的leetcode 贪心_LeetCode进阶1029-贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。