您好,登錄后才能下訂單哦!
這篇文章主要講解了“Python怎么實(shí)現(xiàn)兩個(gè)列表的最小索引總和”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“Python怎么實(shí)現(xiàn)兩個(gè)列表的最小索引總和”吧!
題目:
假設(shè) Andy 和 Doris 想在晚餐時(shí)選擇一家餐廳,并且他們都有一個(gè)表示最喜愛(ài)餐廳的列表,每個(gè)餐廳的名字用字符串表示。
你需要幫助他們用最少的索引和找出他們共同喜愛(ài)的餐廳。如果答案不止一個(gè),則輸出所有答案并且不考慮順序。你可以假設(shè)總是存在一個(gè)答案。
示例 1:
輸入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 輸出: ["Shogun"] 解釋: 他們唯一共同喜愛(ài)的餐廳是“Shogun”。
示例 2:
輸入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] 輸出: ["Shogun"] 解釋: 他們共同喜愛(ài)且具有最小索引和的餐廳是“Shogun”,它有最小的索引和1(0+1)。
提示:
兩個(gè)列表的長(zhǎng)度范圍都在 [1, 1000] 內(nèi)。
兩個(gè)列表中的字符串的長(zhǎng)度將在 [1,30] 的范圍內(nèi)。
下標(biāo)從 0 開(kāi)始,到列表的長(zhǎng)度減 1。
兩個(gè)列表都沒(méi)有重復(fù)的元素。
解題思路:
兩個(gè)字符串?dāng)?shù)組,找重復(fù)出現(xiàn)的元素,返回其索引和最小的目標(biāo)數(shù)組。最容易想到的解法就是用哈希映射解題,Key 存儲(chǔ)其數(shù)組的每個(gè)元素值,Value 存儲(chǔ)其下標(biāo)索引。第一次遍歷將其中一個(gè)數(shù)組添加到哈希映射,第二次遍歷查找目標(biāo)元素。需要維護(hù)一個(gè)最小索引和來(lái)保證查詢的目標(biāo)索引和為最小。
哈希表解題:
Java:
class Solution { public String[] findRestaurant(String[] list1, String[] list2) { Map<String, Integer> map = new HashMap<>();//建立哈希映射 for (int i = 0; i < list1.length; i++)//初次遍歷將一個(gè)數(shù)組建立映射關(guān)系 map.put(list1[i], i); List<String> res = new ArrayList<>();//待返回的目標(biāo)數(shù)組 int sum = Integer.MAX_VALUE;//sum為當(dāng)前滿足條件的最小索引和 for (int i = 0; i < list2.length; i++) {//第二次遍歷查找目標(biāo)元素 if (map.containsKey(list2[i])) { int tmp = i + map.get(list2[i]);//當(dāng)前索引和 if (tmp < sum) {//如果當(dāng)前索引和更小 res.clear();//清除目標(biāo)數(shù)組 res.add(list2[i]);//添加該元素 sum = tmp;// 刷新最小索引和 } else if (tmp == sum)//如果索引和相等 res.add(list2[i]);//只添加元素 } } return res.toArray(new String[res.size()]);//轉(zhuǎn)成 string 數(shù)組 } }
Python:
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: hash_map = dict()# 建立哈希映射 for i, s in enumerate(list1):# 初次遍歷將一個(gè)數(shù)組建立映射關(guān)系 hash_map[s] = i min_sum = 2001# 當(dāng)前滿足條件的最小索引和 res = list()# 待返回的目標(biāo)數(shù)組 for i, s in enumerate(list2):# 第二次枚舉遍歷查找目標(biāo)元素 if s in hash_map: tmp = i+hash_map[s]# 當(dāng)前索引和 if tmp < min_sum:# 如果當(dāng)前索引和更小 res.clear()# 清除目標(biāo)數(shù)組 res.append(s)# 添加該元素 min_sum = tmp# 刷新最小索引和 elif tmp == min_sum:# 如果索引和相等 res.append(s)# 只添加元素 return res
操作索引解題:
這種解法非常巧妙,雖然效率很低。以下解釋摘自 LeetCode,可以作為參考擴(kuò)展思路:
另一種可以遍歷不同 sumsum (下標(biāo)和),并判斷是否有字符串分別出現(xiàn)在 list1 和 list2 中且下標(biāo)和為 sum。
現(xiàn)在我們知道下標(biāo)和的值 sum 數(shù)值范圍從 0 到 m + n - 1。這里 m 和 n 分別是 list1 和 list2 的長(zhǎng)度,我們現(xiàn)在可以升序枚舉 sum ,對(duì)于每個(gè) sum,我們遍歷 list1,假設(shè)當(dāng)前下標(biāo)為 i,為了得到下標(biāo)和 sum,list2 中的下標(biāo) j 為 sum?i。通過(guò)這樣的辦法,我們不需要遍歷 list2,而可以直接通過(guò)計(jì)算得到在 list2 中對(duì)應(yīng)的下標(biāo)。
對(duì)于每個(gè) sum,我們遍歷 list1 的所有下標(biāo),一旦有 list1 和 list2 中的字符串匹配,就把匹配字符串放入一個(gè) res 列表中。
我們對(duì) sum 升序數(shù)組中所有值做相同的過(guò)程,對(duì)于每個(gè) sum 遍歷完一遍 list1 之后,我們檢查 res 列表是否為空。如果是空的,我們繼續(xù)遍歷下一個(gè) sum 數(shù)組。如果不為空,當(dāng)前的 res 就是最小下標(biāo)和的數(shù)組。這是因?yàn)槲覀儽闅v sum 的順序是升序的,所以第一個(gè)找到的列表就是結(jié)果列表。
Java:
class Solution { public String[] findRestaurant(String[] list1, String[] list2) { List<String> res = new ArrayList<>(); for (int sum = 0; sum < list1.length + list2.length - 1; sum++) { for (int i = 0; i <= sum; i++) { if (i < list1.length && sum - i < list2.length && list1[i].equals(list2[sum - i])) res.add(list1[i]); } if (res.size() > 0) break;//一旦找到最小索引和序列直接結(jié)束遍歷,因?yàn)閟um是遞增的,之后得到的索引和一定更大 } return res.toArray(new String[res.size()]); } }
Python
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: res = list() list1_size, list2_size = len(list1), len(list2) for min_sum in range(list1_size+list2_size-1): for i in range(min_sum+1): if i < list1_size and min_sum-i < list2_size and list1[i] == list2[min_sum-i]: res.append(list1[i]) if len(res) > 0:# 一旦找到最小索引和序列直接結(jié)束遍歷,因?yàn)閟um是遞增的,之后得到的索引和一定更大 break return res
感謝各位的閱讀,以上就是“Python怎么實(shí)現(xiàn)兩個(gè)列表的最小索引總和”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)Python怎么實(shí)現(xiàn)兩個(gè)列表的最小索引總和這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。