資訊專(zhuān)欄INFORMATION COLUMN
摘要：代碼第一次寫(xiě)入就先不比較第一次寫(xiě)入就先不比較哈希表法復(fù)雜度時(shí)間空間思路因?yàn)闀?huì)多次調(diào)用，我們不能每次調(diào)用的時(shí)候再把這兩個(gè)單詞的下標(biāo)找出來(lái)。我們可以用一個(gè)哈希表，在傳入字符串?dāng)?shù)組時(shí)，就把每個(gè)單詞的下標(biāo)找出存入表中。
Shortest Word Distance
雙指針?lè)?/b> 復(fù)雜度Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
時(shí)間 O(N) 空間 O(1)
思路一個(gè)指針指向word1上次出現(xiàn)的位置，一個(gè)指針指向word2上次出現(xiàn)的位置。因?yàn)閮蓚€(gè)單詞如果比較接近的話(huà)，肯定是相鄰的word1和word2的位置之差，所以我們只要每次得到一個(gè)新位置和另一個(gè)單詞的位置比較一下就行了。
代碼public class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int idx1 = -1, idx2 = -1, distance = Integer.MAX_VALUE;
for(int i = 0; i < words.length; i++){
if(words[i].equals(word1)){
idx1 = i;
// 第一次寫(xiě)入idx就先不比較
if(idx2 != -1) distance = Math.min(distance, idx1 - idx2);
}
if(words[i].equals(word2)){
idx2 = i;
// 第一次寫(xiě)入idx就先不比較
if(idx1 != -1) distance = Math.min(distance, idx2 - idx1);
}
}
return distance;
}
}
Shortest Word Distance II
哈希表法 復(fù)雜度This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
時(shí)間 O(N) 空間 O(N)
思路因?yàn)闀?huì)多次調(diào)用，我們不能每次調(diào)用的時(shí)候再把這兩個(gè)單詞的下標(biāo)找出來(lái)。我們可以用一個(gè)哈希表，在傳入字符串?dāng)?shù)組時(shí)，就把每個(gè)單詞的下標(biāo)找出存入表中。這樣當(dāng)調(diào)用最短距離的方法時(shí)，我們只要遍歷兩個(gè)單詞的下標(biāo)列表就行了。具體的比較方法，則類(lèi)似merge two list，每次比較兩個(gè)list最小的兩個(gè)值，得到一個(gè)差值。然后把較小的那個(gè)給去掉。因?yàn)槲覀儽闅v輸入數(shù)組時(shí)是從前往后的，所以下標(biāo)列表也是有序的。
代碼public class WordDistance {
HashMap> map = new HashMap>();
public WordDistance(String[] words) {
// 統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的下標(biāo)存入哈希表中
for(int i = 0; i < words.length; i++){
List cnt = map.get(words[i]);
if(cnt == null){
cnt = new ArrayList();
}
cnt.add(i);
map.put(words[i], cnt);
}
}
public int shortest(String word1, String word2) {
List idx1 = map.get(word1);
List idx2 = map.get(word2);
int distance = Integer.MAX_VALUE;
int i = 0, j = 0;
// 每次比較兩個(gè)下標(biāo)列表最小的下標(biāo)，然后把跳過(guò)較小的那個(gè)
while(i < idx1.size() && j < idx2.size()){
distance = Math.min(Math.abs(idx1.get(i) - idx2.get(j)), distance);
if(idx1.get(i) < idx2.get(j)){
i++;
} else {
j++;
}
}
return distance;
}
}
Shortest Word Distance III
雙指針?lè)?/b> 復(fù)雜度This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1. Given word1 = "makes", word2 = "makes", return 3.
Note: You may assume word1 and word2 are both in the list.
時(shí)間 O(N) 空間 O(N)
思路這題和I是一樣的，唯一不同的是對(duì)于word1和word2相同的時(shí)候，我們要區(qū)分第一次遇到和第二次遇到這個(gè)詞。這里加入了一個(gè)turns，如果是相同單詞的話(huà)，每次遇到一個(gè)單詞turn加1，這樣可以根據(jù)turn來(lái)判斷是否要switch。
代碼public class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
int idx1 = -1, idx2 = -1, distance = Integer.MAX_VALUE, turn = 0, inc = (word1.equals(word2) ? 1 : 0);
for(int i = 0; i < words.length; i++){
if(words[i].equals(word1) && turn % 2 == 0){
idx1 = i;
if(idx2 != -1) distance = Math.min(distance, idx1 - idx2);
turn += inc;
} else if(words[i].equals(word2)){
idx2 = i;
if(idx1 != -1) distance = Math.min(distance, idx2 - idx1);
turn += inc;
}
}
return distance;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/64722.html
摘要：另外，為了避免產(chǎn)生環(huán)路和重復(fù)計(jì)算，我們找到一個(gè)存在于字典的新的詞時(shí)，就要把它從字典中移去。代碼用來(lái)記錄跳數(shù)控制來(lái)確保一次循環(huán)只計(jì)算同一層的節(jié)點(diǎn)，有點(diǎn)像二叉樹(shù)遍歷循環(huán)這個(gè)詞從第一位字母到最后一位字母循環(huán)這一位被替換成個(gè)其他字母的情況 Word Ladder Given two words (beginWord and endWord), and a dictionary, find t...
Problem Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the l...
Problem Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. word1 and word2 may be the same and they represent two individual words i...
Problem Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. Example:Assume that words = [practice, makes, perfect, coding, makes]. In...
摘要：存放過(guò)程中的所有集合為所有的結(jié)尾，則順序存放這個(gè)結(jié)尾對(duì)應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的，在下一個(gè)循環(huán)再依次對(duì)其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新，再將放入，并將鍵值對(duì)放入，進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
閱讀 3615·2021-11-22 09:34
閱讀 3186·2021-11-15 11:38
閱讀 3039·2021-10-27 14:16
閱讀 1233·2021-10-18 13:35
閱讀 2424·2021-09-30 09:48
閱讀 3429·2021-09-29 09:34
閱讀 1626·2019-08-30 15:54
閱讀 1818·2019-08-26 11:57
