提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

599. Minimum Index Sum of Two Lists

of index sum two minimum lists
2023-09-11 14:22:45 时间

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

 

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

 

Note:

  1. The length of both lists will be in the range of [1, 1000].
  2. The length of strings in both lists will be in the range of [1, 30].
  3. The index is starting from 0 to the list length minus 1.
  4. No duplicates in both lists.

 

Approach #1: C++.
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        int size1 = list1.size();
        int size2 = list2.size();
        unordered_map<string, int> mp;
        vector<pair<string, int>> v;
        vector<string> ans;
        
        for (int i = 0; i < size1; ++i) 
            mp[list1[i]] = i;
        
        for (int i = 0; i < size2; ++i) {
            if (mp.count(list2[i])) {
                v.push_back({list2[i], i + mp[list2[i]]});
            }
        }
        
        sort(v.begin(), v.end(), cmp);
        
        ans.push_back(v[0].first);
        
        for (int i = 1; i < v.size(); ++i) {
            if (v[i].second == v[i-1].second) 
                ans.push_back(v[i].first);
            else 
                break;
        }
        return ans;
    }
    
private:
    static bool cmp(pair<string, int> a, pair<string, int> b) {
        return a.second < b.second;
    }
};

　　

 Approach #2: 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;
        }
        return res.toArray(new String[res.size()]);
    }
}

　　

Approach #3: Python.

class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        list1Index = {u: i for i, u in enumerate(list1)}
        best, ans = 1e9, []
        
        for j, v in enumerate(list2):
            i = list1Index.get(v, 1e9)
            if i + j < best:
                best = i + j
                ans = [v]
            elif i + j == best:
                ans.append(v)
        return ans;

　　

Time SubmittedStatusRuntimeLanguage
a few seconds ago Accepted 128 ms python
4 minutes ago Accepted 79 ms java
23 minutes ago Accepted 72 ms cpp

Analysis:

In the aproach two we don't use map, however we use the sum represent the summation with the index of i and j. if it satisfy the statement of:

if (i < list1.length && sum-i < list2.length && list1[i].equals(list2[sum-i]))

it will be the minimum sum which we want to find.

 

 

Python -> Enumerate

Enumerate is a built-in function of Python. Its usefulness can not be summarized in a single line. Yet most of the newcomers and even some advanced programmers are unaware of it. It allows us to loop over something and have an automatic counter. Here is an example:

for counter, value in enumerate(some_list):
    print(counter, value)

And there is more! enumerate also accepts an optional argument which makes it even more useful.

my_list = ['apple', 'banana', 'grapes', 'pear']
for c, value in enumerate(my_list, 1):
    print(c, value)

# Output:
# 1 apple
# 2 banana
# 3 grapes
# 4 pear

The optional argument allows us to tell enumerate from where to start the index. You can also create tuples containing the index and list item using a list. Here is an example:

my_list = ['apple', 'banana', 'grapes', 'pear']
counter_list = list(enumerate(my_list, 1))
print(counter_list)
# Output: [(1, 'apple'), (2, 'banana'), (3, 'grapes'), (4, 'pear')]

 

come from: http://book.pythontips.com/en/latest/enumerate.html

 

相关文章