Leetcode

LeetCode: suma mínima de l’índex de dues llistes

Leetcode Minimum Index Sum Two Lists



Descripció ：
Suposem que Andy i Doris volen triar un restaurant per sopar i que tots dos tenen una llista de restaurants preferits representats per cordes.

Heu d’ajudar-los a conèixer el seu interès comú amb la suma d’índex mínima de llista. Si hi ha un vincle d'elecció entre respostes, envieu-les totes sense cap requisit d'ordre. Es podria suposar que sempre existeix una resposta.



Exemple 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'.

Exemple 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).

Nota:

  • La longitud d'ambdues llistes estarà en l'interval de [1, 1000].
  • La longitud de les cadenes de les dues llistes serà de [1, 30].
  • L'índex comença de 0 a la longitud de la llista menys 1.
  • No hi ha duplicats a les dues llistes.

Intenció: una cadena pública que calcula una matriu de dues cadenes, que possiblement conté més d'una, però que requereix la posició del subíndex i el mínim d'aquestes cadenes públiques (a la matriu)

Solució: hi ha una fossa que requereix la posició del subíndex i el mínim d’aquestes cadenes públiques a les dues matrius de cadenes. De fet, només hi ha dos casos:



  1. El resultat retornat només conté una cadena
  2. El resultat retornat conté diverses cadenes les posicions del subíndex són les mateixes a les dues matrius de cadenes

Després d’utilitzar la taula de hash per enregistrar totes les cadenes de la primera matriu de cadenes i les seves posicions de subíndex, travesseu la segona matriu de cadenes; el procés de càlcul és el següent

for str in list2: There is no str in the if hash table: Judge the next string If str is the first public string found: Add str to the result string array res and record the subscript position and indexSum at this time Elif the current subscript position of the string and
Java
class Solution { public String[] findRestaurant(String[] list1, String[] list2) { StringBuilder res = new StringBuilder() int indexSum = -1 Map map = new HashMap() int ind = 0 for (String str: list1) { map.put(str, ind) ind++ } ind = 0 for (String str: list2) { if (!map.containsKey(str)) { ind++ continue } int tempSum = map.get(str) + ind if (indexSum == -1) { indexSum = tempSum res.append(str) } else if (tempSum