Shulou(Shulou.com)06/02 Report--

This article mainly explains the "Python how to achieve the minimum index sum of the two lists", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's ideas slowly in depth, together to study and learn "Python how to achieve the minimum index sum of the two lists" bar!

Title:

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants, with the name of each restaurant represented by a string.

You need to help them use the least index and find out their favorite restaurants. If there is more than one answer, all the answers are output regardless of the order. You can assume that there is always an answer.

Example 1:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] output: ["Shogun"] explain: their only favorite restaurant is "Shogun".

Example 2:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] output: ["Shogun"] explain: their favorite restaurant with the smallest index and sum is "Shogun", which has the smallest index and 1 (0 index 1).

Tip:

The length range of both lists is within [1, 1000].

The length of the strings in the two lists will be in the range of [1JI 30].

The subscript starts at 0 and subtracts 1 from the length of the list.

There are no duplicate elements in either list.

Ideas for solving the problem:

Two string arrays, find the repeating elements, and return their index and the smallest target array. The easiest solution is to use a hash map to solve the problem. Key stores the value of each element of its array, and Value stores its subscript index. The first traversal adds one of the arrays to the hash map, and the second traversal looks for the target element. You need to maintain a minimum index to ensure that the target index of the query is minimum.

Hash table problem solving:

Java:

Class Solution {public String [] findRestaurant (String [] list1, String [] list2) {Map map = new HashMap (); / / establish a hash map for (int I = 0; I

< list1.length; i++)//初次遍历将一个数组建立映射关系 map.put(list1[i], i); List res = new ArrayList();//待返回的目标数组 int sum = Integer.MAX_VALUE;//sum为当前满足条件的最小索引和 for (int i = 0; i < list2.length; i++) {//第二次遍历查找目标元素 if (map.containsKey(list2[i])) { int tmp = i + map.get(list2[i]);//当前索引和 if (tmp < sum) {//如果当前索引和更小 res.clear();//清除目标数组 res.add(list2[i]);//添加该元素 sum = tmp;// 刷新最小索引和 } else if (tmp == sum)//如果索引和相等 res.add(list2[i]);//只添加元素 } } return res.toArray(new String[res.size()]);//转成 string 数组 }} Python： class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) ->

List [str]: hash_map = dict () # establish hash mapping for I, s in enumerate (list1): # the first traversal establishes a mapping relationship between an array hash_ [s] = I min_sum = 200 minimum index and res = list () # the target array for I to be returned S in enumerate (list2): # the second enumeration traverses to find the target element if s in hash_map: tmp = iSuppli hashmap [s] # current index and if tmp

< min_sum:# 如果当前索引和更小 res.clear()# 清除目标数组 res.append(s)# 添加该元素 min_sum = tmp# 刷新最小索引和 elif tmp == min_sum:# 如果索引和相等 res.append(s)# 只添加元素 return res 操作索引解题： 这种解法非常巧妙，虽然效率很低。以下解释摘自 LeetCode，可以作为参考扩展思路： 另一种可以遍历不同 sumsum (下标和)，并判断是否有字符串分别出现在 list1 和 list2 中且下标和为 sum。 现在我们知道下标和的值 sum 数值范围从 0 到 m + n - 1。这里 m 和 n 分别是 list1 和 list2 的长度，我们现在可以升序枚举 sum ，对于每个 sum，我们遍历 list1，假设当前下标为 i，为了得到下标和 sum，list2 中的下标 j 为 sum−i。通过这样的办法，我们不需要遍历 list2，而可以直接通过计算得到在 list2 中对应的下标。 对于每个 sum，我们遍历 list1 的所有下标，一旦有 list1 和 list2 中的字符串匹配，就把匹配字符串放入一个 res 列表中。 我们对 sum 升序数组中所有值做相同的过程，对于每个 sum 遍历完一遍 list1 之后，我们检查 res 列表是否为空。如果是空的，我们继续遍历下一个 sum 数组。如果不为空，当前的 res 就是最小下标和的数组。这是因为我们遍历 sum 的顺序是升序的，所以第一个找到的列表就是结果列表。 Java： class Solution { public String[] findRestaurant(String[] list1, String[] list2) { List res = new ArrayList(); for (int sum = 0; sum < list1.length + list2.length - 1; sum++) { for (int i = 0; i 0) break;//一旦找到最小索引和序列直接结束遍历，因为sum是递增的，之后得到的索引和一定更大 } 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) >

Once the minimum index and sequence are found, the traversal ends directly, because the sum is incremental, and then the index and the larger break return res thank you for your reading. the above is the content of "how Python achieves the minimum index sum of the two lists". After the study of this article, I believe you have a deeper understanding of how Python realizes the minimum index sum of the two lists. The specific use situation still needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.