数据结构
网络
关系数据库管理系统 (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
广告