資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查路徑序列是否重複訪問任何座標
在某些應用中，我們可能需要檢查路徑序列是否重複訪問任何座標。例如，這在 GPS 跟蹤系統中很有用，可以檢測車輛是否在兩點之間來回移動。在本文中，我們將討論如何檢查路徑序列是否重複訪問任何座標，以及其在 C++ 中的實現。
演算法
為了解決這個問題，我們可以使用雜湊表來跟蹤到目前為止我們已經訪問過的所有座標。我們從訪問序列中的第一個座標開始，並將其新增到雜湊表中。然後，對於序列中的每個後續座標，我們檢查它是否已經在雜湊表中。如果在，我們知道我們之前已經訪問過這個座標，我們可以返回 true。如果不在，我們將它新增到雜湊表中並繼續到下一個座標。如果我們已經訪問了所有座標而沒有找到任何重複項，我們可以返回 false。
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
bool isVisitedTwice(int n, int path[][2]) {
int **visited = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
visited[i] = (int *)malloc(2 * sizeof(int));
for (int j = 0; j < 2; j++) {
visited[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
if (visited[path[i][0]][path[i][1]] == 1) {
// Free dynamically allocated memory before returning.
for (int j = 0; j < n; j++) {
free(visited[j]);
}
free(visited);
return true;
}
visited[path[i][0]][path[i][1]] = 1;
}
// Free dynamically allocated memory before returning.
for (int j = 0; j < n; j++) {
free(visited[j]);
}
free(visited);
return false;
}
int main() {
// Test case 1
int path1[5][2] = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}};
if (isVisitedTwice(5, path1)) {
printf("Sequence visits a coordinate twice\n");
} else {
printf("Sequence does not visit a coordinate twice\n");
}
// Test case 2
int path2[6][2] = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {3, 3}};
if (isVisitedTwice(6, path2)) {
printf("Sequence visits a coordinate twice\n");
} else {
printf("Sequence does not visit a coordinate twice\n");
}
// Test case 3
int path3[3][2] = {{0, 0}, {1, 1}, {2, 2}};
if (isVisitedTwice(3, path3)) {
printf("Sequence visits a coordinate twice\n");
} else {
printf("Sequence does not visit a coordinate twice\n");
}
return 0;
}
輸出
Sequence does not visit a coordinate twice Sequence visits a coordinate twice Sequence does not visit a coordinate twice
#include<bits/stdc++.h>
using namespace std;
bool isVisitedTwice(int n, int path[][2]) {
set<pair<int, int>> visited;
for(int i=0;i<n;i++) {
// Check if the current coordinate has already been visited
if(visited.find(make_pair(path[i][0], path[i][1])) != visited.end()) {
return true;
}
visited.insert(make_pair(path[i][0], path[i][1]));
}
return false;
}
int main() {
// Test case 1
int path1[5][2] = {{0,0},{1,1},{2,2},{3,3},{4,4}};
if(isVisitedTwice(5, path1)) {
cout << "Sequence visits a coordinate twice" << endl;
} else {
cout << "Sequence does not visit a coordinate twice" << endl;
}
// Test case 2
int path2[6][2] = {{0,0},{1,1},{2,2},{3,3},{4,4},{3,3}};
if(isVisitedTwice(6, path2)) {
cout << "Sequence visits a coordinate twice" << endl;
} else {
cout << "Sequence does not visit a coordinate twice" << endl;
}
// Test case 3
int path3[3][2] = {{0,0},{1,1},{2,2}};
if(isVisitedTwice(3, path3)) {
cout << "Sequence visits a coordinate twice" << endl;
} else {
cout << "Sequence does not visit a coordinate twice" << endl;
}
return 0;
}
輸出
Sequence does not visit a coordinate twice Sequence visits a coordinate twice Sequence does not visit a coordinate twice
import java.util.HashSet;
public class VisitedTwice {
static boolean isVisitedTwice(int n, int[][] path) {
HashSet<String> visited = new HashSet<>();
for (int i = 0; i < n; i++) {
// Check if the current coordinate has already been visited
String coordinate = path[i][0] + "," + path[i][1];
if (visited.contains(coordinate)) {
return true;
}
visited.add(coordinate);
}
return false;
}
public static void main(String[] args) {
// Test case 1
int[][] path1 = {{0,0},{1,1},{2,2},{3,3},{4,4}};
if (isVisitedTwice(5, path1)) {
System.out.println("Sequence visits a coordinate twice");
} else {
System.out.println("Sequence does not visit a coordinate twice");
}
// Test case 2
int[][] path2 = {{0,0},{1,1},{2,2},{3,3},{4,4},{3,3}};
if (isVisitedTwice(6, path2)) {
System.out.println("Sequence visits a coordinate twice");
} else {
System.out.println("Sequence does not visit a coordinate twice");
}
// Test case 3
int[][] path3 = {{0,0},{1,1},{2,2}};
if (isVisitedTwice(3, path3)) {
System.out.println("Sequence visits a coordinate twice");
} else {
System.out.println("Sequence does not visit a coordinate twice");
}
}
}
輸出
Sequence does not visit a coordinate twice Sequence visits a coordinate twice Sequence does not visit a coordinate twice
def is_visited_twice(n, path):
visited = set()
for i in range(n):
if tuple(path[i]) in visited:
return True
visited.add(tuple(path[i]))
return False
# Test case 1
path1 = [[0,0],[1,1],[2,2],[3,3],[4,4]]
if is_visited_twice(5, path1):
print("Sequence visits a coordinate twice")
else:
print("Sequence does not visit a coordinate twice")
# Test case 2
path2 = [[0,0],[1,1],[2,2],[3,3],[4,4],[3,3]]
if is_visited_twice(6, path2):
print("Sequence visits a coordinate twice")
else:
print("Sequence does not visit a coordinate twice")
# Test case 3
path3 = [[0,0],[1,1],[2,2]]
if is_visited_twice(3, path3):
print("Sequence visits a coordinate twice")
else:
print("Sequence does not visit a coordinate twice")
輸出
Sequence does not visit a coordinate twice Sequence visits a coordinate twice Sequence does not visit a coordinate twice
測試用例示例
考慮序列 "UDDLLRUUUDU"，它表示路徑 "上、下、下、左、左、右、上、上、下、上"。
我們從原點 (0, 0) 開始遍歷路徑，並在前進時更新我們的座標。
在每一步，我們檢查我們是否之前已經訪問過新的座標。如果是，我們知道該序列訪問了同一個座標兩次，我們返回 true。如果不是，我們標記該座標為已訪問並繼續。
以下是該演算法對給定序列的工作方式：
從原點 (0, 0) 開始
"U" − 向上移動到 (0, 1)。標記 (0, 1) 為已訪問。
"D" − 向下移動到 (0, 0)。標記 (0, 0) 為已訪問。
"D" − 向下移動到 (0, -1)。標記 (0, -1) 為已訪問。
"L" − 向左移動到 (-1, -1)。標記 (-1, -1) 為已訪問。
"L" − 向左移動到 (-2, -1)。標記 (-2, -1) 為已訪問。
"R" − 向右移動到 (-1, -1)。這個座標之前已經被訪問過，所以我們返回 true。
由於序列訪問了同一個座標兩次，所以函式返回 true。
因此，對於給定的序列 "UDDLLRUUUDU"，該函式正確地返回該序列訪問了同一個座標兩次。
結論
在本文中，我們討論瞭如何檢查路徑序列是否重複訪問任何座標。我們使用雜湊表來跟蹤到目前為止我們已經訪問過的所有座標，並在每一步檢查重複項。我們還在 C 中提供了該演算法的實現。
更新於：2023年10月16日
瀏覽量：102
廣告