preface
Record the leetcode problem for the day
Topic describes
Let’s say 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 find their favorite restaurants with minimal indexing. If there is more than one answer, all answers are printed regardless of order. You can assume the answer is always there.
Example 1
Input: List1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], List2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] The only restaurant they love together is Shogun.Copy the code
Example 2
Input :list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["KFC", "Shogun", "Burger King"] ["Shogun"] Explanation: Their favorite restaurant with the smallest index sum is "Shogun", which has the smallest index and 1(0+1).Copy the code
prompt
- 1 <= list1.length, list2.length <= 1000
- 1 <= list1[i].length, list2[i].length <= 30
- List1 [I] and list2[I] consist of Spaces and letters.
- All strings for List1 are unique.
- All strings in list2 are unique.
Train of thought
Similar to duplicate lookup, you can create a table to store the first person’s restaurant list and index. Iterate over the second restaurant list to see if it exists in the current table. Here, a variable can be created to store the current minimum index of both restaurants. If both restaurants have subindexes less than the minimum index, then this restaurant is considered to be the minimum index and the favorite restaurant. If it is equal to the minimum index, then there can be multiple restaurants that meet the conditions
code
/ * * *@param {string[]} list1
* @param {string[]} list2
* @return {string[]}* /
var findRestaurant = function (list1, list2) {
const hash = new Map(a)let result = []
// Stores the first traversed data into the hash using the subscript
list1.forEach((item, index) = > {
hash.set(item, index)
})
let minIndex = Number.MAX_VALUE // Store the current minimum index
list2.forEach((item, index) = > {
if (hash.has(item)) {
if (index + hash.get(item) < minIndex) {
// Determine whether their minimum index is smaller than the current record
result.length = 0 // Clear the previous data
minIndex = index + hash.get(item) // Recalculate current minimum index
result.push(item) // Store public restaurants
} else if (index + hash.get(item) == minIndex) {
result.push(item) // Multiple common favorites are represented here}}})return result
};
Copy the code
The last
Make a little progress every day