資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 最短單詞距離 II
假設有一個類，其建構函式接收一個單詞列表，還有一個方法，該方法接收兩個單詞 word1 和 word2，並在列表中查詢這兩個單詞之間的最短距離。該方法將被多次呼叫，引數不同。
讓我們假設 words = ["practice", "makes", "perfect", "skill", "makes"]。
因此，如果輸入為 word1 = “skill”，word2 = “practice”，則輸出將為 3
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 m
初始化器接收一個單詞陣列
對於初始化 i := 0，當 i < 單詞大小，更新 (i 增加 1)，執行：
將 i 插入 m[words[i]] 的末尾
定義一個函式 shortest()，它將接收 word1、word2
定義一個數組 arr1 := m[word1]
定義一個數組 arr2 := m[word2]
i := 0，j := 0
ret := 無窮大
當 (i < arr1 大小 且 j < arr2 大小) 時，執行：
ret := ret 和 |arr1[i] - arr2[j]| 的最小值
如果 arr1[i] < arr2[j]，則：
(i 增加 1)
否則
(j 增加 1)
返回 ret
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class WordDistance {
public:
unordered_map <string, vector <int< > m;
WordDistance(vector<string<& words) {
for(int i = 0; i < words.size(); i++){
m[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
vector<int<& arr1 = m[word1];
vector<int<& arr2 = m[word2];
int i = 0;
int j = 0;
int ret = INT_MAX;
while (i < arr1.size() && j < arr2.size()) {
ret = min(ret, abs(arr1[i] - arr2[j]));
if (arr1[i] < arr2[j]) {
i++;
}
else
j++;
}
return ret;
}
};
main(){
vector<string< v = {"practice", "makes", "perfect", "skill","makes"};
WordDistance ob(v);
cout << (ob.shortest("skill", "practice")) << endl;
cout << (ob.shortest("makes", "skill"));
}輸入
{"practice", "makes", "perfect", "skill", "makes"}
Call shortest("skill", "practice")
Call shortest("makes", "skill")輸出
3 1
更新於：2020年11月18日
301 次瀏覽
廣告