資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中目標顏色的最短距離
假設我們有一個名為 color 的陣列，其中包含三種顏色：1、2 和 3。我們給出了一些查詢。每個查詢包含兩個整數 i 和 c，我們需要找到給定索引 i 和目標顏色 c 之間的最短距離。如果沒有解決方案，則返回 -1。因此，如果顏色陣列像 [1,1,2,1,3,2,2,3,3]，查詢陣列像 [[1,3], [2,2], [6,1]]，則輸出將是 [3,0,3]。這是因為索引 1 處最近的 3 在索引 4 處（距離 3 步）。然後索引 2 處最近的 2 在索引 2 本身（距離 0 步）。而索引 6 處最近的 1 在索引 3 處（距離 3 步）。
為了解決這個問題，我們將遵循以下步驟：
建立一個名為 index 的矩陣，其中包含 4 行，n := color 陣列中元素的數量
對於 I 從 0 到 n – 1 的範圍
將 i 插入到 index[colors[i]] 中
x := queries[i, 0] 和 c := queries[i, 1]
如果 index[c] 的大小為 0，則將 -1 插入 ret，並跳過下一個迭代
it := 第一個不小於 x - index[c] 的第一個元素
op1 := 無窮大，op2 := 無窮大
如果 it = index[c] 的大小，則將其減 1，op1 := |x – index[c, it]|
否則，當 it = 0 時，則 op1 := |x – index[c, it]|
否則，op1 := |x – index[c, it]|，將其減 1，op2 := |x – index[c, it]|
將 op1 和 op2 的最小值插入 ret
返回 ret
示例（C++）
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
vector < vector <int> >idx(4);
int n = colors.size();
for(int i = 0; i < n; i++){
idx[colors[i]].push_back(i);
}
vector <int> ret;
for(int i = 0; i < queries.size(); i++){
int x = queries[i][0];
int c = queries[i][1];
if(idx[c].size() == 0){
ret.push_back(-1);
continue;
}
int it = lower_bound(idx[c].begin(), idx[c].end() , x) - idx[c].begin();
int op1 = INT_MAX;
int op2 = INT_MAX;
if(it == idx[c].size()){
it--;
op1 = abs(x - idx[c][it]);
}
else if(it == 0){
op1 = abs(x - idx[c][it]);
}
else{
op1 = abs(x - idx[c][it]);
it--;
op2 = abs(x - idx[c][it]);
}
ret.push_back(min(op1, op2));
}
return ret;
}
};
main(){
vector<int> v = {1,1,2,1,3,2,2,3,3};
vector<vector<int>> v1 = {{1,3},{2,2},{6,1}};
Solution ob;
print_vector(ob.shortestDistanceColor(v, v1));
}輸入
[1,1,2,1,3,2,2,3,3] [[1,3],[2,2],[6,1]]
輸出
[3,0,3]
更新於： 2020-04-29
205 次檢視
廣告