LeetCode演算法題-Minimum Index Sum of Two Lists(Java實現)
這是悅樂書的第272 次更新,第286 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第139題(順位題號是599)。假設Andy和Doris想要選擇一家餐館吃晚餐,他們都有一個最受歡迎的餐館列表。你需要用最少的列表索引總和幫助他們找出他們的共同興趣。如果答案之間存在選擇關係,則輸出所有答案並且沒有順序要求。你可以假設總有一個答案。例如:
輸入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
輸出: ["Shogun"]
說明: 他們都喜歡的唯一一家餐廳是“Shogun”。
輸入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
輸出: ["Shogun"]
說明: 他們喜歡並且索引總和最少的餐館是“Shogun”,索引和1(0 + 1)。
注意:
-
兩個列表的長度將在[1,1000]的範圍內。
-
兩個列表中的字串長度將在[1,30]的範圍內。
-
索引從0開始到列表長度減去1。
-
兩個列表中都沒有重複項。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
使用兩個HashMap,分別將list1和list2的元素存入其中,以元素值為key,索引為value。定義一個最小值min,初始值為int的最大值,然後遍歷其中一個map的key值,如果第二個map中也存在該key,此時分為兩種情況處理。
第一種情況,如果該key值對應兩索引之和小於min,那麼將min更新,再將結果陣列清空,再將該key新增進結果陣列。
第二種情況,如果該key值對應兩索引之和等於min,表明存在另外一對索引之和,直接將key新增進結果陣列即可。
最後返回結果陣列。
public String[] findRestaurant(String[] list1, String[] list2) { Map<String, Integer> map = new HashMap<>(); Map<String, Integer> map2 = new HashMap<>(); for(int i=0; i<list1.length; i++){ map.put(list1[i], i); } for(int i=0; i<list2.length; i++){ map2.put(list2[i], i); } int min = Integer.MAX_VALUE; List<String> result = new ArrayList<>(); for (String key : map.keySet()) { if (map2.containsKey(key)) { if (map.get(key)+map2.get(key) < min) { min = map.get(key)+map2.get(key); result = new ArrayList<>(); result.add(key); } else if (map.get(key)+map2.get(key) == min) { result.add(key); } } } return result.toArray(new String[result.size()]); }
03 第二種解法
我們可以將第一種解法再簡化下,只使用一個HashMap,然後遍歷剩下的那個陣列,判斷思路與第一種解法一致。同時,我們也可以將迴圈內部使用建立新物件來清空陣列的方法,換成其自身的clear()方法。
public String[] findRestaurant2(String[] list1, String[] list2) { Map<String, Integer> map = new HashMap<>(); for(int i=0; i<list1.length; i++){ map.put(list1[i], i); } int min = Integer.MAX_VALUE; List<String> result = new ArrayList<>(); for (int i=0; i<list2.length; i++) { if (map.containsKey(list2[i])) { if (map.get(list2[i])+i < min) { min = map.get(list2[i])+i; result.clear(); result.add(list2[i]); } else if (map.get(list2[i])+i == min) { result.add(list2[i]); } } } return result.toArray(new String[result.size()]); }
04 第三種解法
我們也可以不使用HashMap,直接使用for迴圈來解決。
public String[] findRestaurant3(String[] list1, String[] list2) { int min = Integer.MAX_VALUE; List<String> result = new ArrayList<>(); for (int i=0; i<list1.length; i++) { for (int j=0; j<list2.length; j++) { if (list1[i].equals(list2[j])) { if (j+i < min) { min = j+i; result.clear(); result.add(list1[i]); } else if (j+i == min) { result.add(list1[i]); } } } } return result.toArray(new String[result.size()]); }
05 小結
演算法專題目前已日更超過四個月 ,演算法題文章139 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!